Para preguntas sobre algoritmos cuánticos. Es decir, algoritmos que en teoría pueden ser ejecutados por computadoras cuánticas, generalmente las computadoras que proporcionan computación cuántica 'universal'.
El algoritmo de búsqueda de Grover proporciona una aceleración cuadrática demostrable para la búsqueda de bases de datos sin clasificar. El algoritmo generalmente se expresa mediante el siguiente circuito cuántico: En la mayoría de las representaciones, una parte crucial del protocolo es la...
Esta publicación de blog de Scott Aaronson es una explicación muy útil y simple del algoritmo de Shor . Me pregunto si existe tal explicación para el segundo algoritmo cuántico más famoso: el algoritmo de Grover para buscar una base de datos desordenada de tamaño en el tiempo...
(Perdón por una pregunta algo amateur) Estudié computación cuántica de 2004 a 2007, pero he perdido la noción del campo desde entonces. En ese momento había mucha publicidad y se hablaba de que el control de calidad podría resolver todo tipo de problemas superando a las computadoras clásicas,...
¿Existe una declaración general sobre qué tipos de problemas se pueden resolver de manera más eficiente utilizando computadoras cuánticas (solo modelo de puerta cuántica)? ¿Los problemas por los cuales se conoce un algoritmo hoy tienen una propiedad común? Hasta donde entiendo, la computación...
En los últimos días, he estado tratando de recopilar material (principalmente trabajos de investigación) relacionados con el aprendizaje automático de Quantum y sus aplicaciones, para un proyecto de verano. Aquí hay algunos que encontré interesantes (de una lectura superficial): Aprendizaje...
Se ha demostrado que la computación cuántica adiabática es equivalente a la computación cuántica "estándar" o modelo de puerta. Sin embargo, la computación adiabática muestra promesas de problemas de optimización, donde el objetivo es minimizar (o maximizar) una función que de alguna manera está...
La computación cuántica nos permite encriptar la información de una manera diferente en comparación con lo que usamos hoy, pero las computadoras cuánticas son mucho más poderosas que las computadoras de hoy. Entonces, si logramos construir computadoras cuánticas (por lo tanto, usamos criptografía...
Se espera que el algoritmo de Shor nos permita factorizar números enteros mucho más grandes de lo que podría hacerse en las computadoras clásicas modernas. En la actualidad, solo se han factorizado los enteros más pequeños. Por ejemplo, este artículo analiza la factorización 15 = 5 × 315=5...
Antecedentes Recientemente leí el artículo "Quantum Bitcoin: una moneda anónima y distribuida asegurada por el teorema de no clonación de la mecánica cuántica", que demuestra cómo podría funcionar un bitcoin cuántico. La conclusión del artículo establece que: Los bitcoins cuánticos son atómicos...
Tengo entendido que parece haber cierta confianza en que el recocido cuántico proporcionará una aceleración para problemas como el vendedor ambulante, debido a la eficiencia proporcionada por, por ejemplo, el túnel cuántico. ¿Sabemos, sin embargo, en qué medida se proporciona una...
Es un resultado bien conocido que la Transformada discreta de Fourier (DFT) de números tiene complejidad con el algoritmo más conocido , mientras realiza la transformación de Fourier de las amplitudes de un estado cuántico, con el algoritmo QFT clásico , solo requiere puertas elementales...
Deep Learning (múltiples capas de redes neuronales artificiales utilizadas en tareas de aprendizaje automático supervisadas y no supervisadas) es una herramienta increíblemente poderosa para muchas de las tareas de aprendizaje automático más difíciles: reconocimiento de imágenes, reconocimiento de...
Nota sobre el vocabulario: la palabra "hamiltoniano" se usa en esta pregunta para hablar sobre matrices hermitianas. El algoritmo HHL parece ser un tema activo de investigación en el campo de la computación cuántica, principalmente porque resuelve un problema muy importante que es encontrar la...
En esta respuesta , se explica el algoritmo de Grover. La explicación indica que el algoritmo depende en gran medida del operador de difusión Grover , pero no proporciona detalles sobre el funcionamiento interno de este operador. Brevemente, el Operador de Difusión Grover crea una 'inversión sobre...
Se utiliza el algoritmo de Grover, entre otras cosas, para buscar un elemento yy\mathbf{y} en una lista desordenada de elementos [x0,x1,...,xn−1][x0,x1,...,xn−1][\mathbf{x}_0, \mathbf{x}_1, ..., \mathbf{x}_{n-1}] de longitud nnn . A pesar de que hay muchas preguntas aquí sobre este tema, todavía...
El algoritmo de búsqueda de Grover generalmente se habla en términos de encontrar una entrada marcada en una base de datos sin clasificar. Este es un formalismo natural que le permite aplicarse directamente a la búsqueda de soluciones a los problemas de NP (donde una buena solución se reconoce...
En la superficie, los algoritmos cuánticos tienen poco que ver con la informática clásica y P vs NP en particular: la resolución de problemas de NP con computadoras cuánticas no nos dice nada sobre las relaciones de estas clases de complejidad clásicas 1 . Por otro lado, la 'descripción...
Muchos artículos afirman que la simulación hamiltoniana es completa BQP (por ejemplo, la simulación hamiltoniana con una dependencia casi óptima de todos los parámetros y la simulación hamiltoniana por Qubitización ). Es fácil ver que la simulación hamiltoniana es difícil para BQP porque...
Daniel Sank mencionó en un comentario , respondiendo a (mi) opinión que la aceleración constante de en un problema que admite un algoritmo de tiempo polinómico es escasa, que10810810^8 La teoría de la complejidad está demasiado obsesionada con los límites de escalamiento de tamaño infinito. Lo...
Como resultado de una excelente respuesta a mi pregunta sobre el bogosort cuántico , me preguntaba cuál es el estado actual de los algoritmos cuánticos para la clasificación. Para ser precisos, la ordenación se define aquí como el siguiente problema: Dada una matriz AAA de enteros (no dude en...