Finding the disjointness of stabilizer codes is NP-complete

• URL: http://arxiv.org/abs/2108.04738v1
• Date: Tue, 10 Aug 2021 15:00:20 GMT
• Title: Finding the disjointness of stabilizer codes is NP-complete
• Authors: John Bostanci and Aleksander Kubica
• Abstract summary: 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.
• Score: 77.34726150561087
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The disjointness of a stabilizer code is a quantity used to constrain the level of the logical Clifford hierarchy attainable by transversal gates and constant-depth quantum circuits. We show that for any positive integer constant $c$, 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, concatenated codes and hypergraph product codes. We also describe numerical methods of finding the disjointness, which can be readily used to rule out the existence of any transversal gate implementing some non-Clifford logical operation in small stabilizer codes. Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.

Related papers

• QGPU: Parallel logic in quantum LDPC codes [1.9960650656921184]
  Quantum low-density parity-check codes are a resource-efficient alternative to surface codes.<n>Key challenge is that logical qubits do not necessarily map to disjoint sets of physical qubits.<n>We introduce clustered-cyclic codes, a quantum low-density parity-check code family with finite-size instances.
  arXiv  Detail & Related papers  (2026-03-05T17:26:00Z)
• Non-Abelian qLDPC: TQFT Formalism, Addressable Gauging Measurement and Application to Magic State Fountain on 2D Product Codes [1.1087735229999818]
  We show that native non-Clifford logical gates can be realized using constant-rate 2D hypergraph-product codes and their Clifford-stabilizer variants.<n>This is achieved by a spacetime path integral effectively implementing the addressable gauging measurement of a new type of 0-form subcomplex symmetries.
  arXiv  Detail & Related papers  (2026-01-11T01:20:36Z)
• Logical gates on Floquet codes via folds and twists [45.88028371034407]
  We show how two techniques from static quantum error-correcting codes can be implemented on Floquet codes.<n>First, we present a way of implementing fold-transversal operations on Floquet codes in order to yield logical Hadamard and S gates.<n>Second, we present a way of implementing logical CNOT gates on Floquet codes via Dehn twists.
  arXiv  Detail & Related papers  (2025-12-19T19:00:06Z)
• Average-Case Complexity of Quantum Stabilizer Decoding [42.770940323689445]
  We prove that decoding a random stabilizer code with even a single logical qubit is at least as hard as decoding a random classical code at constant rate.<n>This result suggests that the easiest random quantum decoding problem is at least as hard as the hardest random classical decoding problem.
  arXiv  Detail & Related papers  (2025-09-25T03:04:40Z)
• No-go theorems for logical gates on product quantum codes [5.529881798520845]
  Homological products of codes offer a versatile framework for quantum error-correcting codes.<n>We show that non-Clifford logical gates cannot be implemented accessiblely on hypergraph product codes.
  arXiv  Detail & Related papers  (2025-07-22T17:46:45Z)
• Parallel Logical Measurements via Quantum Code Surgery [42.95092131256421]
  Quantum code surgery is a flexible and low overhead technique for performing logical measurements on quantum error-correcting codes.<n>We present a code surgery scheme, applicable to any qubit stabiliser low-density parity check (LDPC) code, that fault-tolerantly measures many logical Pauli operators in parallel.
  arXiv  Detail & Related papers  (2025-03-06T22:05:52Z)
• Universal quantum computation via scalable measurement-free error correction [45.29832252085144]
  We show that universal quantum computation can be made fault-tolerant in a scenario where the error-correction is implemented without mid-circuit measurements.<n>We introduce a measurement-free deformation protocol of the Bacon-Shor code to realize a logical $mathitCCZ$ gate.<n>In particular, our findings support that below-breakeven logical performance is achievable with a circuit-level error rate below $10-3$.
  arXiv  Detail & Related papers  (2024-12-19T18:55:44Z)
• Targeted Clifford logical gates for hypergraph product codes [61.269295538188636]
  We construct explicit targeted logical gates for hypergraph product codes. As a concrete example, we give logical circuits for the $[[18,2,3]]$ toric code.
  arXiv  Detail & Related papers  (2024-11-26T02:32:44Z)
• Measurement-free code-switching for low overhead quantum computation using permutation invariant codes [6.281229317487581]
  We present a measurement-free code-switching protocol for universal quantum computation. The novel non-Clifford gates enabled by this code-switching protocol enable implementation of a universal gate set more efficient than the Clifford$+T$ gate set.
  arXiv  Detail & Related papers  (2024-11-20T09:16:07Z)
• Transversal non-Clifford gates for quantum LDPC codes on sheaves [1.0878040851638]
  A major goal in quantum computing is to build a fault-tolerant quantum computer. One approach involves quantum low-density parity-check (qLDPC) codes that support non-Clifford gates.
  arXiv  Detail & Related papers  (2024-10-18T17:31:19Z)
• Geometric structure and transversal logic of quantum Reed-Muller codes [51.11215560140181]
  In this paper, we aim to characterize the gates of quantum Reed-Muller (RM) codes by exploiting the well-studied properties of their classical counterparts. A set of stabilizer generators for a RM code can be described via $X$ and $Z$ operators acting on subcubes of particular dimensions.
  arXiv  Detail & Related papers  (2024-10-10T04:07:24Z)
• Toward Constructing a Continuous Logical Operator for Error-Corrected Quantum Sensing [0.0]
  Operations on logical qubits are only performed through universal gate sets consisting of finite-sized gates such as Clifford+T. The Eastin-Knill theorem prevents a continuous signal from being both fault tolerant to local errors and transverse. A protocol to design continuous logical z-rotations is proposed and applied to the Steane Code.
  arXiv  Detail & Related papers  (2023-04-30T18:22:34Z)
• 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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Transversal Injection: A method for direct encoding of ancilla states for non-Clifford gates using stabiliser codes [55.90903601048249]
  We introduce a protocol to potentially reduce this overhead for non-Clifford gates. Preliminary results hint at high quality fidelities at larger distances.
  arXiv  Detail & Related papers  (2022-11-18T06:03:10Z)
• A Quantum Algorithm for Computing All Diagnoses of a Switching Circuit [73.70667578066775]
  Faults are by nature while most man-made systems, and especially computers, work deterministically. This paper provides such a connecting via quantum information theory which is an intuitive approach as quantum physics obeys probability laws.
  arXiv  Detail & Related papers  (2022-09-08T17:55:30Z)
• Finite-rate sparse quantum codes aplenty [1.1279808969568252]
  We introduce a methodology for generating random multi-qubit stabilizer codes based on solving a constraint satisfaction problem (CSP) on random bipartite graphs. Using a state-of-the-art CSP solver, we obtain convincing evidence for the existence of a satisfiability threshold. We observe that the sparse codes found in the satisfiable phase practically achieve the channel capacity for erasure noise.
  arXiv  Detail & Related papers  (2022-07-07T20:39:39Z)
• Partitioning qubits in hypergraph product codes to implement logical gates [0.0]
  Transversal gates are the simplest type of fault-tolerant logical gates. We show that gates can be used as the basis for universal quantum computing on LDPC codes.
  arXiv  Detail & Related papers  (2022-04-22T16:45:19Z)

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.