Wie allgemein bekannt ist, kann PARITÄT nicht in Schaltkreisen mit konstanter Tiefe in Polygröße durchgeführt werden, und tatsächlich erfordern Schaltkreise mit konstanter Tiefe die EXP-Anzahl von Gattern.
Was ist mit QUANTUM-Schaltungen?
a) Kann PARITÄT mit einer Quantenschaltung durchgeführt werden, die eine konstante Tiefe und Polyanzahl von Gattern hat?
b) Ist meine Frage überhaupt sinnvoll?
cc.complexity-theory
quantum-computing
circuit-complexity
Bill GASARCH
quelle
quelle
Antworten:
Die Frage ist sinnvoll und die kurze Antwort lautet, dass es sich um ein offenes Problem handelt.
Hier ist die lange Antwort: Je nachdem, wie Sie unbegrenzte Quantenschaltungen mit konstanter Tiefe definieren, erhalten Sie möglicherweise unterschiedliche Klassen. QAC 0 ist normalerweise als unbeschränktes Fanin-Toffoli-Gate und Single-Qubit-Gate definiert. QAC 0 wf ist die Klasse, in der wir auch ein "Fanout" -Gatter zulassen, das ein Eingangsbit auf viele Ausgänge kopiert. (Es implementiert | a> | 0> ... | 0> -> | a> | a> ... | a>) Diese Klasse ist sehr mächtig, da sie neben PARITY und AC 0 auch ACC 0 und enthält TC 0 .
Die naheliegende Frage ist also, ob PARITY in QAC 0 enthalten ist , und dies ist ein offenes Problem. Es ist äquivalent zu fragen, ob QAC 0 = QAC 0 wf ist . Ich denke, der Glaube ist, dass PARITÄT nicht in QAC 0 ist . Weitere Informationen finden Sie in der Übersicht Quantenschaltungen mit geringer Tiefe von Bera, Green und Homer.
quelle
Überraschenderweise ist die Anzahl der zusätzlichen Qubits (ancilla) von Bedeutung. Derzeit ist bekannt, dass sich PARITY nicht in QAC_0 mit begrenzten Ancillae befindet. Quantenuntergrenzen für Fanout geben einen Beweis für Schaltkreise, die höchstens linear viele Ancillas und Doi verwenden: 10.1016 / j.ipl.2011.05.002 gibt einen weiteren Beweis für Schaltkreise, die keine Ancillas verwenden.
quelle