Pytania otagowane jako quantum-computing

Obliczenia kwantowe i zagadnienia obliczeniowe związane z mechaniką kwantową

7
Jak wyglądałby bardzo prosty program kwantowy?
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 kodu o porównywalnej prostocie, który wykorzystywałby kwantowe …
3
Rygorystyczny dowód bezpieczeństwa dla kwantowych pieniędzy Wiesnera?
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 banku w celu weryfikacji. W schemacie Wiesner, każdy banknot …
16
Wyniki fizyki w TCS?
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ś głównych obszarów? Moja motywacja jest bardzo prosta: jestem fizykiem teoretycznym, który przybył …
2
Konsekwencje
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” (Bennett i in. 1997): jeśli odrzucisz strukturę problemu i po prostu weźmiesz …
1
vs?
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 instancji) i (ekwiwalent kwantowy z ) zamiast.B Q PBQPBQPQ MZAQMAQMAN.P.NPNP Moje pytania: 1) Czy …
11
Co to jest kwantowy model obliczeniowy?
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ą komputery kwantowe, ale raczej, …
2
Czy jakieś algorytmy kwantowe poprawiają klasyczne SAT?
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 to nadal wymagać pewnej wiedzy o tym, ile rozwiązań może istnieć, ale nie jestem pewien, jak …
4
Gdyby P = NP były prawdziwe, czy komputery kwantowe byłyby przydatne?
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ę wydajności, która nastąpiłaby, gdyby komputer kwantowy mógł zostać …
3
Pojęcie monotonicznych obwodów kwantowych
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 dla obwodów monotonicznych (lub więcej niż jednego)? Czy istnieje kwantowe twierdzenie Razborowa?
5
Dowody kwantowe klasycznych twierdzeń
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. Drucker, R. Wolf) podaje ładną listę takich problemów, ale na …
1
Pomoc algorytmu faktoringu Shora
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 liniowy. Trzeci krok jest mierzony drugim rejestrem (uważam, że ten …
2
Problemy pośrednie NP z efektywnymi rozwiązaniami kwantowymi
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 są wciąż trudne do rozwiązania na komputerach kwantowych. …
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.