Na pytania dotyczące analizy złożoności algorytmów kwantowych i porównań ze złożonością algorytmów klasycznych.
Wiadomo, że komputery kwantowe potrafią złamać w czasie wielomianowym szeroki zakres algorytmów kryptograficznych, które wcześniej uważano za możliwe do rozwiązania tylko dzięki zasobom rosnącym wykładniczo wraz z wielkością bitu klucza. Przykładem tego jest algorytm Shora . Ale, o ile wiem, nie...
Powszechnie uważa się i twierdzono, że komputery kwantowe mogą przewyższyć klasyczne urządzenia w przynajmniej niektórych zadaniach. Jednym z najczęściej cytowanych przykładów problemu, w którym komputery kwantowe przewyższałyby klasyczne urządzenia, jest , ale z drugiej strony nie wiadomo...
Algorytm wyszukiwania Grovera zapewnia udowodnione kwadratowe przyspieszenie dla nieposortowanego wyszukiwania w bazie danych. Algorytm jest zwykle wyrażany przez następujący obwód kwantowy: W większości przedstawień kluczową częścią protokołu jest „wyrocznia” UωUωU_\omega , która „magicznie”...
Ten blog autorstwa Scotta Aaronsona jest bardzo przydatnym i prostym wyjaśnieniem algorytmu Shora . Zastanawiam się, czy istnieje takie wytłumaczenie drugiego najbardziej znanego algorytmu kwantowego: algorytmu Grovera do przeszukiwania nieuporządkowanej bazy danych o wielkości w O ( √O ( n...
Standardowe popularne konto informatyki kwantowej mówi, że komputer kwantowy (QC) działałby, dzieląc na wykładniczo wiele nieinterakcyjnych równoległych kopii siebie w różnych wszechświatach i podejmując każdą próbę weryfikacji innego certyfikatu, a następnie na końcu obliczeń , pojedynczy...
Czy istnieje ogólne stwierdzenie o tym, jakie problemy można rozwiązać bardziej efektywnie za pomocą komputerów kwantowych (tylko model bramki kwantowej)? Czy problemy, dla których znany jest dzisiaj algorytm, mają wspólną właściwość? O ile rozumiem obliczenia kwantowe pomagają rozwiązać problem...
Wiele prac twierdzi, że symulacja Hamiltona jest kompletna pod względem BQP (np. Symulacja Hamiltona z prawie optymalną zależnością od wszystkich parametrów i symulacja Hamiltona przez Qubitization ). Łatwo zauważyć, że symulacja Hamiltona jest trudna dla BQP, ponieważ każdy algorytm kwantowy...
Na powierzchni algorytmy kwantowe mają niewiele wspólnego z obliczeniami klasycznymi, aw szczególności P vs NP: Rozwiązywanie problemów z NP za pomocą komputerów kwantowych nie mówi nam nic o relacjach klasycznych klas złożoności 1 . Z drugiej strony „alternatywny opis” klasycznej złożoności PP...
Komputer kwantowy może skutecznie rozwiązywać problemy leżące w klasie złożoności BQP . Widziałem twierdzenie, które może (potencjalnie, ponieważ nie wiemy, czy BQP jest właściwym podzbiorem, czy jest równe PP) zwiększyć wydajność komputera kwantowego poprzez zastosowanie postselekcji i że klasa...
W wyniku doskonałej odpowiedzi na moje pytanie dotyczące bogosortu kwantowego zastanawiałem się, jaki jest obecny stan techniki w algorytmach kwantowych do sortowania. Mówiąc ściślej, sortowanie definiuje się tutaj jako następujący problem: Biorąc pod uwagę tablicę liczb całkowitych (możesz...
Mylę się co do algorytmu Grovera i jego związku z klasami złożoności. Algorytm Grovera znajduje element w bazie danych (tak, że ) elementów z wywołaniami do wyroczni.kkkN=2nN=2nN=2^nf(k)=1f(k)=1f(k)=1∼N−−√=2n/2∼N=2n/2\sim \sqrt{N}=2^{n/2} Mamy więc następujący problem: Problem: Znajdź w bazie...
Jak sama nazwa wskazuje, to pytanie jest kontynuacją tego drugiego . Byłem zachwycony jakością odpowiedzi, ale czułem, że byłoby niezwykle interesujące, gdyby dodano spostrzeżenia dotyczące technik optymalizacji i aproksymacji, ale mogą one nie pasować do tematu, stąd pytanie. Z odpowiedzi...
Czy są jakieś pakiety szyfrowania, które mogą zostać złamane przez zwykłe komputery lub superkomputery, ale nie komputery kwantowe? Jeśli to możliwe, od jakich założeń będzie to zależeć? (Faktoryzacja dużych liczb, a ^ c \ pmod d a ^ {bc} \ pmod d itp ...)a czab( modre)ab(modd)a^b\pmod d zado(...
Chcę wiedzieć, która złożoność czasu jest uważana za wydajną / nieefektywną dla komputerów kwantowych. W tym celu muszę wiedzieć, ile operacji komputer kwantowy może wykonać na sekundę. Czy ktoś może mi powiedzieć, jak to obliczyć i od jakich czynników to zależy (szczegóły wdrożenia lub liczba...
Chciałbym dowiedzieć się więcej o klasach złożoności obliczeniowej w kontekście obliczeń kwantowych. Medium nie jest tak ważne; może to być książka, notatki z wykładów online lub tym podobne. Najważniejsza jest zawartość. Materiał powinien obejmować podstawy kwantowych klas złożoności...
Patrzyłem na notatkę z wykładu, w której autor podaje wyrocznię między nimiBQPBQP\mathsf{BQP} i NPNP\mathsf{NP}. Wskazuje, w jaki sposób można zastosować standardowe techniki diagonalizacji, aby uczynić to rygorystycznym. Czy ktoś może szczegółowo opisać technikę diagonalizacji, którą należy...
Wydaje się, że klasa złożoności BQP (kwantowy wielomian czasowy z ograniczonym błędem) jest zdefiniowana tylko biorąc pod uwagę czynnik czasu. Czy to zawsze ma znaczenie? Czy istnieją algorytmy, w których obliczeniowy czas skaluje się wielomianowo z rozmiarem wejściowym, ale inne zasoby, takie jak...
Ostatnio czytałem o „kwantowym bogosortie” na niektórych wiki. Podstawową ideą jest to, że podobnie jak bogosort, po prostu tasujemy naszą tablicę i mamy nadzieję, że zostanie ona posortowana „przypadkowo” i ponowna próba awarii. Różnica polega na tym, że teraz mamy „ magiczny kwant”, więc...
Numer Boga jest najgorszym przypadku algorytmu Boga , który jest koncepcja wywodząca się z dyskusji na temat sposobów rozwiązania zagadki Kostka Rubika, ale która może być również zastosowana w innych łamigłówkach kombinacyjnych i grach matematycznych. Odnosi się do dowolnego algorytmu, który...