Pytania otagowane jako complexity-theory

Na pytania dotyczące analizy złożoności algorytmów kwantowych i porównań ze złożonością algorytmów klasycznych.

4
Czy możliwe jest istnienie metody szyfrowania, której nie można złamać, nawet przy użyciu komputerów kwantowych?
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 wszystkie problemy należą do tej kategorii. O robieniu trudnych …
4
Czy istnieją problemy, w których wiadomo, że komputery kwantowe zapewniają wykładniczą przewagę?
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 również, czy faktoring można również skutecznie rozwiązać za pomocą klasycznego komputera (tj. Czy …
3
Czy istnieje wyjaśnienie dla laika, dlaczego algorytm Grovera działa?
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 )O(n)O(n)O ( n--√)O(n)O(\sqrt{n}) czas. W szczególności chciałbym zobaczyć zrozumiałą intuicję …
2
Jak zaimplementowana jest wyrocznia w algorytmie wyszukiwania Grovera?
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” wykonuje operację |x⟩↦(−1)f(x)|x⟩|x⟩↦(−1)f(x)|x⟩|x\rangle\mapsto(-1)^{f(x)}|x\rangle . Często jednak nie wiadomo, jak trudno byłoby zrealizować taką bramę. Rzeczywiście mogłoby się …
2
Dlaczego komputer kwantowy jest pod pewnymi względami potężniejszy niż niedeterministyczna maszyna Turinga?
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 egzemplarz, który znalazł ważny certyfikat, „ogłasza” swoje rozwiązanie, a pozostałe oddziały magicznie znikają. Ludzie, …
4
Czy istnieje jakieś ogólne stwierdzenie dotyczące tego, jakie problemy można rozwiązać bardziej efektywnie za pomocą komputera kwantowego?
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 ukrytej podgrupy (Shor); Algorytm Grovera pomaga przyspieszyć problemy z wyszukiwaniem. Czytałem, …
1
Symulacja Hamiltona jest zakończona BQP
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 można zredukować do symulacji Hamiltona, ale jak symulacja Hamiltona w …
1
Czy istnieją wyniki algorytmów kwantowych lub złożoności, które prowadzą do postępu w rozwiązywaniu problemu P vs NP?
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 jako klasy PostBQP przedstawiony w tym artykule jest, …
2
Jaki jest obecny stan algorytmów sortowania kwantowego?
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 swobodnie wybrać swoją reprezentację , ale bądź jasne, myślę, że to już …
2
Czym jest postselekcja w obliczeniach kwantowych?
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 efektywnie rozwiązywanych problemów staje się teraz postBQP = PP . Co …
4
Algorytm Grovera i jego związek z klasami złożoności?
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 danych, tak abykkkf(k)=1f(k)=1f(k)=1 Teraz jestem świadomy, że nie jest to problem desision, dlatego nasze …
1
Czy istnieje jakieś ogólne stwierdzenie dotyczące tego, jakie problemy można bardziej efektywnie przybliżyć za pomocą komputera kwantowego?
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 Blue: ogólną zasadą w teorii złożoności jest to, że jeśli …
1
Czy są jakieś zestawy szyfrowania, które mogą zostać złamane przez klasyczne komputery, ale nie komputery kwantowe?
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( modre)ac(modd)a^c\pmod d …
1
Oddzielanie NP od BQP względem wyroczni
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 zastosować? Intuicyjnie powinny istnieć istotne różnice między tymi, które służą do umieszczenia czegoś poza …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.