normalne zachowanie maszyn Turinga

20

Czytając kilka ostatnich wątków na temat obliczeń kwantowych ( tutaj , tutaj i tutaj ), pamiętam interesujące pytanie o moc jakiegoś rodzaju maszyny do zachowania normalnego zachowania.p

Dla osób pracujących w teorii złożoności, które dążą do złożoności kwantowej, doskonałym tekstem wprowadzającym jest praca Fortnowa, której link zamieścił tutaj Joshua Grochow . W tym artykule kwantowa maszyna Turinga jest przedstawiona jako uogólniona probabilistyczna maszyna Turinga. Zasadniczo urządzenie ma charakter probabilistyczny stan znormalizowane pod 1 -norm tj s 1 = 1 . Ewolucję czasową maszyny podaje się przez zastosowanie macierzy stochastycznej P, tak że P s 1 = 1 , tj. P zachowujes1s1=1PPs1=1P -normalny. Zatem stanem w czasie t jest P t s (notacja może nie być precyzyjna, ponieważ lewe lub prawe zwielokrotnienie P zależy od tego, czy s jest wektorem wiersza lub kolumny, czy wiersze lub kolumny P są podprzestrzenami zachowującymi normę). W tym sensie probabilistyczna maszyna Turinga jestmaszyną konserwującą normę1 , oznaczoną M 1 .1tPtsPsP1M1

Następnie kwantowa maszyna Turinga może być postrzegana jako posiadająca stan ze s 2 = 1 i macierzą jednostkową P (która zachowuje 2- normalne), tak że P t s jest stanem w czasie t, gdzie P t s 2 = 1 . To 2 -norm Urządzenie konserwujące oznaczona M £ -l 2 .ss2=1P2PtstPts2=12M2

Niech na ogół -norm maszynie konserwującego oznaczamy przez M £ -l p .pMp

Więc moje pytania to:

(1) Jaka jest moc -norm konserwującego maszyny do skończonej p ? Bardziej formalnie, możemy udowodnić, że dla dowolnego p i q , jeśli q > p to istnieje język L i maszyna M £ -l q takie, że M q skutecznie decyduje L i nie ma maszyna M p , które skutecznie decyduje L . Na przykład może to być uogólnienie pytania, czy N P B Q P ?pppqq>pLMqMqLMpLNPBQP

(2) Co z ? Tutaj maksymalna wartość składników wektora stanu wynosi 1.p=

(3) Te pytania wykraczają poza jednolitość, więc nie oczekuje się, że zgadzają się z mechaniką kwantową. Zasadniczo, co dzieje się z obliczeniami, jeśli rozluźnisz ograniczenie jednolitości operacji? Trwają prace nad dopuszczaniem operatorów nieliniowych (patrz Aaronson 2005 ).

(4) Być może najważniejsze, czy jest uniwersalne? Myślę, że jest to jasne, ponieważ w niektórych przypadkach jest uniwersalne. Ale co dzieje się z uniwersalnością, gdy ?p=

Marcos Villagra
źródło
4
Bardzo interesujący artykuł Scotta Aaronsona: Czy mechanika kwantowa jest wyspą w teorii? scottaaronson.com/papers/island.pdf
Tsuyoshi Ito
1
Tsuyoshi, czy mógłbyś zamienić to w odpowiedź? Wygląda na to, że Scott bezpośrednio odpowiada na pytanie Marcosa. Spójrz na Propozycję 5 w gazecie ...
Ryan Williams
Nie przeczytałem go jeszcze całkowicie, ale wydaje się, że odpowiada na pytania (1) i (3) powyżej.
Marcos Villagra,
@Ryan: Gotowe. Następnym razem dodaj znak przed nazwą, aby pojawiła się na stronie „odpowiedzi”.
Tsuyoshi Ito,

Odpowiedzi:

21

To nie jest pełna odpowiedź na pytania, ale jest zbyt długo, aby pisać jako komentarz. Rozszerza mój poprzedni komentarz.

Pytanie „Co stanie się z obliczeniami, jeśli aksjomaty mechaniki kwantowej zostaną nieco zmodyfikowane?” Zostało szczegółowo omówione w zabawnym artykule [Aar04] Scotta Aaronsona. Uważam, że zasadniczo na odpowiedzi na pytania w pierwszej połowie sekcji 2 [Aar04].

Aaronson pokazuje, że jeśli p> 0 i p ≠ 2, to macierz, która zachowuje normę p dla wszystkich wektorów, jest koniecznie uogólnioną macierzą permutacji (iloczyn macierzy permutacji i macierzy diagonalnej). Stwierdza, że ​​to samo dotyczy przypadku p = ∞. Wszystkie te dotyczą zarówno over, jak i ℂ. Należy zauważyć, że obejmuje to przypadek p = 1: macierze stochastyczne zachowują 1-normę dla wektorów nieujemnych, ale nie dla wszystkich wektorów ogólnie.

Sądzę, że probabilistyczna maszyna Turinga uogólniona jak w [For00] ma uogólnioną macierz permutacji jako swoją globalną macierz przejściową tylko wtedy, gdy jest deterministyczną maszyną Turinga, ale nie mam pod ręką dowodu.

Aaronson omawia także kilka innych modyfikacji aksjomatów mechaniki kwantowej w artykule. Na przykład, jeśli zmienimy regułę pomiaru (zamiast zestawu dozwolonych bramek), aby wynik x wystąpił z prawdopodobieństwem | α x | p / ∑ y | α y | p , gdzie α y jest amplitudą | y⟩, wówczas ten „komputer kwantowy” może rozwiązać wszelkie problemy w PP (w tym problemy NP-zupełne) w czasie wielomianowym, chyba że p = 2 (Twierdzenie 5).

Bibliografia

[Aar04] Scott Aaronson. Czy mechanika kwantowa jest wyspą w przestrzeni teorii? W materiałach z konferencji Växjö „Teoria kwantowa: ponowne rozważenie podstaw”, 2004. arXiv: quant-ph / 0401062 v2.

[For00] Lance Fortnow. Pogląd jednego z teoretyków złożoności na temat obliczeń kwantowych. In Computing: Australasian Theory Symposium (CATS 2000), s. 58–72, styczeń 2000. http://dx.doi.org/10.1016/S1571-0661(05)80330-5

Tsuyoshi Ito
źródło
1
Dla mnie jest to najlepsze uzasadnienie, dlaczego amplituda jest podniesiona do kwadratu, a nie 4-ta lub wyższa moc. Chciałbym wiedzieć o tego rodzaju wynikach, kiedy uczyłem się QM, a wybór kwadratu wydawał się tak arbitralny.
Artem Kaznatcheev
0

p{1,2}p|ψi|p

p12Ω(N1/p)pq1/p+1/q=1pp

Dan Stahlke
źródło