Was ist die Komplexitätsklasse für Quantensubroutinen, die beliebige Quantenzustände als Eingaben verwenden?

Die Komplexitätsklasse BQP entspricht polynomiellen Zeitquanten-Subroutinen, die klassische Eingaben aufnehmen und eine probabilistische klassische Ausgabe ausgeben. Der Quantenratschlag modifiziert diesen, um Kopien einiger vorbestimmter Quantenratschlagzustände einzuschließen, jedoch mit klassischen Eingaben wie üblich. Was ist die Komplexitätsklasse für Polynomialzeit-Quantensubroutinen, die willkürliche Quantenzustände als Eingaben annehmen, wobei nur eine Kopie ohne Klonen vorliegt und Quantenzustände als Ausgabe ausgespuckt werden?

Ich denke, was Sie wissen wollen, sind Quantenanaloga von Klassen von Funktionsproblemen. (Vielen Dank an Peter Shor für den Hinweis auf diese kurze Beschreibung in einem Kommentar.)

Ein abstrakter Prozess, der einen Quantenzustand fester Größe als Eingabe verwendet und einen Quantenzustand fester Größe als Ausgabe erzeugt, wird Quantenkanal genannt . In Ihrer Situation möchten wir die Eingangsgröße oder die Ausgangsgröße nicht festlegen, und daher betrachten wir natürlich eine Familie von Quantenkanälen als das Quantenanalog von Funktionen von klassischen Zeichenfolgen zu klassischen Zeichenfolgen.

Es ist eindeutig möglich, die Klasse von Familien von Quantenkanälen zu definieren, die von Familien effizienter Quantenkreise (mit geeigneten Begriffen von Effizienz, Gleichförmigkeit und Approximation) implementiert / approximiert werden können. Ich weiß nicht, ob diese Klasse einen Standardnamen hat (aber siehe Peter Shors Kommentar für einen Vorschlag).

In meinen Spekulationen werden Klassen von Quantenkanälen nicht oft untersucht, da einer der Gründe für die Berücksichtigung von Komplexitätsklassen darin besteht, die Potenzen verschiedener Rechenmodelle zu vergleichen, und Klassen von Quantenkanälen nicht zum Vergleichen von klassischen und Quantenrechenmodellen verwendet werden können. Es ist jedoch vollkommen in Ordnung, solche Klassen zu definieren und darüber zu sprechen, wenn irgendetwas Interessantes über sie bewiesen werden kann.

Vielleicht interessiert Sie der Begriff des Quantenorakels, den Aaronson und Kuperberg in arXiv eingeführt haben: quant-ph / 0604056 . Zitat aus ihrer Zeitung:

So wie ein klassisches Orakel eine Subroutine modelliert, auf die ein Algorithmus Black-Box-Zugriff hat, modelliert ein Quantenorakel eine Quanten-Subroutine, die Quanteneingaben entgegennehmen und Quantenausgaben erzeugen kann.

Dies beantwortet Ihre Frage nach einer Definition einer Komplexitätsklasse, die das von Ihnen beschriebene Modell darstellt, nicht direkt. Dennoch ist der Begriff des Quantenorakels in der Komplexitätstheorie relevant: In ihrer Arbeit verwenden Aaronson und Kuperberg ein Quantenorakel, um eine Trennung zwischen QMA und QCMA zu ermöglichen .

Ich denke, dass eine Komplexitätsklasse für Entscheidungsprobleme , die Quantenzustände als Eingabe verwendet, wahrscheinlich eine fragile Definition hat. Bei Versprechensproblemen ist die Definition entweder empfindlich gegenüber numerischen Entscheidungen, oder sie löst im Wesentlichen klassische Entscheidungs- / Versprechensprobleme, die in einer effizient decodierbaren Basis von Quantenzuständen codiert sind.

Die Antwort von Tsuyoshi beschreibt, was ich für die richtige Verallgemeinerung von Funktionsproblemen halte. Wenn Sie eine Verallgemeinerung von Entscheidungsproblemen wünschen, können Sie sich auf Senderfamilien spezialisieren$\Phi_n: \mathrm L(\mathcal H_2^{\otimes n}) \to \mathrm L(\mathcal H_2)$von n- Qubit-Zuständen zu einzelnen Qubit-Zuständen. Natürlich ist eine Quantenschaltung ein perfekter Kanal. Wenn wir von der Ausführung bestimmter Kanäle sprechen, die rechnerisch begrenzt sind, können wir auch nur von einheitlichen Quantenschaltungsfamilien sprechen (oder von einer einheitlichen Art der Implementierung einer CPTP-Karte). Für ein gutes Maß sollte die Schaltung mit einer Standardbasismessung enden, wenn wir die Semantik der Entscheidung mit begrenzter Wahrscheinlichkeit beibehalten möchten .

