A new approximate Eastin-Knill theorem
- URL: http://arxiv.org/abs/2505.00427v1
- Date: Thu, 01 May 2025 09:56:26 GMT
- Title: A new approximate Eastin-Knill theorem
- Authors: Rhea Alexander,
- Abstract summary: We show that a quantum error correcting code can support a universal set of gates and approximately correct for local erasure.<n>In particular, we show that a quantum error correcting code can support a universal set of gates if and only if the conditional min-entropy of the Choi state of the encoding and noise channel is upper bounded by a function of the worst-case error probability.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Transversal encoded gatesets are highly desirable for fault tolerant quantum computing. However, a quantum error correcting code which exactly corrects for local erasure noise and supports a universal set of transversal gates is ruled out by the Eastin-Knill theorem. Here we provide a new approximate Eastin-Knill theorem for the single-shot regime when we allow for some probability of error in the decoding. In particular, we show that a quantum error correcting code can support a universal set of transversal gates and approximately correct for local erasure if and only if the conditional min-entropy of the Choi state of the encoding and noise channel is upper bounded by a simple function of the worst-case error probability. Our no-go theorem can be computed by solving a semidefinite program, and, in the spirit of the original Eastin-Knill theorem, is formulated in terms of a condition that is both necessary and sufficient, ensuring achievability whenever it is passed. As an example, we find that with $n=100$ physical qutrits we can encode $k=1$ logical qubit in the $W$-state code, which admits a universal transversal set of gates and corrects for single subsystem erasure with error probability of $\varepsilon = 0.005$. To establish our no-go result, we leverage tools from the resource theory of asymmetry, where, in the single-shot regime, a single (output state-dependent) resource monotone governs all state purifications.
Related papers
- Universal transversal gates [0.0]
A long-standing challenge in quantum error correction is the infeasibility of universal gates, as shown by the Eastin-Knill theorem.
We obtain a necessary and sufficient condition for a quantum code to have universal gates and show that the Eastin-Knill no-go result is a special case that does not hold for a general error model.
arXiv Detail & Related papers (2024-10-09T16:34:47Z) - Approximate quantum error correcting codes from conformal field theory [0.0]
We consider generic 1+1D CFT codes under extensive local dephasing channels.
We show that a CFT code with continuous symmetry saturates a bound on the recovery fidelity for covariant codes.
arXiv Detail & Related papers (2024-06-13T19:40:36Z) - Fidelity-based distance bounds for $N$-qubit approximate quantum error
correction [0.0]
Eastin-Knill theorem states that a quantum code cannot correct errors exactly, possess continuous symmetries, and implement a universal set of gates transversely.
It is common to employ a complementary measure of fidelity as a way to quantify quantum state distinguishability and benchmark approximations in error correction.
We address two distance measures based on the sub- and superfidelities as a way to bound error approximations, which in turn require a lower computational cost.
arXiv Detail & Related papers (2022-12-08T16:10:58Z) - 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) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime.
For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially.
If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
arXiv Detail & Related papers (2021-11-29T19:26:28Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated.
Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform.
In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
arXiv Detail & Related papers (2020-11-24T18:44:57Z) - Fault-tolerant Coding for Quantum Communication [71.206200318454]
encode and decode circuits to reliably send messages over many uses of a noisy channel.
For every quantum channel $T$ and every $eps>0$ there exists a threshold $p(epsilon,T)$ for the gate error probability below which rates larger than $C-epsilon$ are fault-tolerantly achievable.
Our results are relevant in communication over large distances, and also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise.
arXiv Detail & Related papers (2020-09-15T15:10:50Z) - Optimal Universal Quantum Error Correction via Bounded Reference Frames [8.572932528739283]
Error correcting codes with a universal set of gates are a desideratum for quantum computing.
We show that our approximate codes are capable of efficiently correcting different types of erasure errors.
Our approach has implications for fault-tolerant quantum computing, reference frame error correction, and the AdS-CFT duality.
arXiv Detail & Related papers (2020-07-17T18:00:03Z) - Using Quantum Metrological Bounds in Quantum Error Correction: A Simple
Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
We present a proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code with its ability to achieve a universal set of logical gates.
Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols.
arXiv Detail & Related papers (2020-04-24T17:58:10Z) - Rigorous measurement error correction [0.0]
We review an experimental technique used to correct state preparation and measurement errors on gate-based quantum computers.
We show how to obtain $Gamma$ from gate set tomography and apply the error correction technique to single IBM Q superconducting qubits.
arXiv Detail & Related papers (2020-02-04T18:58:06Z)
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.