Conjetura NLTS

En la teoría de la información cuántica , la conjetura de ausencia de estados triviales de baja energía (NLTS) es una cota inferior para la complejidad de ciertas clases de estados cuánticos, conjeturada por Michael Freedman y Matthew Hastings en 2013. ^{[ 1 ]} En parte, se pretendía que fuera una consecuencia más débil de un teorema PCP cuántico conjetural , que sería más fácil de demostrar que un teorema PCP cuántico completo. ^{[ 2 ] [ 3 ] [ 4 ]}

Lior Eldar y Aram Harrow anunciaron inicialmente una solución a la conjetura NLTS en 2015 , pero fue modificada para demostrar una afirmación más débil tras descubrirse un error en la demostración. ^{[ 5 ]} En 2023, Anurag Anshu, Nikolas Breuckmann y Chinmay Nirkhe presentaron una demostración completa de la conjetura NLTS en STOC 2023. ^{[ 6 ]}

La teoría clásica de la NP-dificultad es adecuada para caracterizar problemas que probablemente no se puedan resolver en tiempo polinomial, pero no abarca algunas de las complejidades que surgen en escenarios más realistas. Por ejemplo, muchos problemas de optimización NP-difíciles tienen algoritmos de aproximación en tiempo polinomial , aunque a menudo existe un umbral de aproximación más allá del cual el problema se vuelve NP-difícil de resolver. Estos resultados de dificultad de aproximación se demuestran típicamente utilizando el teorema PCP clásico o bajo una suposición como la conjetura de juegos únicos , que caracteriza la aproximabilidad de muchos problemas de satisfacción de restricciones .

En el contexto cuántico, un análogo común de los problemas clásicos de satisfacción de restricciones es el problema del hamiltoniano local, que requiere la energía fundamental (el autovalor más bajo) de un hamiltoniano local cuántico. Se sabe que este problema es QMA -difícil y se espera que sea irresoluble incluso con algoritmos cuánticos de tiempo polinomial. Un análogo del teorema PCP para el problema del hamiltoniano local implicaría que la energía fundamental es QMA -difícil incluso para aproximarla, pero aún es conjetural. ^{[ 3 ]}

En 2012, Hastings observó que la conjetura PCP cuántica implica que existen hamiltonianos locales cuánticos cuyos estados fundamentales no pueden prepararse mediante circuitos cuánticos pequeños , ya que de otro modo la aproximación de la energía fundamental estaría contenida en NP. Motivados por esta observación, Freedman y Hastings, en 2013, conjeturaron formalmente la existencia de tales hamiltonianos como la conjetura de ausencia de estados triviales de baja energía (NLTS). Interpretada de forma más física, la conjetura afirma que existen grandes sistemas cuánticos donde el entrelazamiento del estado fundamental persiste a temperaturas distintas de cero. ^{[ 7 ] [ 8 ]}

La conjetura NLTS afirma que existe una familia de hamiltonianos locales cuánticos que satisfacen la propiedad NLTS, la cual se define con mayor precisión a continuación.

Un hamiltoniano k -local  es una matriz hermitiana que actúa sobre n cúbits y que puede representarse como la suma de términos hamiltonianos que actúan sobre como máximo  cúbits cada uno: ${\displaystyle H}$${\displaystyle m}$${\displaystyle k}$

${\displaystyle H=\sum _{i=1}^{m}H_{i}.}$

El problema general del hamiltoniano k -local consiste en encontrar , dado un hamiltoniano k -local, el autovalor más pequeño de . ^{[ 9 ]} también se denomina energía del estado fundamental del hamiltoniano. ${\displaystyle H}$${\displaystyle \lambda }$${\displaystyle H}$${\displaystyle \lambda }$

La familia de hamiltonianos locales surge así del problema k -local. Kliesch establece la siguiente definición para hamiltonianos locales en el contexto de NLTS: ^{[ 3 ]}

Sea I ⊂ N un conjunto de índices. Una familia de hamiltonianos locales es un conjunto de hamiltonianos { H ^{( n )} }, n ∈ I , donde cada H ^{( n )} está definido en n subsistemas de dimensión finita (en lo sucesivo, considerados cúbits), que tienen la forma

${\displaystyle H^{(n)}=\sum _{n}H_{m}^{(n)},}$

