normalne zachowanie maszyn Turinga

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.$\ell_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 zachowuje$s$$\ell_1$$\parallel s\parallel_1=1$$P$$\parallel Ps\parallel_1=1$$P$ -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 .$\ell_1$$t$$P^ts$$P$$s$$P$$\ell_1$$M^{\ell_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 .$s$$\parallel s\parallel_2=1$$P$$\ell_2$$P^ts$$t$$\parallel P^ts\parallel_2=1$$\ell_2$$M^{\ell_2}$

Niech na ogół -norm maszynie konserwującego oznaczamy przez M £ -l p .$\ell_p$$M^{\ell_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 ?$\ell_p$$p$$p$$q$$q>p$$L$$M^{\ell_q}$$M^{\ell_q}$$L$$M^{\ell_p}$$L$$NP \subseteq BQP$

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

(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=\infty$

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

$p \not\in \{1,2\}$$\ell_p$$\left| \psi_i \right|^p$

$\ell_p$$\ell_1$$\ell_2$$\Omega(N^{1/p})$$\ell_\infty$$\ell_p$$\ell_q$$1/p+1/q=1$$\ell_p$$p$