En lugar de evidencia empírica, ¿con qué principios formales hemos demostrado que la computación cuántica será más rápida que la computación tradicional /
Antecedentes Las funciones en son PAC que se pueden aprender en tiempo cuasipolinomial con un algoritmo clásico que requiere consultas elegidas al azar para aprender un circuito de profundidad d [1]. Si no hay un algoritmo de factorización , entonces esto es óptimo [2]. Por supuesto, en una...
A menudo consideramos clases de complejidad donde estamos limitados en la cantidad de espacio que nuestra máquina Turing puede usar, por ejemplo: o NSPACE ( f ( n ) ) . Parece que al principio de la teoría de la complejidad hubo mucho éxito con estas clases, como el teorema de la jerarquía espacial...
¿Existe algún paquete de software que permita la descomposición de unidades unitarias de en circuitos cuánticos sobre un conjunto de compuerta universal predefinido?U(
Pregunta corta ¿Cuál es el poder computacional de los circuitos "cuánticos", si permitimos puertas no unitarias (pero aún invertibles), y requerimos que la salida dé la respuesta correcta con certeza? Esta pregunta es, en cierto sentido, sobre lo que le sucede a la clase cuando permite que los...
A partir de los comentarios sobre una de mis preguntas sobre MathOverflow, tengo la sensación de que la pregunta sobre que GCD está en vs. es similar a la pregunta sobre la Factorización de enteros en vs. .NCNC\mathsf{NC}PP\mathsf{P}PP\mathsf{P}NPNP\mathsf{NP} ¿Hay algo así como un algoritmo...
Beigi, Shor y Watrous tienen un muy buen artículo sobre el poder de las pruebas cuánticas interactivas con mensajes cortos. Consideran tres variantes de 'mensajes cortos', y la específica que me interesa es su segunda variante donde se puede enviar cualquier número de mensajes, pero la longitud...
Por lo que puedo decir, casi todas las implementaciones de QKD usan el algoritmo CASCADE de Brassard y Salvail para la corrección de errores. ¿Es este realmente el método más conocido para corregir errores en una secuencia compartida de qubits aleatorios, o hay una mejor propuesta de que las...
Soy estudiante universitario de ciencias de la computación y actualmente estoy planeando mi proyecto de graduación. Necesito algunas ideas en el campo de la computación cuántica. ¿alguna
Contexto. Estoy escribiendo sobre temas como el teorema de Gottesman-Knill , utilizando grupos estabilizadores de Pauli, pero en el caso de d -qudits dimensionales, donde d puede tener más de un factor primo. (Destaco esto porque la gran mayoría de la literatura sobre formalismo estabilizador en...
La teoría del cómputo del estado del clúster ya está bien establecida, lo que demuestra que cualquier circuito BQP puede modificarse de modo que solo use puertas cuánticas de qubit único, posiblemente controladas de forma clásica, que proporcionen un amplio suministro de un estado conocido como...
En el artículo Quantum Random Walks Hit Exponencialmente más rápido ( arXiv: quant-ph / 0205083 ) Kempe da una noción del tiempo de golpeo para caminatas cuánticas (en el hipercubo) que no es muy popular en la literatura de la caminata cuántica. Se define de la siguiente manera: One-Shot Quantum...
Versión rápida ¿Existen modelos de la decoherencia cuántica para la caminata en la línea de tal manera que podemos sintonizar el pie de propagación como para cualquier 1 / 2 ≤ k ≤ 1 ?Θ ( tk)Θ(tk)\Theta(t^k)1 / 2 ≤ k ≤ 11/2≤k≤11/2 \leq k \leq 1 Motivación Las caminatas aleatorias clásicas...
He leído en SP Jordan, D. Gosset, "Amor del PJ problemas -Complete para hamiltonianas stoquastic y matrices de MarkovQ MUNQMAQMA " que es poco probable que .Q MA ⊆ A MQMA⊆AMQMA \subseteq AM Me sorprendió esta afirmación. Entonces, ¿cuál es la relación adecuada entre y A M ?Q MUNQMAQMAA...
El grupo Clifford de operadores cuánticos es generado por las operaciones cuánticas: Z controlada , Hadamard y = | 0 ⟩ ⟨ 0 | + i | 1 ⟩ ⟨ 1 |=El |0 0⟩⟨0 0El |+yoEl |1⟩⟨1El |= |0\rangle\langle0| + i |1\rangle\langle1| Un circuito compuesto solo por estas puertas puede simularse eficientemente en...
Estoy buscando una encuesta sobre los conceptos importantes en el campo de los autómatas cuánticos. He encontrado la teoría de los autómatas cuánticos: una revisión de Hirvensalo, pero parece demasiado sucinto para comprender el tema. ¿Existe una encuesta bastante completa sobre el tema de...
Ahora se sabe que el adversario general de límite inferior caracteriza la complejidad de la consulta cuántica debido al trabajo innovador de Reichardt et al. La misma línea de trabajo también establece conexiones con el marco del programa span para diseñar algoritmos cuánticos. Muchos algoritmos...
Estoy considerando ideas sobre algoritmos cuánticos exactos. En particular, estoy considerando las posibles limitaciones de EQPEQP\mathsf{EQP} , que consiste en lenguajes exactamente decidibles por las familias de circuitos cuánticos uniformes de polimetro sobre un conjunto arbitrario de puerta...
Actualmente estoy buscando algún buen material de referencia que relacione juegos no locales con aspectos beneficiosos en la comunicación cuántica. Por ejemplo, soy consciente de que los juegos no locales son buenos para reducir la complejidad de la comunicación, así como para garantizar la...
Creo que la respuesta a esta pregunta es bien conocida; pero, desafortunadamente, no lo sé. En computación cuántica, sabemos que los estados mixtos están representados por matrices de densidad. Y la norma de traza de la diferencia de dos matrices de densidad caracteriza la distinción de los dos...