BQP - BQP

En la teoría de la complejidad computacional , el tiempo polinomial cuántico de error acotado ( BQP ) es la clase de problemas de decisión que puede resolver una computadora cuántica en tiempo polinomial , con una probabilidad de error de como máximo 1/3 para todos los casos. Es el análogo cuántico de la clase de complejidad BPP .

Un problema de decisión es miembro de BQP si existe un algoritmo cuántico (un algoritmo que se ejecuta en una computadora cuántica) que resuelve el problema de decisión con alta probabilidad y se garantiza que se ejecutará en tiempo polinomial. Una ejecución del algoritmo resolverá correctamente el problema de decisión con una probabilidad de al menos 2/3.

Algoritmo BQP (1 ejecución)
Respuesta producido Respuesta correcta	sí	No
sí	≥ 2/3	≤ 1/3
No	≤ 1/3	≥ 2/3
Algoritmo BQP ( k ejecuciones)
Respuesta producido Respuesta correcta	sí	No
sí	> ^1-2^{- ck}	<2 ^{- ck}
No	<2 ^{- ck}	> ^1-2^{- ck}
para alguna constante c > 0

Definición

BQP puede verse como los lenguajes asociados con ciertas familias uniformes de circuitos cuánticos de error acotado . Un lenguaje L está en BQP si y solo si existe una familia uniforme de circuitos cuánticos en tiempo polinómico , tal que ${\ Displaystyle \ {Q_ {n} \ dos puntos n \ in \ mathbb {N} \}}$

Para todos , Q _n toma n qubits como entrada y salidas 1 bit ${\ Displaystyle n \ in \ mathbb {N}}$
Para todo x en L , ${\ Displaystyle \ mathrm {Pr} (Q_ {| x |} (x) = 1) \ geq {\ tfrac {2} {3}}}$
Para todo x no en L , ${\ Displaystyle \ mathrm {Pr} (Q_ {| x |} (x) = 0) \ geq {\ tfrac {2} {3}}}$

Alternativamente, se puede definir BQP en términos de máquinas cuánticas de Turing . Un lenguaje L está en BQP si y solo si existe una máquina de Turing cuántica polinomial que acepta L con una probabilidad de error de como máximo 1/3 para todas las instancias.

De manera similar a otras clases probabilísticas de "error acotado", la elección de 1/3 en la definición es arbitraria. Podemos ejecutar el algoritmo un número constante de veces y obtener un voto mayoritario para lograr cualquier probabilidad de corrección deseada menor que 1, utilizando el límite de Chernoff . La clase de complejidad no cambia permitiendo un error tan alto como 1/2 - n ^{- c} por un lado, o requiriendo un error tan pequeño como 2 ^{- n ^c} por otro lado, donde c es cualquier constante positiva y n es la longitud de entrada.

Un problema completo de BQP

Similar a la noción de NP-completitud y otros problemas completos , podemos definir un problema BQP-completo como un problema que está en BQP y que cada problema en BQP se reduce a él en tiempo polinomial.

Aquí hay un problema completo intuitivo de BQP, que se deriva directamente de la definición de BQP.

Problema de APPROX-QCIRCUIT-PROB

Dada una descripción de un circuito cuántico que actúa sobre qubits con puertas, donde hay un polinomio y cada puerta actúa sobre uno o dos qubits, y dos números , distinga entre los dos casos siguientes: ${\ Displaystyle C}$ ${\ Displaystyle n}$ ${\ Displaystyle m}$ ${\ Displaystyle m}$ ${\ Displaystyle n}$ ${\ Displaystyle \ alpha, \ beta \ in [0,1], \ alpha> \ beta}$

midiendo el primer qubit del estado rinde con probabilidad ${\ Displaystyle C | 0 \ rangle ^ {\ otimes n}}$ ${\ Displaystyle | 1 \ rangle}$ ${\ Displaystyle \ geq \ alpha}$
midiendo el primer qubit del estado rinde con probabilidad ${\ Displaystyle C | 0 \ rangle ^ {\ otimes n}}$ ${\ Displaystyle | 1 \ rangle}$ ${\ Displaystyle \ leq \ beta}$

Tenga en cuenta que el problema no especifica el comportamiento si una instancia no está cubierta por estos dos casos.

Afirmar. Cualquier problema de BQP se reduce a APROX-QCIRCUIT-PROB.

