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.
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 zachowuje -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 .
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 .
Niech na ogół -norm maszynie konserwującego oznaczamy przez M £ -l p .
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 ?
(2) Co z ? Tutaj maksymalna wartość składników wektora stanu wynosi 1.
(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 ?
źródło
Odpowiedzi:
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
źródło
źródło