Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
NLTS conjecture
open-in-new
<h2 id="nlts-property">NLTS property</h2> <p>The NLTS property is the underlying set of constraints that forms the basis for the NLTS conjecture. </p> <h3>Definitions</h3> <h4>Local hamiltonians</h4> <p class="note">Main article: <a href="/facts/QMA/AtQsb09s">QMA § The_local_Hamiltonian_problem</a></p> <p class="note">See also: <a href="/facts/Hamiltonian_(quantum_mechanics)/5XwK2HmD">Hamiltonian (quantum mechanics)</a></p> <p>A <i>k</i>-local <a href="/facts/Hamiltonian_(quantum_mechanics)/5XwK2HmD">Hamiltonian (quantum mechanics)</a> H {\displaystyle H} is a <a href="/facts/Hermitian_matrix/qArPblYo">Hermitian matrix</a> acting on <i>n</i> qubits which can be represented as the sum of m {\displaystyle m} Hamiltonian terms acting upon at most k {\displaystyle k} qubits each: </p> H = ∑ i = 1 m H i . {\displaystyle H=\sum _{i=1}^{m}H_{i}.} <p>The general <i>k</i>-local Hamiltonian problem is, given a <i>k</i>-local Hamiltonian H {\displaystyle H} , to find the smallest eigenvalue λ {\displaystyle \lambda } of H {\displaystyle H} .<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a> λ {\displaystyle \lambda } is also called the <a href="/facts/Ground-state/ML7cfCug">ground-state</a> energy of the Hamiltonian. </p><p>The <i>family of local Hamiltonians</i> thus arises out of the <i>k</i>-local problem. Kliesch states the following as a definition for local Hamiltonians in the context of NLTS:<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> </p> <blockquote> <p>Let <i>I</i> ⊂ N be an index set. A family of local Hamiltonians is a set of Hamiltonians {<i>H</i>(<i>n</i>)}, <i>n</i> ∈ <i>I</i>, where each <i>H</i>(<i>n</i>) is defined on <i>n</i> finite-dimensional subsystems (in the following taken to be qubits), that are of the form </p> H ( n ) = ∑ n H m ( n ) , {\displaystyle H^{(n)}=\sum _{n}H_{m}^{(n)},} <p>where each <i>H</i><i>m</i>(<i>n</i>) acts non-trivially on <i>O</i>(1) qubits. Another constraint is the operator norm of <i>H</i><i>m</i>(<i>n</i>) is bounded by a constant independent of <i>n</i> and each qubit is only involved in a constant number of terms <i>H</i><i>m</i>(<i>n</i>). </p> </blockquote> <h4>Topological order</h4> <p class="note">Main article: <a href="/facts/Symmetry-protected_topological_order/h8CVbg1M">Symmetry-protected topological order</a></p> <p class="note">See also: <a href="/facts/Topological_order/EfEnKRSw">Topological order</a>, <a href="/facts/Periodic_table_of_topological_invariants/xpmFqV1S">Periodic table of topological invariants</a>, and <a href="/facts/Topological_insulator/pbrbxG9X">Topological insulator</a></p> <p>In <a href="/facts/Physics/a7aH2y08">physics</a>, <i><a href="/facts/Topological/2EqW47cU">topological</a> order</i><a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> is a kind of order in the zero-temperature <a href="/facts/Phase_of_matter/NkHXDdN3">phase of matter</a> (also known as quantum matter). In the context of NLTS, Kliesch states: "a family of local gapped Hamiltonians is called <i>topologically ordered</i> if any ground states cannot be prepared from a product state by a constant-depth circuit".<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> </p> <h4>NLTS property</h4> <p>Kliesch defines the NLTS property thus:<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a> </p> <blockquote> <p>Let <i>I</i> be an infinite set of system sizes. A family of local Hamiltonians {<i>H</i>(<i>n</i>)}, <i>n</i> ∈ <i>I</i> has the NLTS property if there exists <i>ε</i> > 0 and a function <i>f</i> : N → N such that </p> <ul><li>for all <i>n</i> ∈ <i>I</i>, <i>H</i>(<i>n</i>) has ground energy 0,</li> <li>⟨0<i>n</i>|<i>U</i>†<i>H</i>(<i>n</i>)<i>U</i>|0<i>n</i>⟩ > <i>εn</i> for any depth-<i>d</i> circuit <i>U</i> consisting of two qubit gates and for any <i>n</i> ∈ <i>I</i> with <i>n</i> ≥ <i>f</i>(<i>d</i>).</li></ul> </blockquote> <h4>NLTS conjecture</h4> <p>There exists a family of local Hamiltonians with the NLTS property.<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> </p> <h2 id="quantum-pcp-conjecture">Quantum PCP conjecture</h2> <p class="note">Main article: <a href="/facts/PCP_theorem/GwlBcYH6">PCP theorem</a></p> <p>Proving the NLTS conjecture is an <a href="/facts/Logical_consequence/AyDXp4dn">obstacle</a> for resolving the qPCP conjecture, an even harder theorem to prove.<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a> The qPCP conjecture is a quantum analogue of the classical PCP theorem. The classical PCP theorem states that <a href="/facts/Satisfiability/NkmQFgHB">satisfiability</a> problems like <a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">3SAT</a> are <a href="/facts/NP_(complexity)/6muUfVMI">NP-hard</a> when estimating the maximal number of clauses that can be simultaneously satisfied in a <a href="/facts/Hamiltonian_system/1jx7lA7t">hamiltonian system</a>.<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a> In layman's terms, classical PCP describes the near-infinite complexity involved in predicting the outcome of a system with many resolving states, such as a water bath full of hundreds of <a href="/facts/Magnet/vvrg6VSk">magnets</a>.<a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a> qPCP increases the complexity by trying to solve PCP for <a href="/facts/Quantum_state/7jbxd7Dx">quantum states</a>.<a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a> Though it hasn't been proven yet, a positive proof of qPCP would imply that quantum entanglement in <a href="/facts/Gibbs_state/AjusaYRo">Gibbs states</a> could remain stable at higher-energy states above <a href="/facts/Absolute_zero/U3UyPl2K">absolute zero</a>.<a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a> </p> <h2 id="nlets-proof">NLETS proof</h2> <p>NLTS on its own is difficult to prove, though a simpler no low-error trivial states (NLETS) theorem has been proven, and that proof is a precursor for NLTS.<a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a> </p><p>NLETS is defined as:<a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a> </p> Let <i>k</i> > 1 be some <a href="/facts/Integer/PUwwrawx">integer</a>, and {<i>H</i><i>n</i>}<i>n</i> ∈ N be a family of <i>k</i>-local Hamiltonians. {<i>H</i><i>n</i>}<i>n</i> ∈ N is NLETS if there exists a constant <i>ε</i> > 0 such that any <i>ε</i>-impostor family <i>F</i> = {<i>ρ</i><i>n</i>}<i>n</i> ∈ N of {<i>H</i><i>n</i>}<i>n</i> ∈ N is non-trivial. <h2 id="references">References</h2> <ol> <li id="fn:1"><p>"On the NLTS Conjecture". Simons Institute for the Theory of Computing. 2021-06-30. Retrieved 2022-08-07. <a href="https://simons.berkeley.edu/talks/nlts-conjecture" target="_blank">https://simons.berkeley.edu/talks/nlts-conjecture</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Kliesch, Alexander (2020-01-23). "The NLTS conjecture" (PDF). Technical University of Munich. Retrieved Aug 7, 2022. <a href="https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/HS_ResearchSemQIT2019/NLTSConjecture.pdf" target="_blank">https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/HS_ResearchSemQIT2019/NLTSConjecture.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Anshu, Anurag; Nirkhe, Chinmay (2020-11-01). Circuit lower bounds for low-energy states of quantum code Hamiltonians. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 215. pp. 6:1–6:22. arXiv:2011.02044. doi:10.4230/LIPIcs.ITCS.2022.6. ISBN 9783959772174. S2CID 226299885. <a href="9783959772174" target="_blank">9783959772174</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Freedman, Michael H.; Hastings, Matthew B. (January 2014). "Quantum Systems on Non-$k$-Hyperfinite Complexes: a generalization of classical statistical mechanics on expander graphs". Quantum Information and Computation. 14 (1&2): 144–180. arXiv:1301.1363. doi:10.26421/qic14.1-2-9. ISSN 1533-7146. S2CID 10850329. <a href="https://dx.doi.org/10.26421/qic14.1-2-9" target="_blank">https://dx.doi.org/10.26421/qic14.1-2-9</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Kliesch, Alexander (2020-01-23). "The NLTS conjecture" (PDF). Technical University of Munich. Retrieved Aug 7, 2022. <a href="https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/HS_ResearchSemQIT2019/NLTSConjecture.pdf" target="_blank">https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/HS_ResearchSemQIT2019/NLTSConjecture.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>"Circuit lower bounds for low-energy states of quantum code Hamiltonians". DeepAI. 2020-11-03. Retrieved 2022-08-07. <a href="https://deepai.org/publication/circuit-lower-bounds-for-low-energy-states-of-quantum-code-hamiltonians" target="_blank">https://deepai.org/publication/circuit-lower-bounds-for-low-energy-states-of-quantum-code-hamiltonians</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>"Circuit lower bounds for low-energy states of quantum code Hamiltonians". DeepAI. 2020-11-03. Retrieved 2022-08-07. <a href="https://deepai.org/publication/circuit-lower-bounds-for-low-energy-states-of-quantum-code-hamiltonians" target="_blank">https://deepai.org/publication/circuit-lower-bounds-for-low-energy-states-of-quantum-code-hamiltonians</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>"Computer Science Proof Lifts Limits on Quantum Entanglement". Quanta Magazine. 2022-07-18. Retrieved 2022-08-08. <a href="https://www.quantamagazine.org/computer-science-proof-lifts-limits-on-quantum-entanglement-20220718/" target="_blank">https://www.quantamagazine.org/computer-science-proof-lifts-limits-on-quantum-entanglement-20220718/</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>"Research Vignette: Quantum PCP Conjectures". Simons Institute for the Theory of Computing. 2014-09-30. Retrieved 2022-08-08. <a href="https://simons.berkeley.edu/news/research-vignette-qhc2014" target="_blank">https://simons.berkeley.edu/news/research-vignette-qhc2014</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>"Computer Science Proof Lifts Limits on Quantum Entanglement". Quanta Magazine. 2022-07-18. Retrieved 2022-08-08. <a href="https://www.quantamagazine.org/computer-science-proof-lifts-limits-on-quantum-entanglement-20220718/" target="_blank">https://www.quantamagazine.org/computer-science-proof-lifts-limits-on-quantum-entanglement-20220718/</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Anshu, Anurag; Breuckmann, Nikolas P.; Nirkhe, Chinmay (2023-06-02). "NLTS Hamiltonians from Good Quantum Codes". Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC 2023. New York, NY, USA: Association for Computing Machinery. pp. 1090–1096. arXiv:2206.13228. doi:10.1145/3564246.3585114. ISBN 978-1-4503-9913-5. <a href="978-1-4503-9913-5" target="_blank">978-1-4503-9913-5</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>Morimae, Tomoyuki; Takeuchi, Yuki; Nishimura, Harumichi (2018-11-15). "Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy". Quantum. 2: 106. arXiv:1711.10605. Bibcode:2018Quant...2..106M. doi:10.22331/q-2018-11-15-106. ISSN 2521-327X. S2CID 3958357. <a href="https://doi.org/10.22331%2Fq-2018-11-15-106" target="_blank">https://doi.org/10.22331%2Fq-2018-11-15-106</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Kliesch, Alexander (2020-01-23). "The NLTS conjecture" (PDF). Technical University of Munich. Retrieved Aug 7, 2022. <a href="https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/HS_ResearchSemQIT2019/NLTSConjecture.pdf" target="_blank">https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/HS_ResearchSemQIT2019/NLTSConjecture.pdf</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>Wen, Xiao-Gang (1990). "Topological Orders in Rigid States" (PDF). Int. J. Mod. Phys. B. 4 (2): 239. Bibcode:1990IJMPB...4..239W. CiteSeerX 10.1.1.676.4078. doi:10.1142/S0217979290000139. Archived from the original (PDF) on 2011-07-20. Retrieved 2009-04-09. <a href="/wiki/Xiao-Gang_Wen" target="_blank">/wiki/Xiao-Gang_Wen</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Kliesch, Alexander (2020-01-23). "The NLTS conjecture" (PDF). Technical University of Munich. Retrieved Aug 7, 2022. <a href="https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/HS_ResearchSemQIT2019/NLTSConjecture.pdf" target="_blank">https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/HS_ResearchSemQIT2019/NLTSConjecture.pdf</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>Kliesch, Alexander (2020-01-23). "The NLTS conjecture" (PDF). Technical University of Munich. Retrieved Aug 7, 2022. <a href="https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/HS_ResearchSemQIT2019/NLTSConjecture.pdf" target="_blank">https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/HS_ResearchSemQIT2019/NLTSConjecture.pdf</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Kliesch, Alexander (2020-01-23). "The NLTS conjecture" (PDF). Technical University of Munich. Retrieved Aug 7, 2022. <a href="https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/HS_ResearchSemQIT2019/NLTSConjecture.pdf" target="_blank">https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/HS_ResearchSemQIT2019/NLTSConjecture.pdf</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>"On the NLTS Conjecture". Simons Institute for the Theory of Computing. 2021-06-30. Retrieved 2022-08-07. <a href="https://simons.berkeley.edu/talks/nlts-conjecture" target="_blank">https://simons.berkeley.edu/talks/nlts-conjecture</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>"Research Vignette: Quantum PCP Conjectures". Simons Institute for the Theory of Computing. 2014-09-30. Retrieved 2022-08-08. <a href="https://simons.berkeley.edu/news/research-vignette-qhc2014" target="_blank">https://simons.berkeley.edu/news/research-vignette-qhc2014</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>"Computer Science Proof Lifts Limits on Quantum Entanglement". Quanta Magazine. 2022-07-18. Retrieved 2022-08-08. <a href="https://www.quantamagazine.org/computer-science-proof-lifts-limits-on-quantum-entanglement-20220718/" target="_blank">https://www.quantamagazine.org/computer-science-proof-lifts-limits-on-quantum-entanglement-20220718/</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>"Computer Science Proof Lifts Limits on Quantum Entanglement". Quanta Magazine. 2022-07-18. Retrieved 2022-08-08. <a href="https://www.quantamagazine.org/computer-science-proof-lifts-limits-on-quantum-entanglement-20220718/" target="_blank">https://www.quantamagazine.org/computer-science-proof-lifts-limits-on-quantum-entanglement-20220718/</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>"Research Vignette: Quantum PCP Conjectures". Simons Institute for the Theory of Computing. 2014-09-30. Retrieved 2022-08-08. <a href="https://simons.berkeley.edu/news/research-vignette-qhc2014" target="_blank">https://simons.berkeley.edu/news/research-vignette-qhc2014</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>Eldar, Lior (2017). "Local Hamiltonians Whose Ground States are Hard to Approximate" (PDF). IEEE Symposium on Foundations of Computer Science (FOCS). Retrieved Aug 7, 2022. <a href="http://ieee-focs.org/FOCS-2017-Papers/3464a427.pdf" target="_blank">http://ieee-focs.org/FOCS-2017-Papers/3464a427.pdf</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> <li id="fn:24"><p>Eldar, Lior (2017). "Local Hamiltonians Whose Ground States are Hard to Approximate" (PDF). IEEE Symposium on Foundations of Computer Science (FOCS). Retrieved Aug 7, 2022. <a href="http://ieee-focs.org/FOCS-2017-Papers/3464a427.pdf" target="_blank">http://ieee-focs.org/FOCS-2017-Papers/3464a427.pdf</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li> </ol>