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

• 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)
• Homological Quantum Rotor Codes: Logical Qubits from Torsion [51.9157257936691]
  homological quantum rotor codes allow one to encode both logical rotors and logical qudits in the same block of code. We show that the $0$-$pi$-qubit as well as Kitaev's current-mirror qubit are indeed small examples of such codes.
  arXiv  Detail & Related papers  (2023-03-24T00:29:15Z)
• 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.