Lesen auf

Was soll ich lesen, um dieses Problem zu verstehen?

Die Leistung von Quantenschaltungen mit geringer Tiefe. Ist ? Mit anderen Worten, kann der "Quanten" -Teil eines beliebigen Quantenalgorithmus auf Polylog (n) -Tiefe komprimiert werden, vorausgesetzt, wir sind bereit, eine klassische Nachbearbeitung in Polynomzeit durchzuführen? (Es ist bekannt, dass dies für Shors Algorithmus zutrifft.) In diesem Fall wäre der Bau eines Allzweck-Quantencomputers viel einfacher als allgemein angenommen! Nebenbei bemerkt, ist es nicht schwer , eine Trennung zwischen Oracle zu geben B Q P und B P P B Q N $BQP = BPP^{BQNC}$$BQP$$BPP^{BQNC}$, aber die Frage ist, ob es eine konkrete Funktion gibt, die ein solches Orakel "instanziiert". - Scott Aaronson http://www.scottaaronson.com/writings/qchallenge.html

Dies vermutete R. Jozsa in Abschnitt 8 von arXiv: quant-ph / 0508124 . Wenn Sie bereits mit Quantencomputing und Quantenkomplexitätstheorie vertraut sind, lesen Sie zunächst diesen Abschnitt.

Eine wichtige Lesart ist arXiv: quant-ph / 0006004 , wobei Cleve und Watrous zeigen, dass Shors Algorithmus in dieser Klasse liegt.