Hardness results for decoding the surface code with Pauli noise
- URL: http://arxiv.org/abs/2309.10331v3
- Date: Tue, 5 Mar 2024 18:16:17 GMT
- Title: Hardness results for decoding the surface code with Pauli noise
- Authors: Alex Fischer, Akimasa Miyake
- Abstract summary: We show that quantum maximum likelihood decoding (QMLD) and degenerate quantum maximum likelihood decoding (DQMLD) for the surface code are NP-hard and #P-hard, respectively.
We transform a formula into a qubit-dependent Pauli noise model and set of syndromes that encode the satisfiability properties of the formula.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Real quantum computers will be subject to complicated, qubit-dependent noise,
instead of simple noise such as depolarizing noise with the same strength for
all qubits. We can do quantum error correction more effectively if our decoding
algorithms take into account this prior information about the specific noise
present. This motivates us to consider the complexity of surface code decoding
where the input to the decoding problem is not only the syndrome-measurement
results, but also a noise model in the form of probabilities of single-qubit
Pauli errors for every qubit.
In this setting, we show that quantum maximum likelihood decoding (QMLD) and
degenerate quantum maximum likelihood decoding (DQMLD) for the surface code are
NP-hard and #P-hard, respectively. We reduce directly from SAT for QMLD, and
from #SAT for DQMLD, by showing how to transform a boolean formula into a
qubit-dependent Pauli noise model and set of syndromes that encode the
satisfiability properties of the formula. We also give hardness of
approximation results for QMLD and DQMLD. These are worst-case hardness results
that do not contradict the empirical fact that many efficient surface code
decoders are correct in the average case (i.e., for most sets of syndromes and
for most reasonable noise models). These hardness results are nicely analogous
with the known hardness results for QMLD and DQMLD for arbitrary stabilizer
codes with independent $X$ and $Z$ noise.
Related papers
- Optimized Noise Suppression for Quantum Circuits [0.46040036610482665]
Current quantum computation hardware suffers from noise and is too small for error correction.
Here, we efficiently characterize and mitigate crosstalk noise, which is a severe error source in, e.g., cross-resonance based superconducting quantum processors.
After characterization, we mitigate noise in quantum circuits by a noise-aware qubit routing algorithm.
arXiv Detail & Related papers (2024-01-12T07:34:59Z) - Testing the Accuracy of Surface Code Decoders [55.616364225463066]
Large-scale, fault-tolerant quantum computations will be enabled by quantum error-correcting codes (QECC)
This work presents the first systematic technique to test the accuracy and effectiveness of different QECC decoding schemes.
arXiv Detail & Related papers (2023-11-21T10:22:08Z) - Q-Pandora Unboxed: Characterizing Noise Resilience of Quantum Error
Correction Codes [2.348041867134616]
Quantum error correction codes (QECCs) are critical for realizing reliable quantum computing by protecting fragile quantum states against noise and errors.
This paper conducts a comprehensive study analyzing two QECCs under different error types and noise models using simulations.
rotated surface codes perform best with higher thresholds attributed to simplicity and lower qubit overhead.
arXiv Detail & Related papers (2023-08-05T02:24:55Z) - The END: An Equivariant Neural Decoder for Quantum Error Correction [73.4384623973809]
We introduce a data efficient neural decoder that exploits the symmetries of the problem.
We propose a novel equivariant architecture that achieves state of the art accuracy compared to previous neural decoders.
arXiv Detail & Related papers (2023-04-14T19:46:39Z) - Modular decoding: parallelizable real-time decoding for quantum
computers [55.41644538483948]
Real-time quantum computation will require decoding algorithms capable of extracting logical outcomes from a stream of data generated by noisy quantum hardware.
We propose modular decoding, an approach capable of addressing this challenge with minimal additional communication and without sacrificing decoding accuracy.
We introduce the edge-vertex decomposition, a concrete instance of modular decoding for lattice-surgery style fault-tolerant blocks.
arXiv Detail & Related papers (2023-03-08T19:26:10Z) - Deep Quantum Error Correction [73.54643419792453]
Quantum error correction codes (QECC) are a key component for realizing the potential of quantum computing.
In this work, we efficiently train novel emphend-to-end deep quantum error decoders.
The proposed method demonstrates the power of neural decoders for QECC by achieving state-of-the-art accuracy.
arXiv Detail & Related papers (2023-01-27T08:16:26Z) - Improved decoding of circuit noise and fragile boundaries of tailored
surface codes [61.411482146110984]
We introduce decoders that are both fast and accurate, and can be used with a wide class of quantum error correction codes.
Our decoders, named belief-matching and belief-find, exploit all noise information and thereby unlock higher accuracy demonstrations of QEC.
We find that the decoders led to a much higher threshold and lower qubit overhead in the tailored surface code with respect to the standard, square surface code.
arXiv Detail & Related papers (2022-03-09T18:48:54Z) - Performance of teleportation-based error correction circuits for bosonic
codes with noisy measurements [58.720142291102135]
We analyze the error-correction capabilities of rotation-symmetric codes using a teleportation-based error-correction circuit.
We find that with the currently achievable measurement efficiencies in microwave optics, bosonic rotation codes undergo a substantial decrease in their break-even potential.
arXiv Detail & Related papers (2021-08-02T16:12:13Z) - Pauli channels can be estimated from syndrome measurements in quantum
error correction [0.7264378254137809]
We show that a stabilizer code can be used to estimate Pauli channels with correlations across a number of qubits given by the pure distance.
It also allows for measurement errors within the framework of quantum data-syndrome codes.
It is our hope that this work opens up interesting applications, such as the online adaptation of a decoder to time-varying noise.
arXiv Detail & Related papers (2021-07-29T18:01:10Z) - The XZZX Surface Code [2.887393074590696]
We show that a variant of the surface code -- the XZZX code -- offers remarkable performance for fault-tolerant quantum computation.
The error threshold of this code matches what can be achieved with random codes (hashing) for every single-qubit Pauli noise channel.
We show that it is possible to maintain all of these advantages when we perform fault-tolerant quantum computation.
arXiv Detail & Related papers (2020-09-16T18:00:01Z) - Efficiently computing logical noise in quantum error correcting codes [0.0]
We show that measurement errors on readout qubits manifest as a renormalization on the effective logical noise.
We derive general methods for reducing the computational complexity of the exact effective logical noise by many orders of magnitude.
arXiv Detail & Related papers (2020-03-23T19:40:56Z)
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.