¿BQP es solo cuestión de tiempo? ¿Es esto significativo?

La clase de complejidad BQP (tiempo polinómico cuántico de error acotado) parece definirse solo considerando el factor tiempo. ¿Es esto siempre significativo? ¿Existen algoritmos donde el tiempo computacional se escala polinomialmente con el tamaño de entrada pero otros recursos, como la memoria, se escalan exponencialmente?

BQP se define considerando el tamaño del circuito , es decir, el número total de puertas. Esto significa que incorpora:

• Número de qubits: porque podemos ignorar cualquier qubits sobre los que no actúa una puerta. Esto estará limitado polinómicamente en relación con el tamaño de entrada y, a menudo, un polinomio modesto (por ejemplo, el algoritmo de Shor solo involucra un número de qubits que es un factor constante multiplicado por el tamaño de entrada).
• Profundidad del circuito (o 'tiempo'): porque lo más largo que podría tomar el cálculo es si realizamos una puerta tras otra, sin realizar ninguna operación en paralelo.
• Comunicación con los sistemas de control: debido a que las puertas que se realizan se toman de un conjunto de puertas finitas, e incluso si permitimos mediciones intermedias, la cantidad de comunicación requerida para indicar el resultado de la medición y la cantidad de cálculo requerida para determinar qué se hará a continuación suele ser una constante para cada operación.
• Interacciones entre sistemas cuánticos: incluso si consideramos una arquitectura que no tiene interacciones totales o nada parecido, podemos simular tener esa conectividad realizando operaciones SWAP explícitas, que pueden descomponerse en un número constante de dos operaciones de qubit. Esto podría darnos una sobrecarga polinómica notable que afecta lo práctico que es un algoritmo para una arquitectura dada, pero no oculta una cantidad exponencial de trabajo.
• Energía: una vez más, debido a que los circuitos se descomponen en un conjunto de puertas finito, no hay una forma obvia de obtener una aceleración aparente al "hacer las puertas más rápido" o al ocultar el trabajo en una interacción exótica, si nuestro límite es en términos de El número de operaciones realizadas a partir de un conjunto bastante básico de operaciones. Esta consideración es más importante en la computación cuántica adiabática: no podemos tratar de evitar pequeñas brechas simplemente amplificando todo el panorama energético tanto como queramos, lo que significa que debemos tomar más tiempo para hacer el cálculo, correspondiente en la imagen del circuito para Un circuito con más puertas.

En efecto, contar el número de puertas de un conjunto de tamaño constante captura muchas cosas de las que podría preocuparse como recursos prácticos: deja muy poco espacio para ocultar cualquier cosa que es secretamente muy costosa.

No para memoria, al menos, ya que cada acceso a memoria requiere 'tiempo'.$O(1)$

En el término complejidad del tiempo, 'tiempo' es un poco engañoso, ya que en realidad contamos el número de operaciones elementales requeridas para realizar un algoritmo. Bajo el supuesto adicional de que estas operaciones se pueden realizar en ' tiempo', podemos decir que nuestro algoritmo tiene una 'complejidad de tiempo'. Pero lo que realmente queremos decir es que tenemos una "complejidad operativa" que expresamos a tiempo.$O(1)$

Creo que es más claro que contar operaciones elementales es una medida fundamental e importante del número de recursos requeridos por un algoritmo, ya que siempre podemos decidir cuántos recursos requiere cada operación elemental.

Mientras que en la definición de BQP y para los algoritmos cuánticos consideramos la complejidad del circuito en lugar de la " complejidad de la operación", la complejidad del circuito puede definirse nuevamente en términos de operaciones en máquinas Turing, por lo que se aplica el mismo razonamiento.