Modelos de cómputo estrictamente entre clásico y cuántico en términos de complejidad de consulta

18

Es bien sabido que las computadoras cuánticas son estrictamente más poderosas que sus contrapartes clásicas en términos de complejidad de consulta .

¿Existen otros modelos (naturales o artificiales) que estén estrictamente entre lo cuántico y lo clásico en términos de complejidad de consulta?

La separación puede estar en

problemas específicos: el modelo X calcula la función con estrictamente más consultas que cuánticas, pero menos consultas que el límite inferior en el clásico, o $f$
problemas diferentes: el modelo X calcula la función con estrictamente más consultas que cuánticas, pero calcula la función con menos consultas que las clásicas. $f_1$ $f_2$

En ambos casos, queremos que cada función tenga para evitar ejemplos que sean difíciles de comparar con cuánticos (como la complejidad del certificado de consultas no deterministas). Aquí (y ) es la dos caras cuántica -error (y clásica aleatorizado) la complejidad de consulta y las desigualdades se encuentran dentro de los factores constantes. $f$ $Q_2(f) \leq X(f) \leq R_2(f)$ $Q_2(f)$ $R_2(f)$ $1/3$

cc.complexity-theory quantum-computing query-complexity Artem Kaznatcheev
fuente

8

Una manera fácil de llegar a tal modelo es crear primero un modelo restringido de computación cuántica que aún pueda hacer algo no clásico, y luego simplemente darle la computación clásica de forma gratuita.

Un ejemplo de esta estrategia es el modelo de qubit limpio (junto con una máquina BPP). Algunas referencias: sobre el poder de un bit de información cuántica , la computación con unitarios y un puro Qubit y la estimación de polinomios de Jones es un problema completo para un qubit limpio .

Otro ejemplo sería tener un circuito cuántico de profundidad de registro (o profundidad de registro múltiple) con acceso a una computadora clásica. Esto dará lugar a algo como . $BPP^{BQNC}$

Robin Kothari
fuente

Esto ciertamente funciona para la complejidad computacional, pero ¿funciona para la complejidad de la consulta? No veo inmediatamente ningún problema para el que el modelo de qubit limpio + BPP produzca una mejor complejidad de consulta que una máquina clásica. Además, en general, esta técnica puede fallar, ya que dar a un grupo Clifford o una computadora de compuerta de fósforo la computación clásica los impulsa a la computación cuántica universal.

Joe Fitzsimons

@JoeFitzsimons: No puedo pensar en un problema fuera de mi cabeza, pero creo que Dan Shepherd muestra una separación de oráculo entre BPP y el único modelo de qubit limpio en su artículo. Su segundo punto es válido, por supuesto.

Robin Kothari

Pero seguramente una separación de oráculo no implica necesariamente una separación de complejidad de consulta.

Joe Fitzsimons

Estoy de acuerdo con @JoeFitzsimons, aunque el modelo DQC1 es interesante, no he visto una separación de complejidad de consulta para él. Los problemas naturales como la estimación de trazas o la variante de Peter Shor del problema polinomial de Jones parecen difíciles de presentar en el modelo de consulta.

Artem Kaznatcheev

7

$X(f)\leq D(f)$ $R_2(f)$

Joe Fitzsimons
fuente

2

P

$\mathsf P$

\oplus L

$\oplus L$

P

$\mathsf P$

L

$\mathsf L$

2

Quizás el ejemplo más claro de este tipo de modelos informáticos es DQC1 explicado por @RobinKothari en su respuesta. Vea las referencias en su respuesta para una buena introducción al modelo.

Además, recientemente, hubo un buen artículo en la revista Nature sobre Quantum Discord. Quantum Discord es una medida teórica de la información de correlaciones no clásicas, enredando en general. Aquí está el enlace . Verá que hay ejemplos de cálculos en los que el enredo no juega un papel fundamental, es decir, otras correlaciones no clásicas son las que se encargan de acelerar el cálculo. Esto sucede en DQC1 para calcular el rastro de una matriz (ver el artículo de Datta, Shaji y Caves ). Lo que es interesante en el artículo es que abre la pregunta sobre "Algoritmos basados en la discordia cuántica", es decir, algoritmos en los que no necesita enredarse para la aceleración cuántica. Eso es algo entre la computación cuántica completa y la clásica.

Otro modelo que posiblemente caiga en esta categoría (entre el cuántico completo y el clásico) es el Modelo óptico lineal de Arkhipov y Aaronson. Vea esta pregunta para una buena explicación.

No sé dónde encajan estos modelos en términos de complejidad de consulta, pero podría ser un buen punto de partida.

Marcos Villagra
fuente

Modelos de cómputo estrictamente entre clásico y cuántico en términos de complejidad de consulta

Respuestas: