Geht es bei BQP nur um Zeit? Ist das sinnvoll?

Die Komplexitätsklasse BQP (Quantenpolynomzeit mit begrenztem Fehler) scheint nur unter Berücksichtigung des Zeitfaktors definiert zu sein. Ist das immer sinnvoll? Gibt es Algorithmen, bei denen die Rechenzeit polynomiell mit der Eingabegröße skaliert, andere Ressourcen wie der Speicher jedoch exponentiell skaliert werden?

BQP wird unter Berücksichtigung der Schaltungsgröße definiert , dh der Gesamtzahl der Gates. Dies bedeutet, dass es beinhaltet:

• Anzahl der Qubits - weil wir alle Qubits ignorieren können, auf die kein Gate einwirkt. Dies ist in Bezug auf die Eingabegröße polynomiell begrenzt und häufig ein bescheidenes Polynom (z. B. beinhaltet Shors Algorithmus nur eine Anzahl von Qubits, was ein konstanter Faktor multipliziert mit der Eingabegröße ist).
• Schaltungstiefe (oder 'Zeit') - weil die Berechnung am längsten dauern kann, wenn wir ein Gate nach dem anderen ausführen, ohne irgendwelche Operationen parallel auszuführen.
• Kommunikation mit Steuerungssystemen - da die durchgeführten Gates aus einem endlichen Gatesatz stammen und selbst wenn wir Zwischenmessungen zulassen, der Kommunikationsaufwand, der erforderlich ist, um das Ergebnis der Messung anzuzeigen, und der Rechenaufwand, der erforderlich ist, um zu bestimmen, was als nächstes getan wird ist normalerweise eine Konstante für jede Operation.
• Interaktionen zwischen Quantensystemen - selbst wenn wir eine Architektur betrachten, die keine All-to-All-Interaktionen oder ähnliches aufweist, können wir diese Konnektivität simulieren, indem wir explizite SWAP-Operationen ausführen, die selbst in eine konstante Anzahl von zwei zerlegt werden können -Quit-Operationen. Dies kann zu einem spürbaren Polynom-Overhead führen, der sich auf die Praktikabilität eines Algorithmus für eine bestimmte Architektur auswirkt, jedoch keinen exponentiellen Arbeitsaufwand verbirgt.
• Energie - wieder, weil die Schaltkreise in eine endliche Gate-Menge zerlegt sind, gibt es keinen offensichtlichen Weg, eine scheinbare Beschleunigung zu erreichen, indem man "die Gates schneller macht" oder indem man Arbeit in einer exotischen Interaktion versteckt, wenn unsere Grenze in Bezug auf ist die Anzahl der Operationen, die von einem ziemlich einfachen Satz von Operationen ausgeführt werden. Diese Überlegung ist beim adiabatischen Quantencomputing wichtiger: Wir können nicht versuchen, kleine Lücken zu vermeiden, indem wir die gesamte Energielandschaft so weit verstärken, wie wir möchten - was bedeutet, dass wir stattdessen länger brauchen müssen, um die Berechnung durchzuführen, die im Schaltungsbild entspricht eine Schaltung mit mehr Toren.

Wenn Sie die Anzahl der Tore aus einem Set mit konstanter Größe zählen, werden viele Dinge erfasst, über die Sie sich als praktische Ressourcen Sorgen machen könnten: Es bleibt nur sehr wenig Platz, um alles zu verbergen, was insgeheim sehr teuer ist.

Zumindest nicht für den Speicher, da jeder Speicherzugriff 'Zeit' erfordert .$O(1)$

Im Begriff Zeitkomplexität ist 'Zeit' etwas irreführend, da wir tatsächlich die Anzahl der Elementaroperationen zählen, die zur Ausführung eines Algorithmus erforderlich sind. Unter der zusätzlichen Annahme, dass diese Operationen in ' -Zeit' ausgeführt werden können, können wir sagen, dass unser Algorithmus eine 'Zeitkomplexität' aufweist. Aber was wir eigentlich meinen, ist, dass wir eine "Operationskomplexität" haben, die wir rechtzeitig ausdrücken.$O(1)$

Ich denke, es ist klarer, dass das Zählen von Elementaroperationen ein grundlegendes und wichtiges Maß für die Anzahl der von einem Algorithmus benötigten Ressourcen ist, da wir immer entscheiden können, wie viele Ressourcen jede Elementaroperation benötigt.

Während bei der Definition von BQP und für Quantenalgorithmen die Schaltungskomplexität anstelle der "Betriebskomplexität" betrachtet wird, kann die Schaltungskomplexität wiederum in Bezug auf Operationen auf Turing-Maschinen definiert werden, sodass die gleiche Argumentation gilt.