donde cada H _m ^{( n )} actúa de manera no trivial sobre O (1) cúbits. Otra restricción es que la norma del operador de H _m ^{( n )} está limitada por una constante independiente de n y cada cúbit solo está involucrado en un número constante de términos H _m ^{( n )} .

En física , el orden topológico ^{[ 10 ]} es un tipo de orden en la fase de temperatura cero de la materia (también conocida como materia cuántica). En el contexto de NLTS, Kliesch afirma que "una familia de hamiltonianos locales con brecha se denomina topológicamente ordenada si ningún estado fundamental puede prepararse a partir de un estado producto mediante un circuito de profundidad constante". ^{[ 3 ]} Una versión informal de la conjetura NLTS afirma la existencia de hamiltonianos locales cuyos estados de baja energía están topológicamente ordenados.

Kliesch enuncia una versión más precisa de la propiedad NLTS de la siguiente manera: Sea I un conjunto infinito de tamaños de sistemas. Una familia de hamiltonianos locales { H ^{( n )} }, n ∈ I tiene la propiedad NLTS si existe ε > 0 y una función f  : N → N tal que

1. para todo n ∈ I , H ^{( n )} tiene energía fundamental 0,
2. ⟨0 ⁿ | U ^† H ^{( n )} U |0 ⁿ ⟩ > εn para cualquier circuito U de profundidad d que consta de dos compuertas de cúbits y para cualquier n ∈ I con n ≥ f ( d ). ^{[ 3 ]}

Existe una familia de hamiltonianos locales con la propiedad NLTS. ^{[ 3 ]}

Demostrar la conjetura NLTS es un obstáculo para resolver la conjetura qPCP, un teorema aún más difícil de probar. ^{[ 2 ]} La conjetura qPCP es un análogo cuántico del teorema PCP clásico. El teorema PCP clásico establece que los problemas de satisfacibilidad como 3SAT son NP-difíciles cuando se estima el número máximo de cláusulas que pueden satisfacerse simultáneamente en un sistema hamiltoniano . ^{[ 7 ]} En términos sencillos, el PCP clásico describe la complejidad casi infinita que implica predecir el resultado de un sistema con muchos estados de resolución, como un baño de agua lleno de cientos de imanes . ^{[ 8 ]} qPCP aumenta la complejidad al intentar resolver PCP para estados cuánticos . ^{[ 8 ]} Aunque aún no se ha demostrado, una prueba positiva de qPCP implicaría que el entrelazamiento cuántico en estados de Gibbs podría permanecer estable en estados de mayor energía por encima del cero absoluto . ^{[ 7 ]}

En 2015, Harrow y Eldar anunciaron una solución a la conjetura NLTS, que posteriormente fue modificada para demostrar el teorema más simple y débil de no estados triviales de bajo error (NLETS) después de que se descubriera un error. ^{[ 11 ]} Una formulación de NLETS se puede enunciar de la siguiente manera: ^{[ 11 ]}

Sea k > 1 un entero , y { H _n } _{n ∈ N} una familia de hamiltonianos k -locales. { H _n } _{n ∈ N} es NLETS si existe una constante ε > 0 tal que cualquier familia ε -impostora F = { ρ _n } _{n ∈ N} de { H _n } _{n ∈ N} no es trivial.

Nirkhe, Vazirani y Yuen dieron una demostración simplificada de NLETS en 2018. ^{[ 12 ]}

El teorema NLETS fue reforzado posteriormente en 2022 por Anshu y Breuckmann para demostrar que existe una familia de hamiltonianos donde cualquier estado que viole una pequeña fracción constante de términos locales debe tener una complejidad de circuito no trivial. ^{[ 13 ]}

La solución a la conjetura NLTS original construye una familia de hamiltonianos cuyos estados fundamentales son las palabras clave de un código estabilizador cuántico , que se sabe que son simulables clásicamente por el teorema de Gottesman-Knill . La construcción de hamiltonianos NLTS fue generalizada posteriormente por Coble, Coudron, Nelson y Nezhadi a hamiltonianos cuyo espacio de baja energía no contiene ni estados de complejidad de circuito trivial ni estados estabilizadores. ^{[ 14 ]}

Una conjetura más fuerte, introducida por Gharibian y Le Gall en 2021, afirma que existe una familia de hamiltonianos cuyo espacio de baja energía no contiene ningún estado cuya medición en la base computacional pueda simularse eficientemente mediante un algoritmo clásico. ^{[ 15 ]}