En la teoría de la complejidad computacional , PostBQP es una clase de complejidad que consta de todos los problemas computacionales que se pueden resolver en tiempo polinomial en una máquina cuántica de Turing con postselección y error acotado (en el sentido de que el algoritmo es correcto al menos 2/3 del tiempo en todos entradas).
La posselección no se considera una característica que posea una computadora realista (incluso una cuántica), pero no obstante, las máquinas de posselección son interesantes desde una perspectiva teórica.
La eliminación de cualquiera de las dos características principales (quantumness, postselección) de PostBQP da las siguientes dos clases de complejidad, las cuales son subconjuntos de PostBQP :
- BQP es igual que PostBQP excepto sin postselección
- La ruta de BPP es la misma que la de PostBQP, excepto que en lugar de cuántica, el algoritmo es un algoritmo aleatorio clásico (con postselección) [1]
La adición de la postselección parece hacer que las máquinas cuánticas de Turing sean mucho más poderosas: Scott Aaronson demostró que [2] [3] PostBQP es igual a PP , una clase que se cree que es relativamente poderosa, mientras que BQP ni siquiera contiene lo aparentemente más pequeño clase NP . Usando técnicas similares, Aaronson también demostró que pequeños cambios en las leyes de la computación cuántica tendrían efectos significativos. Como ejemplos específicos, en cualquiera de los dos cambios siguientes, la "nueva" versión de BQP sería igual a PP :
- si ampliamos la definición de 'puerta cuántica' para incluir no solo operaciones unitarias sino operaciones lineales, o
- si la probabilidad de medir un estado base era proporcional a en vez de para cualquier entero par p> 2 .
Propiedades básicas
Para describir algunas de las propiedades de PostBQP , fijamos una forma formal de describir la postselección cuántica. Defina un algoritmo cuántico para que sea una familia de circuitos cuánticos (específicamente, una familia de circuitos uniforme ). Designamos un qubit como el qubit P posterior a la selección y otro como el qubit Q de salida . Entonces PostBQP se define mediante la selección posterior en el caso de que el qubit posterior a la selección sea. Explícitamente, un lenguaje L está en PostBQP si hay un algoritmo cuántico A de modo que después de ejecutar A en la entrada xy medir los dos qubits P y Q ,
- P = 1 con probabilidad distinta de cero
- si la entrada x está en L entonces Pr [ Q = 1 | P = 1] ≥ 2/3
- si la entrada x no está en L entonces Pr [ Q = 0 | P = 1] ≥ 2/3.
Se puede demostrar que permitir un solo paso posterior a la selección al final del algoritmo (como se describió anteriormente) o permitir pasos intermedios posteriores a la selección durante el algoritmo son equivalentes. [2] [4]
Aquí hay tres propiedades básicas de PostBQP (que también son válidas para BQP a través de pruebas similares):
1. PostBQP se cierra bajo complemento . Dado un lenguaje L en PostBQP y una familia de circuitos de decisión correspondiente, cree una nueva familia de circuitos cambiando el qubit de salida después de la medición, luego la nueva familia de circuitos demuestra que el complemento de L está en PostBQP .
2. Puede hacer una amplificación de probabilidad en PostBQP . La definición de PostBQP no cambia si reemplazamos el valor 2/3 en su definición por cualquier otra constante estrictamente entre 1/2 y 1. Como ejemplo, dado un algoritmo PostBQP A con probabilidad de éxito 2/3, podemos construir otro algoritmo que ejecuta tres copias independientes de A , genera un bit de postselección igual a la conjunción de los tres "internos" y genera un bit de salida igual a la mayoría de los tres "internos"; el nuevo algoritmo será correcto con probabilidad condicional, mayor que los 2/3 originales.
3. PostBQP está cerrado en la intersección . Supongamos que tenemos familias de circuitos PostBQP para dos lenguajes L1 y L2 , con qubits de postselección respectivos y qubits de salida P1, P2, Q1, Q2 . Podemos suponer por amplificación de probabilidad que ambas familias de circuitos tienen una probabilidad de éxito de al menos 5/6. Luego creamos un algoritmo compuesto donde los circuitos para L1 y L2 se ejecutan de forma independiente, y establecemos P en la conjunción de P1 y P2 , y Q en la conjunción de Q1 y Q2 . No es difícil ver por un enlace de unión que este algoritmo compuesto decide correctamente la membresía en con probabilidad (condicional) de al menos 2/3.
De manera más general, las combinaciones de estas ideas muestran que PostBQP está cerrado bajo reducciones de tabla de verdad de unión y BQP.
PostBQP = PP
Scott Aaronson demostró [5] que las clases de complejidad PostBQP (tiempo polinomial cuántico de error acotado postseleccionado) y PP (tiempo polinomial probabilístico) son iguales. El resultado fue significativo porque esta reformulación de la computación cuántica de PP proporcionó una nueva perspectiva y pruebas más simples de las propiedades de PP .
La definición habitual de una familia de circuitos PostBQP es una con dos qubits de salida P (postselección) y Q (salida) con una sola medición de P y Q al final, de modo que la probabilidad de medir P = 1 tiene una probabilidad distinta de cero, la probabilidad condicional Pr [ Q = 1 | P = 1] ≥ 2/3 si la entrada x está en el idioma y Pr [ Q = 0 | P = 1] ≥ 2/3 si la entrada x no está en el idioma. Por razones técnicas, modificamos la definición de PostBQP de la siguiente manera: requerimos que Pr [ P = 1] ≥ 2 - n c para alguna constante c dependiendo de la familia de circuitos. Tenga en cuenta que esta elección no afecta las propiedades básicas de PostBQP , y también se puede demostrar que cualquier cálculo que consista en puertas típicas (por ejemplo, Hadamard, Toffoli) tiene esta propiedad siempre que Pr [ P = 1]> 0.
Demostrando PostBQP ⊆ PP
Supongamos que se nos da una PostBQP familia de circuitos para decidir un lenguaje L . Suponemos sin pérdida de generalidad (por ejemplo, ver las propiedades no esenciales de las computadoras cuánticas ) que todas las puertas tienen matrices de transición que se representan con números reales, a expensas de agregar un qubit más.
Sea Ψ el estado cuántico final del circuito antes de que se realice la medición posterior a la selección. El objetivo general de la prueba de ello es la construcción de un PP algoritmo para decidir L . Más específicamente, es suficiente que L compare correctamente la amplitud al cuadrado de Ψ en los estados con Q = 1, P = 1 con la amplitud al cuadrado de Ψ en los estados con Q = 0, P = 1 para determinar cuál es mayor. La idea clave es que la comparación de estas amplitudes se puede transformar en comparar la probabilidad de aceptación de una máquina de PP con 1/2.
Vista de matriz de algoritmos PostBQP
Sea n el tamaño de la entrada, B = B ( n ) el número total de qubits en el circuito (entradas, qubits auxiliares, de salida y posteriores a la selección), y G = G ( n ) denota el número total de puertas. Represente la i- ésima puerta por su matriz de transición A i (un unitario realmatrix) y sea el estado inicial | x > (rellenado con ceros). Luego. Definir S 1 (resp. S 0 ) como el conjunto de estados base correspondientes a P = 1, Q = 1 (resp. P = 1, Q = 0 ) y definir las probabilidades
La definición de PostBQP asegura que o según que x esté en L o no.
Nuestra máquina de PP se comparará y . Para hacer esto, ampliamos la definición de multiplicación de matrices:
donde la suma se toma sobre todas las listas de vectores de base G. Ahora y se puede expresar como una suma de productos por pares de estos términos. Intuitivamente, queremos diseñar una máquina cuya probabilidad de aceptación sea algo así como, Desde entonces implicaría que la probabilidad de aceptación es , tiempo implicaría que la probabilidad de aceptación es .
Técnica: podemos asumir que las entradas de las matrices de transición A i son racionales con denominador 2 f ( n ) para algún polinomio f ( n ).
La definición de PostBQP nos dice quesi x está en L , y que en caso contrario. Reemplacemos todas las entradas de A por la fracción más cercana con denominador para un polinomio grande que describimos actualmente. Lo que se utilizará más adelante es que los nuevos valores de π satisfacensi x está en L , ysi x no está en L . Utilizando el supuesto técnico anterior y analizando cómo cambia la norma 1 del estado computacional, esto se considera satisfecho sipor tanto, es evidente que hay una f suficientemente grande que es polinomio en n .
Construyendo la máquina de PP
Ahora proporcionamos la implementación detallada de nuestra máquina PP . Sea α la secuencia y definir la notación taquigráfica
- ,
luego
Definimos nuestra máquina de PP para
- elegir un estado base ω uniformemente al azar
- Si luego DETENER y aceptar con probabilidad 1/2, rechazar con probabilidad 1/2
- elige dos secuencias de los estados base G uniformemente al azar
- calcular (que es una fracción con denominador tal que )
- Si luego acepta con probabilidad y rechazar con probabilidad (que toma como máximo lanzamientos de moneda)
- de lo contrario (entonces ) aceptar con probabilidad y rechazar con probabilidad (que de nuevo toma como máximo lanzamientos de moneda)
Entonces es sencillo calcular que esta máquina acepta con probabilidad por lo que esta es una máquina de PP para el lenguaje L , según sea necesario.
Demostrando PP ⊆ PostBQP
Supongamos que tenemos una máquina de PP con complejidad de tiempo T: = T (n) en la entrada x de longitud n: = | x | . Por lo tanto, la máquina lanza una moneda en la mayoría de T veces durante el cálculo. Por lo tanto, podemos ver la máquina como una función determinista f (implementada, por ejemplo, por un circuito clásico) que toma dos entradas ( x, r ) donde r , una cadena binaria de longitud T , representa los resultados de los lanzamientos de monedas aleatorios que se realizan por el cálculo, y la salida de f es 1 (aceptar) o 0 (rechazar). La definición de PP nos dice que
Por lo tanto, queremos un algoritmo PostBQP que pueda determinar si la declaración anterior es cierta.
Defina s como el número de cadenas aleatorias que conducen a la aceptación,
y entonces es el número de cadenas rechazadas. Es sencillo argumentar que sin pérdida de generalidad,; para más detalles, ver un supuesto similar sin pérdida de generalidad en la prueba de que PP está cerrado bajo complementación .
Algoritmo de Aaronson
El algoritmo de Aaronson para resolver este problema es el siguiente. Para simplificar, escribiremos todos los estados cuánticos como no normalizados. Primero, preparamos el estado. En segundo lugar, aplicamos las puertas Hadamard al primer registro (cada uno de los primeros T qubits), medimos el primer registro y luego seleccionamos si es la cadena de cero. Es fácil verificar que esto deja el último registro (el último qubit) en el estado residual
Donde H denota la puerta de Hadamard, calculamos el estado
- .
Dónde son números reales positivos que se elegirán más tarde con , calculamos el estado y medir el segundo qubit, postseleccionando si su valor es igual a 1, lo que deja el primer qubit en un estado residual dependiendo de que denotamos
- .
Visualizando los posibles estados de un qubit como un círculo, vemos que si , (es decir, si ) luego se encuentra en el cuadrante abierto mientras que si , (es decir, si ) luego se encuentra en el cuadrante abierto . De hecho, para cualquier x fijo (y sus correspondientes s ), a medida que variamos la razón en , tenga en cuenta que la imagen de es precisamente el cuadrante abierto correspondiente. En el resto de la demostración, precisamos la idea de que podemos distinguir entre estos dos cuadrantes.
Análisis
Dejar , que es el centro de , y deja ser ortogonal a . Cualquier qubit en, cuando se mide en la base , da el valor menos de la mitad del tiempo. Por otro lado, si y habíamos elegido luego midiendo en la base daría el valor todo el tiempo. Como no sabemos s tampoco sabemos el valor exacto de r * , pero podemos probar varios (polinomialmente muchos) valores diferentes paracon la esperanza de conseguir uno que esté "cerca" de r * .
Específicamente, tenga en cuenta y establezcamos sucesivamente a cada valor de la forma por . Luego, los cálculos elementales muestran que para uno de estos valores de i , la probabilidad de que la medición de en la base rendimientos Por lo menos
En general, el algoritmo PostBQP es el siguiente. Sea k cualquier constante estrictamente entre 1/2 y. Hacemos el siguiente experimento para cada: construir y medir en la base un total de veces donde C es una constante. Si la proporción demedidas es mayor que k , luego rechace. Si no rechazamos por ninguna i , acepte. Los límites de Chernoff muestran entonces que para una constante universal C suficientemente grande , clasificamos correctamente x con una probabilidad de al menos 2/3.
Tenga en cuenta que este algoritmo satisface el supuesto técnico de que la probabilidad general posterior a la selección no es demasiado pequeña: cada medición individual de tiene probabilidad posterior a la selección y entonces la probabilidad general es .
Trascendencia
Referencias
- ^ Y. Han y Hemaspaandra, L. y Thierauf, T. (1997). "Cálculo de umbrales y seguridad criptográfica". Revista SIAM de Computación . 26 : 59–78. CiteSeerX 10.1.1.23.510 . doi : 10.1137 / S0097539792240467 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ a b Aaronson, Scott (2005). "Computación cuántica, postselección y polinomio probabilístico-tiempo". Proceedings of the Royal Society A . 461 (2063): 3473–3482. arXiv : quant-ph / 0412187 . Código bibliográfico : 2005RSPSA.461.3473A . doi : 10.1098 / rspa.2005.1546 .. Preimpresión disponible en [1]
- ^ Aaronson, Scott (11 de enero de 2004). "Clase de complejidad de la semana: PP" . Weblog de complejidad computacional . Consultado el 2 de mayo de 2008 .
- ^ Ethan Bernstein y Umesh Vazirani (1997). "Teoría de la complejidad cuántica". Revista SIAM de Computación . 26 (5): 11-20. CiteSeerX 10.1.1.144.7852 . doi : 10.1137 / s0097539796300921 .
- ^ Aaronson, Scott (2005). "Computación cuántica, postselección y polinomio probabilístico-tiempo". Proceedings of the Royal Society A . 461 (2063): 3473–3482. arXiv : quant-ph / 0412187 . Código bibliográfico : 2005RSPSA.461.3473A . doi : 10.1098 / rspa.2005.1546 .