Eine Quantenschaltung kann jeden einheitlichen Operator verwenden. Seine Matrix ist exponentiell in der Anzahl der Eingangsbits. Wie kann dies in der Praxis jemals möglich sein (abgesehen von Operatoren, die Tensorprodukte sind), dh wie können Sie eine exponentielle Größenmatrix erstellen?
Der Schlüssel ist , dass Sie nicht wirklich eine Matrix konstruieren. Ja, wenn Sie eine Quantenberechnung auf einem klassischen Computer simulieren möchten, besteht eine Methode darin, die entsprechende einheitliche Matrix zu erstellen. Aus diesem Grund ist es (sofern keine spezielle Struktur vorhanden ist) unmöglich, eine klassische Simulation der Quantenberechnung effizient durchzuführen.
Die grundlegenden Quantenoperationen, die wir verwenden, werden auf diese Weise betrachtet - Sie tun wirklich nur ein oder zwei Qubits gleichzeitig und machen sie exponentiell, indem Sie allen anderen Qubits Identitäten hinzufügen ("nichts tun"). Das Kombinieren einer kleinen Anzahl von diesen, die auf verschiedene Sätze von Qubits wirken, kann einige einheitliche Matrizen erzeugen, die keine Tensorprodukte sind.
Während ein Quantencomputer im Prinzip jeden einheitlichen Operator implementieren kann, sagt die Universalität in diesem Sinne nichts darüber aus, wie lange die Konstruktion dauert. Die große, überwältigende Mehrheit von ihnen haben nehmen exponentielle Zeit zu implementieren. Die Quantenberechnung ist speziell daran interessiert, diese Goldlöckchen-Zone zu finden, jene kleine Anzahl von Instanzen, die in Polynomzeit implementiert werden können und eine interessante Berechnung ergeben, die auf einem klassischen Computer nicht in Polynomzeit berechnet werden kann.
Beachten Sie, dass diesbezüglich nichts spezielles Quantum ist.
Die Dimension dieser Matrizen nimmt ebenfalls exponentiell mit der Anzahl der Bits zu, dies ist jedoch kein Problem, da es aus den in der anderen Antwort dargelegten Gründen keinen Zusammenhang damit gibt, wie schwierig es tatsächlich ist, die entsprechende Operation zu implementieren .