Angenommen, wir definieren eine "Quantensprache" $\mathcal L$aus Teilmengen der Dichteoperatoren auf n  Qubits bestehen, die sich über alle n erstrecken . Bei der Definition einer Quanteneingabe-Quantum-Polytime-Klasse mit beschränktem Fehler, QBQP , können wir nicht hoffen, eine klare Trennung zwischen Zuständen in der Sprache und Zuständen außerhalb der Sprache vorzunehmen , und gleichzeitig die Wahrscheinlichkeit der Akzeptanz für NO-Instanzen von diesen abzugrenzen von JA-Instanzen wie bei BQP und BPP ; irgendein Staat$\rho'$ das ist sehr nah an einem Staat $\rho \in \mathcal L$ (entweder mit hoher Überlappung oder geringer Spurweite) wird eine Akzeptanzwahrscheinlichkeit ergeben, die der von sehr nahe kommt $\rho$, ob oder nicht $\rho'$ ist in der $\mathcal L$. Es scheint mir also, dass eine Klasse QBQP nur "Quantenversprechungsprobleme" enthalten würde, bei denen versprochen wird, dass die Eingabe zu einer Klasse von JA-Instanzen oder von NEIN-Instanzen gehört, die nicht den Raum aller möglichen Zustände ausschöpfen. (Eine quantensprachliche Entscheidungsklasse mit unbegrenztem Fehler, eine Art QPQP- Klasse, darf nicht auf eine Versprechen-Problem-Formulierung beschränkt sein, um sinnvoll zu sein.)

Darüber hinaus scheint es wahrscheinlich, dass Sie die Erfolgswahrscheinlichkeit nicht erhöhen können, da das No-Cloning-Theorem Sie daran hindert, Kopien Ihres Eingabezustands anzufertigen. Jede Definition von QBQP, die eine konstante Erfolgswahrscheinlichkeit beinhaltet, die von 1/2 abweicht , würde wahrscheinlich entscheidend davon abhängen, wie hoch diese Wahrscheinlichkeit ist. Um dies zu vermeiden, würden wir in der Praxis wie bei den Funktionsklassen FBPP und FBQP wahrscheinlich QBQP so definieren , dass für einen Eingangszustand in$\mathcal L$in QBQP , jeder Staat in$\mathcal L$ergibt das Ergebnis 1 (von der Nachmessung) mit einer Wahrscheinlichkeit von 1 -  o (1), der eine Wahrscheinlichkeit , die mit Gewissheit näher als die Eingangsgröße wächst ist , - und in ähnlicher Weise von jedem Zustand die Wahrscheinlichkeit der Zurückweisung , daß die Entscheidungsroutine ist fähig abzulehnen sollte auch auf Null konvergieren.

Die Quantenversprechungsprobleme, die eine QBQP- Schaltung (für Eingänge der Größe n ) unterscheiden könnte, wären dann

• Für JA-Instanzen: Eine Menge von reinen Zuständen in einem Unterraum von $\mathcal H_2^{\otimes n}$und alle durch das Versprechen erlaubten Gemische;
• Für NO-Fälle Gemische von reinen Zuständen, die orthogonal zu diesem Unterraum sind (oder zumindest alle orthokomplementären Zustände, die das Versprechen zulässt).

Über diesen Klassen von Staaten kann sich ein Miasma von nahe gelegenen Staaten befinden, die nach dem Versprechen zulässig sind und sehr nahe an Staaten liegen, die zu einer der beiden obigen Klassen gehören; aber asymptotisch würden die durch das Versprechen erfüllten Klassen von Staaten zu diesen beiden Klassen konvergieren, wenn n wächst. Die an der Entscheidungsprozedur beteiligte Schaltung würde dann im wesentlichen einer Schaltung entsprechen, die eine Basis von reinen Zuständen abbildet$\mathcal L$ - zusammen mit einer Basis für die "orthokomplementäre Quantensprache" (sozusagen) $\mathcal L^\bot$- zur Standardbasis und entscheidet, welche dieser Berechnungsbasiszustände Zuständen in der Quantensprache entsprechen. Kurz gesagt, es würde ein klassisches Entscheidungs- oder Versprechungsproblem lösen, das in Quantenzuständen codiert ist, wobei der Fehler gegen Null konvergiert.

Correct me if I am wrong, but it seems to me that you are interested in the class BQP/qpoly. Definition from Complexity Zoo: "The class of problems solvable by a BQP machine that receives a quantum state ψn as advice, which depends only on the input length n."

If it is that one, in the website you can find relationships of this class to other complexity classes. If it is not, this website also contains information about what happens to BQP when you use different types of advice.

There is also a relatively recent work about the "characterisation of quantum advice" where you can find the following hierarchy:

Ich weiß nicht, wie viele dieser Informationen bereits in Complexity Zoo enthalten sind. Wenn Sie sich für das Papier interessieren, haben die Autoren auch einen Vortrag darüber gehalten.

Edit Ich frage mich, ob mit "willkürlich" ein Zustand gemeint ist, der durch einen allgemeineren Quantenprozess erzeugt wird, bei dem die "auf rechnerischer Basis wirkende einheitliche Evolution" wie die dissipative Evolution ist. In diesem speziellen letzteren Fall verfügen Sie nicht über mehr Rechenleistung als BQP, wie in diesem Artikel gezeigt .

Hier einige Referenzen zu Quantensprachen, dh Entscheidungsproblemen bei Quanteneingaben. Es gibt wahrscheinlich noch viel mehr.

1. Quantum NP und eine Quantenhierarchie - Tomoyuki Yamakami
2. Über die Komplexität von Quantensprachen - Elham Kashefi, Carolina Moura Alves
3. Ein effizienter Test für Produktzustände mit Anwendungen für Quanten-Merlin-Arthur-Spiele - Aram Harrow, Ashley Montanaro, DOI: 10.1109 / FOCS.2010.66, Abstract: arxiv.org/abs/1001.0017v3