Prueba. Supongamos que tenemos un algoritmo que resuelve APROX-QCIRCUIT-PROB, es decir, dado un circuito cuántico que actúa sobre qubits y dos números , distingue entre los dos casos anteriores. Podemos resolver cualquier problema en BQP con este oráculo, configurando . ${\ Displaystyle A}$ ${\ Displaystyle C}$ ${\ Displaystyle n}$ ${\ Displaystyle \ alpha, \ beta \ in [0,1], \ alpha> \ beta}$ ${\ Displaystyle A}$ ${\ Displaystyle \ alpha = 2/3, \ beta = 1/3}$

Para cualquiera , existe una familia de circuitos cuánticos tal que para todos , un estado de qubits, si ; más si . Fije una entrada de qubits y el circuito cuántico correspondiente . Primero podemos construir un circuito tal que . Esto se puede hacer fácilmente conectando y aplicando una secuencia de puertas CNOT para voltear los qubits. Entonces podemos combinar dos circuitos para obtener , y ahora . Y finalmente, necesariamente el resultado de se obtiene midiendo varios qubits y aplicándoles algunas puertas lógicas (clásicas). Siempre podemos diferir la medición y desviar los circuitos para que al medir el primer qubit de , obtengamos la salida. Este será nuestro circuito , y decidir la composición de en ejecutando con . Por definición de BQP, caeremos en el primer caso (aceptación) o en el segundo caso (rechazo), por lo que se reduce a APROX-QCIRCUIT-PROB. ${\ Displaystyle L \ in \ mathrm {BQP}}$ ${\ Displaystyle \ {Q_ {n} \ dos puntos n \ in \ mathbb {N} \}}$ ${\ Displaystyle n \ in \ mathbb {N}}$ ${\ Displaystyle | x \ rangle}$ ${\ Displaystyle n}$ ${\ Displaystyle x \ in L, Pr (Q_ {n} (| x \ rangle) = 1) \ geq 2/3}$ ${\ Displaystyle x \ notin L, Pr (Q_ {n} (| x \ rangle) = 0) \ geq 2/3}$ ${\ Displaystyle | x \ rangle}$ ${\ Displaystyle n}$ ${\ Displaystyle Q_ {n}}$ ${\ Displaystyle C_ {x}}$ ${\ Displaystyle C_ {x} | 0 \ rangle ^ {\ otimes n} = | x \ rangle}$ ${\ Displaystyle | x \ rangle}$ ${\ Displaystyle C '= C_ {x} Q_ {n}}$ ${\ Displaystyle C '| 0 \ rangle ^ {\ otimes n} = Q_ {n} | x \ rangle}$ ${\ Displaystyle Q_ {n}}$ ${\ Displaystyle C '| 0 \ rangle ^ {\ otimes n} = Q_ {n} | x \ rangle}$ ${\ Displaystyle C}$ ${\ Displaystyle x}$ ${\ Displaystyle L}$ ${\ Displaystyle A (C)}$ ${\ Displaystyle \ alpha = 2/3, \ beta = 1/3}$ ${\ Displaystyle L \ in \ mathrm {BQP}}$

APPROX-QCIRCUIT-PROB es útil cuando intentamos probar las relaciones entre algunas clases de complejidad conocidas y BQP.

Relación con otras clases de complejidad

Problema no resuelto en informática :

¿Cuál es la relación entre y ? ${\ Displaystyle {\ mathsf {BQP}}}$ ${\ Displaystyle {\ mathsf {NP}}}$

(más problemas sin resolver en informática)

La presunta relación de BQP con otros espacios problemáticos

BQP en relación con otras clases de complejidad probabilística ( ZPP , RP , co-RP, BPP , PP ), que generalizan P dentro de PSPACE . Se desconoce si alguna de estas contención es estricta.

BQP se define para computadoras cuánticas; la clase de complejidad correspondiente para las computadoras clásicas (o más formalmente para las máquinas probabilísticas de Turing ) es BPP . Al igual que P y BPP , BQP es bajo por sí mismo, lo que significa BQP ^BQP = BQP . De manera informal, esto es cierto porque los algoritmos de tiempo polinómico están cerrados bajo composición. Si un algoritmo de tiempo polinomial llama a los algoritmos de tiempo polinomial como subrutinas, el algoritmo resultante sigue siendo tiempo polinomial.

BQP contiene P y BPP y está incluido en AWPP , PP y PSPACE . De hecho, BQP es bajo para PP , lo que significa que una máquina de PP no logra ningún beneficio al poder resolver problemas de BQP instantáneamente, una indicación de la posible diferencia de potencia entre estas clases similares. Las relaciones conocidas con las clases de complejidad clásicas son:

{\ Displaystyle {\ mathsf {P \ subseteq BPP \ subseteq BQP \ subseteq AWPP \ subseteq PP \ subseteq PSPACE \ subseteq EXP}}}

Como el problema de P ≟ PSPACE aún no se ha resuelto, se supone que la prueba de desigualdad entre BQP y las clases mencionadas anteriormente es difícil. Se desconoce la relación entre BQP y NP . En mayo de 2018, los informáticos Ran Raz de la Universidad de Princeton y Avishay Tal de la Universidad de Stanford publicaron un artículo que mostraba que, en relación con un oráculo , el PH no contenía BQP .

Agregar postselección a BQP da como resultado la clase de complejidad PostBQP que es igual a PP .

Probaremos o discutiremos algunos de estos resultados a continuación.

BQP y EXP

Comenzamos con una contención más fácil. Para mostrar eso , basta con mostrar que APPROX-QCIRCUIT-PROB está en EXP ya que APPROX-QCIRCUIT-PROB es BQP-complete. ${\ Displaystyle {\ mathsf {BQP}} \ subseteq {\ mathsf {EXP}}}$

Reclamo - ${\ displaystyle {\ text {APROX-QCIRCUIT-PROB}} \ in {\ mathsf {EXP}}}$

Prueba -

La idea es sencilla. Dado que tenemos potencia exponencial, dado un circuito cuántico $C$ , podemos usar una computadora clásica para estimular cada puerta en $C$ para obtener el estado final.

Más formalmente, sea $C$ un circuito cuántico de tamaño polinomial en $n$ qubits y $m$ puertas, donde m es polinomio en n. Sea y el estado después de que se aplica la $i$ -ésima puerta en el circuito . Cada estado se puede representar en una computadora clásica como un vector unitario en . Además, cada puerta se puede representar mediante una matriz en . Por lo tanto, el estado final se puede calcular en el tiempo y, por lo tanto, todos juntos tenemos un algoritmo de tiempo para calcular el estado final y, por lo tanto, la probabilidad de que el primer qubit se mida como uno. Esto implica eso . ${\ Displaystyle | \ psi _ {0} \ rangle = | 0 \ rangle ^ {\ otimes n}}$ ${\ Displaystyle | \ psi _ {i} \ rangle}$ ${\ Displaystyle | \ psi _ {i-1} \ rangle}$ ${\ Displaystyle | \ psi _ {i} \ rangle}$ ${\ Displaystyle \ mathbb {C} ^ {2 ^ {n}}}$ ${\ Displaystyle \ mathbb {C} ^ {2 ^ {n} \ times 2 ^ {n}}}$ ${\ Displaystyle | \ psi _ {m} \ rangle}$ ${\ Displaystyle O (m2 ^ {2n})}$ ${\ Displaystyle 2 ^ {O (n)}}$ ${\ displaystyle {\ text {APROX-QCIRCUIT-PROB}} \ in {\ mathsf {EXP}}}$

Tenga en cuenta que este algoritmo también requiere espacio para almacenar los vectores y las matrices. Mostraremos en la siguiente sección que podemos mejorar la complejidad del espacio. ${\ Displaystyle 2 ^ {O (n)}}$

BQP y PSPACE

Para demostrarlo , primero presentamos una técnica llamada suma de historias. ${\ Displaystyle {\ mathsf {BQP}} \ subseteq {\ mathsf {PSPACE}}}$

Suma de historias

La suma de historias es una técnica introducida por el físico Richard Feynman para la formulación integral de trayectorias . Aplicamos esta técnica a la computación cuántica para resolver APPROX-QCIRCUIT-PROB.

Árbol de suma de historias

Considere un circuito cuántico $C$ , que consta de $t$ puertas, donde cada una proviene de un conjunto de puertas universales y actúa sobre dos qubits como máximo. Para comprender cuál es la suma de historias, visualizamos la evolución de un estado cuántico dado un circuito cuántico como un árbol. La raíz es la entrada y cada nodo del árbol tiene hijos, cada uno de los cuales representa un estado en . El peso en el borde de un árbol desde un nodo en $j$ -ésimo nivel que representa un estado hasta un nodo en -ésimo nivel que representa un estado es , la amplitud de después de aplicar en . La amplitud de transición de un camino de raíz a hoja es el producto de todos los pesos en los bordes a lo largo del camino. Para obtener la probabilidad de que el estado final sea , sumamos las amplitudes de todas las rutas de raíz a salida que terminan en un nodo que representa . ${\ Displaystyle g_ {1}, g_ {2}, \ cdots, g_ {m}}$ ${\ Displaystyle g_ {j}}$ ${\ Displaystyle | 0 \ rangle ^ {\ otimes n}}$ ${\ Displaystyle 2 ^ {n}}$ ${\ Displaystyle \ mathbb {C} ^ {n}}$ ${\ Displaystyle | x \ rangle}$ ${\ Displaystyle j + 1}$ ${\ Displaystyle | y \ rangle}$ ${\ Displaystyle \ langle y | g_ {j + 1} | x \ rangle}$ ${\ Displaystyle | y \ rangle}$ ${\ Displaystyle g_ {j + 1}}$ ${\ Displaystyle | x \ rangle}$ ${\ Displaystyle | \ psi \ rangle}$ ${\ Displaystyle | \ psi \ rangle}$

Más formalmente, para el circuito cuántico $C$ , su suma sobre el árbol de historias es un árbol de profundidad $m$ , con un nivel para cada puerta además de la raíz, y con factor de ramificación . ${\ Displaystyle g_ {i}}$ ${\ Displaystyle 2 ^ {n}}$

Definir : un historial es una ruta en el árbol de suma de historias. Denotaremos una historia mediante una secuencia para algún estado final $x$ . ${\ displaystyle (u_ {0} = | 0 \ rangle ^ {\ otimes n} \ rightarrow u_ {1} \ rightarrow \ cdots \ rightarrow u_ {m-1} \ rightarrow u_ {m} = x)}$

Definir - Let . Sea la amplitud del borde en el $j$ -ésimo nivel del árbol de suma sobre historias . Para cualquier historia , la amplitud de transición de la historia es el producto . ${\ Displaystyle u, v \ in \ {0,1 \} ^ {n}}$ ${\ Displaystyle (| u \ rangle, | v \ rangle)}$ ${\ Displaystyle \ alpha _ {j} (u \ rightarrow v) = \ langle v | g_ {j} | u \ rangle}$ ${\ displaystyle h = (u_ {0} \ rightarrow u_ {1} \ rightarrow \ cdots \ rightarrow u_ {m-1} \ rightarrow u_ {m})}$ ${\ Displaystyle \ alpha _ {h} = \ alpha _ {1} (| 0 \ rangle ^ {\ otimes n} \ rightarrow u_ {1}) \ alpha _ {2} (u_ {1} \ rightarrow u_ {2 }) \ cdots \ alpha _ {m} (u_ {m-1} \ rightarrow x)}$

Reclamación : para una historia . La amplitud de transición de la historia se puede calcular en tiempo polinomial. ${\ Displaystyle (u_ {0} \ rightarrow \ cdots \ rightarrow u_ {m})}$

Prueba -

Cada puerta puede descomponerse en algún operador unitario que actúe sobre dos qubits, que sin pérdida de generalidad pueden tomarse como los dos primeros. Por tanto, que se puede calcular en tiempo polinomial en $n$ . Dado que $m$ es polinomio en $n$ , la amplitud de transición de la historia se puede calcular en tiempo polinomial. ${\ Displaystyle g_ {j}}$ ${\ Displaystyle g_ {j} = I \ otimes {\ tilde {g}} _ {j}}$ ${\ Displaystyle {\ tilde {g}} _ {j}}$ ${\ Displaystyle \ langle v | g_ {j} | u \ rangle = \ langle v_ {1}, v_ {2} | {\ tilde {g}} _ {j} | u_ {1}, u_ {2} \ rangle \ langle v_ {3}, \ cdots, v_ {n} | u_ {3}, \ cdots, u_ {n} \ rangle}$

Reclamación - Dejado ser el estado final del circuito cuántico. Para algunos , la amplitud se puede calcular mediante . ${\ Displaystyle C | 0 \ rangle ^ {\ otimes n} = \ sum _ {x \ in \ {0,1 \} ^ {n}} \ alpha _ {x} | x \ rangle}$ ${\ Displaystyle x \ in \ {0,1 \} ^ {n}}$ ${\ Displaystyle \ alpha _ {x}}$ ${\ Displaystyle \ alpha _ {x} = \ sum _ {h = (| 0 \ rangle ^ {\ otimes n} \ rightarrow u_ {1} \ rightarrow \ cdots \ rightarrow u_ {t-1} \ rightarrow | x \ rangle)} \ alpha _ {h}}$

Prueba -

Tenemos . El resultado viene directamente insertando entre , y , y así sucesivamente, y luego expande la ecuación. Entonces cada término corresponde a a , donde ${\ Displaystyle \ alpha _ {x} = \ langle x | C | 0 \ rangle ^ {\ otimes n} = \ langle x | g_ {t} g_ {t-1} \ cdots g_ {1} | C | 0 \ rangle ^ {\ otimes n}}$ ${\ Displaystyle I = \ sum _ {x \ in \ {0,1 \} ^ {n}} | x \ rangle \ langle x |}$ ${\ Displaystyle g_ {1}, g_ {2}}$ ${\ Displaystyle g_ {2}, g_ {3}}$ ${\ Displaystyle \ alpha _ {h}}$ ${\ displaystyle h = (| 0 \ rangle ^ {\ otimes n} \ rightarrow u_ {1} \ rightarrow \ cdots \ rightarrow u_ {t-1} \ rightarrow | x \ rangle)}$

Reclamo - ${\ displaystyle {\ text {APROX-QCIRCUIT-PROB}} \ in {\ mathsf {PSPACE}}}$

Observe que en el algoritmo de suma sobre historias para calcular cierta amplitud , solo se almacena una historia en cualquier punto del cálculo. Por lo tanto, el algoritmo de suma sobre historias usa espacio para calcular cualquier $x,$ ya que se necesitan bits para almacenar las historias además de algunas variables del espacio de trabajo. ${\ Displaystyle \ alpha _ {x}}$ ${\ Displaystyle O (nm)}$ ${\ Displaystyle \ alpha _ {x}}$ ${\ Displaystyle O (nm)}$

Por lo tanto, en el espacio polinomial, podemos calcular sobre todo $x$ con el primer qubit siendo ${\ Displaystyle \ sum _ {x} | \ alpha _ {x} | ^ {2}}$ 1 , que es la probabilidad de que el primer qubit se mida como 1 al final del circuito.

Observe que, en comparación con la simulación dada para la prueba de que , nuestro algoritmo aquí ocupa mucho menos espacio, pero en cambio mucho más tiempo. ¡De hecho, se necesita tiempo para calcular una sola amplitud! ${\ Displaystyle {\ mathsf {BQP}} \ subseteq {\ mathsf {EXP}}}$ ${\ Displaystyle O (m2 ^ {mn})}$

BQP y PP

Se puede usar un argumento similar de suma sobre historias para demostrarlo . ${\ Displaystyle {\ mathsf {BQP}} \ subseteq {\ mathsf {PP}}}$

BQP, P y NP

En primer lugar, lo sabemos , ya que cada circuito clásico puede ser simulado por un circuito cuántico. ${\ Displaystyle {\ mathsf {P}} \ subseteq {\ mathsf {BQP}}}$

Se conjetura que BQP resuelve problemas difíciles fuera de P, específicamente, problemas en NP. La afirmación es indefinida porque no sabemos si P = NP, por lo que no sabemos si esos problemas están realmente en P. A continuación se muestran algunas pruebas de la conjetura:

Factorización de enteros (ver algoritmo de Shor )
Logaritmo discreto
Simulación de sistemas cuánticos (ver simulador cuántico universal )
Aproximación del polinomio de Jones en ciertas raíces de la unidad
Algoritmo de Harrow-Hassidim-Lloyd (HHL)

Sin embargo, también conocemos un análogo de en un sentido de "caja negra". Considere el problema de la búsqueda no estructurada: dado un acceso de Oracle a una función desconocida , encuentre $x$ tal que . Este problema está claramente en NP. El algoritmo cuántico óptimo para este problema, por otro lado, es el algoritmo de Grover , que tiene una complejidad de si solo se le permite acceder a $f a$ través de ese oráculo. ${\ Displaystyle {\ mathsf {NP}} \ not \ subseteq {\ mathsf {BQP}}}$ ${\ Displaystyle f: \ {0,1 \} ^ {n} \ to \ {0,1 \}}$ ${\ Displaystyle f (x) = 1}$ ${\ Displaystyle O ({\ sqrt {2 ^ {n}}})}$