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

• Decoding Quasi-Cyclic Quantum LDPC Codes [23.22566380210149]
  Quantum low-density parity-check (qLDPC) codes are an important component in the quest for fault tolerance. Recent progress on qLDPC codes has led to constructions which are quantumally good, and which admit linear-time decoders to correct errors affecting a constant fraction of codeword qubits. In practice, the surface/toric codes, which are the product of two repetition codes, are still often the qLDPC codes of choice.
  arXiv  Detail & Related papers  (2024-11-07T06:25:27Z)
• List Decodable Quantum LDPC Codes [49.2205789216734]
  We give a construction of Quantum Low-Density Parity Check (QLDPC) codes with near-optimal rate-distance tradeoff. We get efficiently list decodable QLDPC codes with unique decoders.
  arXiv  Detail & Related papers  (2024-11-06T23:08:55Z)
• Decoding Quantum LDPC Codes Using Graph Neural Networks [52.19575718707659]
  We propose a novel decoding method for Quantum Low-Density Parity-Check (QLDPC) codes based on Graph Neural Networks (GNNs) The proposed GNN-based QLDPC decoder exploits the sparse graph structure of QLDPC codes and can be implemented as a message-passing decoding algorithm.
  arXiv  Detail & Related papers  (2024-08-09T16:47:49Z)
• Limitations of the decoding-to-LPN reduction via code smoothing [59.90381090395222]
  The Learning Parity with Noise (LPN) problem underlies several classic cryptographic primitives. This paper attempts to find a reduction from the decoding problem of linear codes, for which several hardness results exist. We characterize the efficiency of the reduction in terms of the parameters of the decoding and problems.
  arXiv  Detail & Related papers  (2024-08-07T12:54:43Z)
• 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.13422222472898]
  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)
• 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.