NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate
Quantum LDPC Codes
- URL: http://arxiv.org/abs/2311.09503v1
- Date: Thu, 16 Nov 2023 01:58:00 GMT
- Title: NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate
Quantum LDPC Codes
- Authors: Louis Golowich and Tali Kaufman
- Abstract summary: We show improvements to the NLTS (No Low-Energy Trivial States) theorem and explicit lower bounds against a linear number of levels of the Sum-of-Squares hierarchy.
We introduce a new method of planting a strongly explicit nontrivial codeword in linear-distance qLDPC codes, which in turn yields strongly explicit SoS lower bounds.
- Score: 0.7088856621650764
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent constructions of the first asymptotically good quantum LDPC (qLDPC)
codes led to two breakthroughs in complexity theory: the NLTS (No Low-Energy
Trivial States) theorem (Anshu, Breuckmann, and Nirkhe, STOC'23), and explicit
lower bounds against a linear number of levels of the Sum-of-Squares (SoS)
hierarchy (Hopkins and Lin, FOCS'22).
In this work, we obtain improvements to both of these results using qLDPC
codes of low rate:
- Whereas Anshu et al. only obtained NLTS Hamiltonians from qLDPC codes of
linear dimension, we show the stronger result that qLDPC codes of arbitrarily
small positive dimension yield NLTS Hamiltonians.
- The SoS lower bounds of Hopkins and Lin are only weakly explicit because
they require running Gaussian elimination to find a nontrivial codeword, which
takes polynomial time. We resolve this shortcoming by introducing a new method
of planting a strongly explicit nontrivial codeword in linear-distance qLDPC
codes, which in turn yields strongly explicit SoS lower bounds.
Our "planted" qLDPC codes may be of independent interest, as they provide a
new way of ensuring a qLDPC code has positive dimension without resorting to
parity check counting, and therefore provide more flexibility in the code
construction.
Related papers
- Factor Graph Optimization of Error-Correcting Codes for Belief Propagation Decoding [62.25533750469467]
Low-Density Parity-Check codes possess several advantages over other families of codes.
The proposed approach is shown to outperform the decoding performance of existing popular codes by orders of magnitude.
arXiv Detail & Related papers (2024-06-09T12:08:56Z) - Belief Propagation Decoding of Quantum LDPC Codes with Guided Decimation [55.8930142490617]
We propose a decoder for QLDPC codes based on BP guided decimation (BPGD)
BPGD significantly reduces the BP failure rate due to non-convergence.
arXiv Detail & Related papers (2023-12-18T05:58:07Z) - Semidefinite programming bounds on the size of entanglement-assisted
codeword stabilized quantum codes [5.770351255180495]
We use the isotropic subgroup of the CWS group and the set of word operators of a CWS-type quantum code to derive an upper bound on the minimum distance.
This characterization can be incorporated into the associated distance enumerators, enabling us to construct semidefinite constraints.
We illustrate several instances where SDP bounds outperform LP bounds, and there are even cases where LP fails to yield meaningful results.
arXiv Detail & Related papers (2023-11-13T07:01:58Z) - Hierarchical memories: Simulating quantum LDPC codes with local gates [0.05156484100374058]
Constant-rate low-density parity-check (LDPC) codes are promising candidates for constructing efficient fault-tolerant quantum memories.
We construct a new family of hierarchical codes, that encode a number of logical qubits K = Omega(N/log(N)2.
Under conservative assumptions, we find that the hierarchical code outperforms the basic encoding where all logical qubits are encoded in the surface code.
arXiv Detail & Related papers (2023-03-08T18:48:12Z) - Neural Belief Propagation Decoding of Quantum LDPC Codes Using
Overcomplete Check Matrices [60.02503434201552]
We propose to decode QLDPC codes based on a check matrix with redundant rows, generated from linear combinations of the rows in the original check matrix.
This approach yields a significant improvement in decoding performance with the additional advantage of very low decoding latency.
arXiv Detail & Related papers (2022-12-20T13:41:27Z) - Symbolic Distillation for Learned TCP Congestion Control [70.27367981153299]
TCP congestion control has achieved tremendous success with deep reinforcement learning (RL) approaches.
Black-box policies lack interpretability and reliability, and often, they need to operate outside the traditional TCP datapath.
This paper proposes a novel two-stage solution to achieve the best of both worlds: first, to train a deep RL agent, then distill its NN policy into white-box, light-weight rules.
arXiv Detail & Related papers (2022-10-24T00:58:16Z) - Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
We show that the problem of calculating the $c-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete.
We provide bounds on the disjointness for various code families, including the CSS codes,$d codes and hypergraph codes.
Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.
arXiv Detail & Related papers (2021-08-10T15:00:20Z) - Sample Efficient Reinforcement Learning In Continuous State Spaces: A
Perspective Beyond Linearity [50.38337893712897]
We introduce the Effective Planning Window (EPW) condition, a structural condition on MDPs that makes no linearity assumptions.
We demonstrate that the EPW condition permits sample efficient RL, by providing an algorithm which provably solves MDPs satisfying this condition.
We additionally show the necessity of conditions like EPW, by demonstrating that simple MDPs with slight nonlinearities cannot be solved sample efficiently.
arXiv Detail & Related papers (2021-06-15T00:06:59Z) - Circuit lower bounds for low-energy states of quantum code Hamiltonians [17.209060627291315]
We prove circuit lower bounds for all low-energy states of local Hamiltonians arising from quantum error-correcting codes.
We show that low-depth states cannot accurately approximate the ground-energy even in physically relevant systems.
arXiv Detail & Related papers (2020-11-03T22:36:22Z) - Single-Shot Decoding of Linear Rate LDPC Quantum Codes with High
Performance [5.33024001730262]
We construct and analyze a family of low-density parity check (LDPC) quantum codes with a linear encoding rate, scaling distance and efficient decoding schemes.
The code family is based on tessellations of closed, four-dimensional, hyperbolic, as first suggested by Guth and Lubotzky.
arXiv Detail & Related papers (2020-01-10T17:21:27Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.