Pytania otagowane jako speedup

W przypadku pytań dotyczących: porównania wydajności algorytmu kwantowego z klasycznym algorytmem (lub zestawem klasycznych algorytmów) niezależnym od urządzeń; lub stosunek czasu do rozwiązania urządzenia kwantowego z określonym algorytmem do klasycznego urządzenia z określonym algorytmem.

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 …
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, …
2
Czy od czasu Grovera i Shora nastąpił naprawdę przełomowy postęp w dziedzinie algorytmów kwantowych?
(Przepraszam za nieco amatorskie pytanie) Studiowałem informatykę kwantową w latach 2004-2007, ale od tego czasu straciłem orientację w tej dziedzinie. W tamtym czasie było dużo szumu i dyskusji na temat QC potencjalnie rozwiązującej wszelkiego rodzaju problemy, przewyższającej klasyczne komputery, ale w praktyce były tylko dwa teoretyczne przełomy: Algorytm Shora, który …
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, …
2
Kiedy dowiemy się, że osiągnięta została supremacja kwantowa?
Termin „supremacja kwantowa” - w moim rozumieniu - oznacza, że ​​można tworzyć i uruchamiać algorytmy do rozwiązywania problemów na komputerach kwantowych, których nie da się rozwiązać w realistycznych czasach na komputerach binarnych. Jest to jednak dość niejasna definicja - co w tym kontekście można by uznać za „realistyczny czas”? Czy …
3
Co sprawia, że ​​komputery kwantowe są tak dobre w obliczaniu głównych czynników?
Jednym z powszechnych twierdzeń na temat komputerów kwantowych jest ich zdolność do „łamania” konwencjonalnej kryptografii. Wynika to z faktu, że konwencjonalna kryptografia opiera się na czynnikach głównych, co jest kosztem obliczeniowym dla konwencjonalnych komputerów do obliczenia, ale który jest rzekomo trywialnym problemem dla komputera kwantowego. Jaka właściwość komputerów kwantowych czyni …
4
Dlaczego dyskretna transformata Fouriera może być skutecznie wdrażana jako obwód kwantowy?
Jest to dobrze znany wynik, że dyskretna transformata Fouriera (DFT) o liczbach N=2nN=2nN=2^n ma złożoność O(n2n)O(n2n)\mathcal O(n2^n) z najlepiej znanym algorytmem , podczas gdy wykonuje transformatę Fouriera amplitud stanu kwantowego, z klasycznym Algorytm QFT , wymaga tylko elementarnych bramek O(n2)O(n2)\mathcal O(n^2) . Czy jest jakiś znany powód, dla którego tak …
1
W jaki sposób górna skala destylacji stanu magicznego różni się od zalet kwantowych?
Interesuje mnie model obliczeń kwantowych metodą iniekcji stanu magicznego, czyli tam, gdzie mamy dostęp do bram Clifforda, tanie dostawy kubitów ancylowych w oparciu o obliczenia oraz kilka kosztownych do destylacji stanów magicznych (zwykle te które implementują bramki S, T). Przekonałem się, że najlepsze skalowanie jest logarytmiczne w dokładności , w …
1
Jak długo trwa wyżarzanie kwantowe, aby znaleźć rozwiązanie danego problemu?
Wyżarzanie kwantowe jest protokołem optymalizacji, który dzięki tunelowaniu kwantowemu pozwala w danych okolicznościach zmaksymalizować / zminimalizować daną funkcję bardziej skutecznie niż klasyczne algorytmy optymalizacji. Kluczowym punktem wyżarzania kwantowego jest adiabatyczność algorytmu, która jest wymagana, aby stan pozostawał w stanie podstawowym zależnego od czasu hamiltonianu. Jest to jednak również problem, ponieważ …
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ż …
1
Czym dokładnie jest „losowe próbkowanie obwodu”?
Wiele osób sugerowało stosowanie „losowego próbkowania obwodów” w celu wykazania supremacji kwantowej. Ale jaka jest dokładna definicja problemu „losowego próbkowania obwodu”? Widziałem takie stwierdzenia, jak: „zadaniem jest pobranie losowego (wydajnego) obwodu kwantowego określonej postaci i wygenerowanie próbek z jego rozkładu wyjściowego”. Ale nie jest dla mnie jasne, co dokładnie oznaczają …
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 …
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.