Jaka jest klasa złożoności podprogramów kwantowych przyjmujących dowolne stany kwantowe jako dane wejściowe?

Klasa złożoności BQP odpowiada podprogramom kwantowym w czasie wielomianowym, przyjmującym klasyczne dane wejściowe i wyrzucającym probabilistyczny sygnał klasyczny. Porada kwantowa modyfikuje to, aby uwzględnić kopie niektórych z góry określonych stanów porady kwantowej, ale jak zwykle z klasycznymi danymi wejściowymi. Jaka jest klasa złożoności podprogramów kwantowych czasu wielomianowego przyjmujących dowolne stany kwantowe jako dane wejściowe, z jedną kopią tylko z powodu braku klonowania i wypluwających stany kwantowe jako wynik?

Myślę, że chcesz wiedzieć o kwantowych analogach klas problemów funkcji. (Podziękowania dla Petera Shora za wskazanie tego zwięzłego opisu w komentarzu.)

Abstrakcyjny proces, który przyjmuje stan kwantowy o ustalonym rozmiarze jako dane wejściowe i wytwarza stan kwantowy o ustalonym rozmiarze jako wynik, nazywany jest kanałem kwantowym . W twojej sytuacji nie chcemy ustalać wielkości wejściowej ani wyjściowej, dlatego naturalnie uważamy rodzinę kanałów kwantowych za kwantowy analog funkcji od klasycznych łańcuchów do klasycznych łańcuchów.

Jest oczywiście możliwe zdefiniowanie klasy rodzin kanałów kwantowych, które mogą być implementowane / aproksymowane przez rodziny efektywnych obwodów kwantowych (z odpowiednimi pojęciami wydajności, jednorodności i aproksymacji). Nie wiem, czy ta klasa ma jakąkolwiek standardową nazwę (zobacz sugestię Petera Shora).

W mojej spekulacji klasy kanałów kwantowych nie są często badane, ponieważ jednym z powodów do rozważenia klas złożoności jest porównanie mocy różnych modeli obliczeniowych, a klas kanałów kwantowych nie można użyć do porównania klasycznych i kwantowych modeli obliczeniowych. Jednak doskonale jest definiować i rozmawiać o takich klasach, jeśli można coś udowodnić na ich temat.

Być może zainteresuje Cię pojęcie kwantowej wyroczni wprowadzone przez Aaronsona i Kuperberga w arXiv: quant-ph / 0604056 . Cytując z pracy:

Tak jak klasyczna wyrocznia modeluje podprogram, do którego algorytm ma dostęp do czarnej skrzynki, tak kwantowa wyrocznia modeluje kwantowy podprogram, który może przyjmować dane kwantowe i wytwarzać dane kwantowe.

To nie odpowiada bezpośrednio na twoje pytanie dotyczące definicji klasy złożoności, która reprezentuje opisany model. Jednak pojęcie kwantowej wyroczni ma znaczenie w teorii złożoności: w swojej pracy Aaronson i Kuperberg używają kwantowej wyroczni, aby rozdzielić QMA i QCMA .

Myślę, że klasa złożoności problemów decyzyjnych , przyjmująca stany kwantowe jako dane wejściowe, może mieć kruchą definicję. W przypadku problemów z obietnicą albo definicja będzie wrażliwa na wybory numeryczne, albo zasadniczo rozwiąże klasyczne problemy związane z decyzją / obietnicą zakodowane w pewnej skutecznie dekodowalnej podstawie stanów kwantowych.

$\Phi_n: \mathrm L(\mathcal H_2^{\otimes n}) \to \mathrm L(\mathcal H_2)$-qubit stany do pojedynczych stanów qubit. Oczywiście obwód kwantowy jest kanałem doskonale dobrym; jeśli mamy mówić o wykonywaniu określonych kanałów, które są ograniczone obliczeniowo, możemy równie dobrze mówić o jednolitych rodzinach obwodów kwantowych (lub, w tym przypadku, o dowolnym jednolitym sposobie implementacji mapy CPTP). Dla pewności obwód powinien zakończyć się standardowym pomiarem podstawowym, jeśli chcemy zachować semantykę decydowania o czymś z ograniczonym prawdopodobieństwem.

$\mathcal L$$\rho'$$\rho \in \mathcal L$$\rho$$\rho'$$\mathcal L$

$\mathcal L$$\mathcal L$(1), to jest prawdopodobieństwo, które jest bliższe pewności wraz ze wzrostem wielkości wejściowej - i podobnie prawdopodobieństwo odrzucenia dowolnego stanu, który procedura decyzyjna może odrzucić, powinna również zbiegać się do zera.

Problemy kwantowej obietnicy, które obwód QBQP (dla wejść o rozmiarze n ) byłby w stanie odróżnić, byłyby wtedy

• $\mathcal H_2^{\otimes n}$
• W przypadku NIE, mieszanina stanów czystych, które są ortogonalne do tej podprzestrzeni (lub przynajmniej wszystkie stany ortokomplementarne dozwolone przez obietnicę).

$\mathcal L$$\mathcal L^\bot$ problem decyzji lub obietnicy, zakodowany w stanach kwantowych, z błędem zbliżającym się do zera.

Popraw mnie, jeśli się mylę, ale wydaje mi się, że jesteś zainteresowany klasą BQP / qpoly . Definicja ze złożoności zoo: „Klasa problemów rozwiązanych przez maszynę BQP, która otrzymuje stan kwantowy asn jako wskazówkę, która zależy tylko od długości wejściowej n.”

Jeśli tak jest, na stronie internetowej można znaleźć powiązania tej klasy z innymi klasami złożoności. Jeśli tak nie jest, ta strona internetowa zawiera również informacje o tym, co dzieje się z BQP, gdy korzystasz z różnych rodzajów porad.

Istnieje również stosunkowo nowa praca na temat „ charakteryzacji porad kwantowych ”, w której można znaleźć następującą hierarchię:

Nie wiem, ile z tych informacji jest już w Zoo Złożoności. Jeśli jesteś zainteresowany tym artykułem, autorzy wygłosili również o nim rozmowę .

Edytuj Zastanawiam się, czy przez „arbitralny” rozumiesz stan generowany przez bardziej ogólny proces kwantowy, że „ewolucja jednostkowa działająca na podstawie obliczeniowych stanów” przypomina ewolucję rozpraszającą. W tym konkretnym ostatnim przypadku nie masz większej mocy obliczeniowej niż BQP, jak pokazano w tym artykule .

Oto kilka odniesień do języków kwantowych, tj. Problemy decyzyjne z wejściami kwantowymi. Prawdopodobnie jest ich o wiele więcej.

1. Quantum NP i Quantum Hierarchy - Tomoyuki Yamakami
2. O złożoności języków kwantowych - Elham Kashefi, Carolina Moura Alves
3. Wydajny test stanów produktu, z zastosowaniami do kwantowych gier Merlin-Arthur -Aram Harrow, Ashley Montanaro, DOI: 10.1109 / FOCS.2010.66, streszczenie: arxiv.org/abs/1001.0017v3