Obliczenia kwantowe i zagadnienia obliczeniowe związane z mechaniką kwantową
Jest to „pytanie historyczne” bardziej niż pytanie badawcze, ale czy klasyczne sprowadzenie do ustalania porządku w algorytmie Shora dla faktoryzacji zostało początkowo odkryte przez Petera Shora, czy też było wcześniej znane? Czy istnieje artykuł opisujący redukcję, która poprzedza Shora, czy jest...
W świetle ogłoszenia pierwszego na świecie programowalnego układu kwantowego , zastanawiałem się, jakie byłoby oprogramowanie dla komputera wykorzystującego splątanie kwantowe. Jeden z pierwszych programów, które napisałem, był podobny for i = 1 to 10 print i next i Czy ktoś może podać przykład...
W swoim słynnym artykule „Conjugate Coding” (napisanym około 1970 r.) Stephen Wiesner zaproponował schemat pieniądza kwantowego, który jest bezwarunkowo niemożliwy do sfałszowania, zakładając, że bank emitujący ma dostęp do ogromnej tabeli liczb losowych i że banknoty można przynieść z powrotem do...
Wydaje się jasne, że na wiele podpól teoretycznej informatyki istotny wpływ wywarły wyniki fizyki teoretycznej. Oto dwa przykłady Obliczenia kwantowe Wyniki mechaniki statystycznej stosowane w analizie złożoności / algorytmach heurystycznych. Więc moje pytanie brzmi: czy brakuje mi jakichś...
Centralnym problemem teorii złożoności jest zapewne vs .P.PPN.P.NPNP Ponieważ natura jest kwantowa, bardziej naturalne wydaje się rozważenie klas (tj. Problemów decyzyjnych rozwiązanych przez komputer kwantowy w czasie wielomianowym, z prawdopodobieństwem błędu co najwyżej 1/3 dla wszystkich...
Jako amator TCS czytam popularny materiał wprowadzający na temat komputerów kwantowych. Oto kilka podstawowych elementów informacji, których nauczyłem się do tej pory: Komputery kwantowe nie są znane z rozwiązywania problemów NP-zupełnych w czasie wielomianowym. „Magia kwantowa nie wystarczy”...
Od czasu do czasu słyszałem, jak ludzie mówią o algorytmach kwantowych oraz o stanach i możliwości rozważenia wielu możliwości naraz, ale nigdy nie udało mi się przekonać kogoś do wyjaśnienia stojącego za tym modelu obliczeniowego. Żeby było jasne, nie pytam o to, jak fizycznie zbudowane są...
Nie wydaje się, żeby to było znane - ale czy są jakieś interesujące dolne granice złożoności mnożenia macierzy w modelu obliczeń kwantowych? Czy mamy intuicję, że możemy pokonać złożoność algorytmu Coppersmith-Winograd za pomocą komputerów
Załóżmy, że P = NP jest prawdziwe. Czy byłoby zatem jakieś praktyczne zastosowanie do budowy komputera kwantowego, takie jak szybsze rozwiązywanie określonych problemów, czy też takie ulepszenie byłoby nieistotne w związku z faktem, że P = NP jest prawdziwe? Jak scharakteryzowałbyś poprawę...
Klasyczne algorytmy mogą rozwiązać 3-SAT w czasie (losowo) lub (deterministycznie). (Odnośnik: najlepsze górne granice na SAT )1,3303 n1,3071n1.3071n1.3071^n1,3303n1.3303n1.3303^n Dla porównania, użycie algorytmu Grovera na komputerze kwantowym i zapewniło rozwiązanie w losowaniu losowym . (Może...
Mam mały problem z pełnym zrozumieniem ostatnich kroków algorytmu faktoringu Shora. Biorąc pod uwagę którą chcemy uwzględnić, wybieramy losowy x, który ma porządek r .NNNxxxrrr Pierwszy krok obejmuje skonfigurowanie rejestrów i zastosowanie operatora Hadamard. W drugim kroku stosuje się operator...
Ogólnie uważa się za mało prawdopodobne, aby komputery kwantowe były w stanie skutecznie rozwiązywać problemy związane z NP. W klasycznym przypadku jednym podejściem do rozwiązania takich problemów jest zastosowanie algorytmów aproksymacyjnych. Czy były jakieś badania algorytmów aproksymacyjnych...
Peter Shor pokazał, że dwa z najważniejszych problemów pośrednich NP, faktoring i dyskretny log, są w BQP. Natomiast najbardziej znany algorytm kwantowy dla SAT (poszukiwanie Grovera) zapewnia jedynie kwadratową poprawę w porównaniu z klasycznym algorytmem, co sugeruje, że problemy z całkowitą NP...
W modelu czarnej skrzynki problem określania wydajności maszyny BPP na wejściu x jest przybliżonym problemem zliczania określania E r M ( x , r ) z błędem addytywnym 1/3 (powiedzmy) .M(x,r)M(x,r)M(x,r)xxxErM(x,r)ErM(x,r)E_r M(x,r) Czy istnieje podobny problem dla BQP? Ten komentarz Kena Regana...
W złożoności obliczeniowej istnieje istotne rozróżnienie między obliczeniami monotonicznymi i ogólnymi, a słynne twierdzenie Razborova stwierdza, że 3-SAT, a nawet DOPASOWANIE nie są wielomianowe w monotonicznym modelu obwodów boolowskich. Moje pytanie jest proste: czy istnieje analog kwantowy...
Interesują mnie przykłady problemów, w których twierdzenie, które pozornie nie ma nic wspólnego z mechaniką / informacją kwantową (np. Mówi coś o obiektach czysto klasycznych), może jednak zostać udowodnione za pomocą narzędzi kwantowych. Badanie Kwantowe dowody dla klasycznych twierdzeń (A....
Splątanie jest często utrzymywane jako kluczowy składnik, który sprawia, że algorytmy kwantowe są dobrze ... kwantowe, i można to prześledzić do stanów Bella, które niszczą ideę fizyki kwantowej jako modelu probabilistycznego w stanie ukrytym. W teorii informacji kwantowej (z mojego raczej...
Jest dobrze ustalone, że istnieje próg szumowy dla obliczeń kwantowych, taki że poniżej tego progu obliczenia mogą być zakodowane w taki sposób, że dają poprawny wynik z ograniczonym prawdopodobieństwem (z co najwyżej wielomianowym narzutem obliczeniowym). Próg ten zależy od zastosowanego kodowania...
W „Wymaganiu do obliczeń kwantowych” Bartlett i Sanders podsumowują niektóre ze znanych wyników obliczeń ciągłych zmiennych kwantowych w poniższej tabeli: MOJE pytanie jest trzykrotne: Czy dziewięć lat później można wypełnić ostatnią komórkę? Jeśli kolumna zostanie dodana z tytułem „Universal...
Próbuję zrozumieć związek między izomorfizmem grafu a problemem ukrytej podgrupy. Czy jest na to dobre