Lovász Meets Lieb-Schultz-Mattis: Complexity in Approximate Quantum Error Correction

• URL: http://arxiv.org/abs/2510.04453v1
• Date: Mon, 06 Oct 2025 03:00:43 GMT
• Title: Lovász Meets Lieb-Schultz-Mattis: Complexity in Approximate Quantum Error Correction
• Authors: Jinmin Yi, Ruizhi Liu, Zhi Li,
• Abstract summary: We reveal a tension between the error-correcting power of an AQEC and the hardness of code state preparation.<n>We show that short-range entangled states must be distinguishable via a local operator.<n>Our framework also provides a novel perspective for systems with Lieb-Schultz-Mattis type constraints.
• Score: 3.614650093702117
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Approximate quantum error correction (AQEC) provides a versatile framework for both quantum information processing and probing many-body entanglement. We reveal a fundamental tension between the error-correcting power of an AQEC and the hardness of code state preparation. More precisely, through a novel application of the Lov\'asz local lemma, we establish a fundamental trade-off between local indistinguishability and circuit complexity, showing that orthogonal short-range entangled states must be distinguishable via a local operator. These results offer a powerful tool for exploring quantum circuit complexity across diverse settings. As applications, we derive stronger constraints on the complexity of AQEC codes with transversal logical gates and establish strong complexity lower bounds for W state preparation. Our framework also provides a novel perspective for systems with Lieb-Schultz-Mattis type constraints.

Related papers

• Quantum-Efficient Reinforcement Learning Solutions for Last-Mile On-Demand Delivery [1.8262547855491453]
  We investigate quantum computing to solve the large-scale Capacitated Pickup and Delivery Problem with Time Windows.<n>A novel problem-specific encoding quantum circuit with an entangling and variational layer is proposed.
  arXiv  Detail & Related papers  (2025-08-07T13:50:43Z)
• Minor Embedding for Quantum Annealing with Reinforcement Learning [10.787328610467801]
  Reinforcement Learning (RL) offers a promising alternative by treating minor embedding as a sequential decision-making problem.<n>We propose a RL-based approach to minor embedding using a Proximal Policy Optimization agent, testing its ability to embed both fully connected and randomly generated problem.<n>Our proposed approach is also able to scale to moderate problem sizes and adapts well to different graph structures, highlighting RL's potential as a flexible and general-purpose framework.
  arXiv  Detail & Related papers  (2025-07-21T18:54:15Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Comparative study of quantum error correction strategies for the heavy-hexagonal lattice [41.94295877935867]
  Topological quantum error correction is a milestone in the scaling roadmap of quantum computers.<n>The square-lattice surface code has become the workhorse to address this challenge.<n>In some platforms, however, the connectivities are kept even lower in order to minimise gate errors.
  arXiv  Detail & Related papers  (2024-02-03T15:28:27Z)
• Complexity and order in approximate quantum error-correcting codes [1.1999555634662633]
  We establish rigorous connections between quantum circuit complexity and approximate quantum error correction (AQEC) properties. Our key finding is that if the subsystem variance is below an $O(k/n)$ threshold then any state in the code subspace must obey certain circuit complexity lower bounds. This theory of AQEC provides a versatile framework for understanding the quantum complexity and order of many-body quantum systems.
  arXiv  Detail & Related papers  (2023-10-07T07:03:46Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [88.57261102552016]
  The anticipated applications of quantum computers span across science and industry.<n>We present a survey of several potential application areas of quantum algorithms.<n>We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Unitary Complexity and the Uhlmann Transformation Problem [39.6823854861458]
  We introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes.<n>We use this framework to study the complexity of transforming one entangled state into another via local operations.<n>Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.
  arXiv  Detail & Related papers  (2023-06-22T17:46:39Z)
• Learning marginals suffices! [14.322753787990036]
  We investigate the relationship between the sample complexity of learning a quantum state and the circuit complexity of the state. We show that learning its marginals for the quantum state with low circuit complexity suffices for state tomography.
  arXiv  Detail & Related papers  (2023-03-15T21:09:29Z)
• Quantum process tomography of continuous-variable gates using coherent states [49.299443295581064]
  We demonstrate the use of coherent-state quantum process tomography (csQPT) for a bosonic-mode superconducting circuit. We show results for this method by characterizing a logical quantum gate constructed using displacement and SNAP operations on an encoded qubit.
  arXiv  Detail & Related papers  (2023-03-02T18:08:08Z)
• Logical blocks for fault-tolerant topological quantum computation [55.41644538483948]
  We present a framework for universal fault-tolerant logic motivated by the need for platform-independent logical gate definitions. We explore novel schemes for universal logic that improve resource overheads. Motivated by the favorable logical error rates for boundaryless computation, we introduce a novel computational scheme.
  arXiv  Detail & Related papers  (2021-12-22T19:00:03Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Quantum communication complexity beyond Bell nonlocality [87.70068711362255]
  Efficient distributed computing offers a scalable strategy for solving resource-demanding tasks. Quantum resources are well-suited to this task, offering clear strategies that can outperform classical counterparts. We prove that a new class of communication complexity tasks can be associated to Bell-like inequalities.
  arXiv  Detail & Related papers  (2021-06-11T18:00:09Z)

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.