Interaction locality and coding limits for energy-gap-protected universal adiabatic quantum computation: the surviving open core of the Jordan–Farhi–Shor questions

Jordan, Farhi, and Shor, in 'Error-correcting codes for adiabatic quantum computation' (Phys. Rev. A 74, 052322, 2006), introduced energy-gap protection: encode an adiabatic quantum computation in a quantum error-detecting code and add a stabilizer-based penalty Hamiltonian that raises the energy of any leakage out of the code space, producing a size-independent gap against local noise at the cost of raising the interaction locality to 4-local (one-qubit noise) or 6-local (two-qubit noise). That paper left open (i) whether a non-stabilizer 3-qubit single-error-detecting code with 2-local logical operations exists, (ii) whether computationally universal 3-local or 2-local adiabatic Hamiltonians with a constant gap against local noise exist, and (iii) the long-time open-system dynamics of the scheme beyond the initial-rate master-equation analysis. Of these, (i) is settled negatively by Rains's 1999 linear-programming bound on distance-2 quantum codes (no 2-dimensional code of length 3 and distance 2 exists in any formalism), (iii) is substantially resolved for Markovian environments at arbitrary times, and (ii) is partially resolved: a no-go excludes ground-space protection by commuting 2-local Hamiltonians, 2-local universal constructions exist with non-commuting penalties whose protection gaps shrink with system size, and a constant-gap 2-local commuting construction exists only in an excited-subspace paradigm for Hamiltonian simulation. The problem posed here is the surviving open core: a constant-gap, at-most-3-local, computationally universal ground-state protection against one-qubit local noise, protection against two-qubit local noise below the 6-local construction, and the open-system dynamics beyond the settled Markovian, weak-coupling regimes.

Background

Adiabatic quantum computation (AQC) is a model of quantum computing in which one prepares the ground state of an easily initialized Hamiltonian and slowly deforms it, $H(t/T)$ for $0\le t\le T$, into a final Hamiltonian whose ground state encodes the answer to a computational problem. The quantum adiabatic theorem guarantees that a closed system stays in the instantaneous ground state with high probability provided the total runtime $T$ is large compared with inverse powers of the energy gap between the ground state and the first excited state. AQC is polynomially equivalent in computational power to the standard circuit model, and universal computation is already possible with 2-local Hamiltonians, where a Hamiltonian on $n$ qubits is called $k$-local if it is a sum of tensor products of Pauli matrices each acting nontrivially on at most $k$ qubits; low locality models the few-body interactions that experimental platforms can implement. However, the adiabatic gap of most experimentally relevant constructions shrinks as an inverse polynomial in the problem size, so the 'inherent' noise resistance hoped for from the gap is limited: excitation by a thermal environment is suppressed only when the temperature shrinks along with the gap, which is hard to achieve experimentally.

Jordan, Farhi, and Shor (2006) proposed to strengthen this passive resistance with quantum error-detecting codes. A stabilizer code is a code space defined as the joint +1 eigenspace of an abelian group of commuting Pauli operators, its stabilizer generators; a Pauli error is detectable precisely when it anticommutes with at least one generator, because it then takes every codeword outside the code space. Their scheme encodes each computational qubit into a code block, replaces every Pauli operator of the desired computational Hamiltonian by its encoded (logical) counterpart to form $H_{SL}$, and adds a penalty Hamiltonian $H_P=-E_p\sum_i g_i$ built from the stabilizer generators $g_i$, so that any state pushed out of the code space costs energy at least $E_p$. Since $H_{SL}$ commutes with $H_P$, the computation runs unchanged inside the protected ground space, which now has a gap against local noise that does not shrink as the computation grows. Their 4-qubit stabilizer code (a $[[4,1,2]]$ code in the standard notation of length, encoded qubits, and distance, where the distance $d$ is the minimum number of qubits that must be altered to map one codeword back into the code space) detects every single-qubit Pauli error while its logical Pauli operators are 2-local, so a 2-local computational Hamiltonian becomes a 4-local protected Hamiltonian; the standard 5-qubit code, which detects all two-qubit errors (distance 3), has 3-local logical operators and yields a 6-local protected Hamiltonian. Coupling the encoded system weakly to a photon bath and using the master equation of Childs, Farhi, and Preskill, they showed that the initial transition rate out of the code space carries a Bose–Einstein factor that is exponentially small in $E_p/T$ at temperature $T$ and grows only polynomially in the number of qubits, so a fixed leakage probability requires $1/T$ to grow only logarithmically with system size — but the analysis concerns the initial instant and the weak-coupling regime only, and the authors acknowledge that the picture breaks down after sufficiently long times.

Within the stabilizer formalism these localities are optimal: the paper proves that no 3-qubit stabilizer code can detect all single-qubit errors, and that the 5-qubit code meets the quantum Singleton bound $n-k\ge 2(d-1)$, a general upper bound relating block length, encoded qubits, and distance, so it is optimal in qubit number. It then asks whether better codes exist outside the stabilizer formalism — a nonadditive code, written $((n,K,d))$ for a $K$-dimensional code of length $n$ and distance $d$ that is not equivalent to any stabilizer code — and, more broadly, whether the induced interaction locality of the protected Hamiltonian can be reduced at all without giving up the size-independent protection gap. The code part of this question is now closed: Rains's linear-programming bound for general distance-2 codes, published seven years before the source, implies that no 2-dimensional code of length 3 and distance 2 exists in any formalism, so the 3-qubit subquestion has a negative answer (see the problem statement). Later work introduced subsystem codes, a generalization in which the code space factors into a gauge subsystem, on which errors are tolerated and whose gauge generators need not commute with each other, and a protected logical subsystem; this relaxation lowers the achievable weight of penalty and logical operators, but the resulting penalty Hamiltonian need not commute with the encoded computation, and its protection gap may close with system size.

Problem Statement

The source questions of Jordan, Farhi, and Shor (2006), posed under a single common objective — determining the minimal physical resources (interaction locality, qubit overhead, penalty strength, and cooling requirement) that suffice to passively protect universal adiabatic quantum computation against local noise by energy-gap protection — are the following. The open problem is the surviving core, items (A), (B), and (C) below, which must be answered in the original generality and consistently with the settled results.

(0) Settled negatively (context). The source asks whether a 3-qubit quantum code — stabilizer or non-stabilizer (nonadditive) — exists that detects all single-qubit errors while still admitting 2-local encoded (logical) Pauli operations, so that block-encoding a 2-local Hamiltonian would yield a 3-local energy-gap-protected Hamiltonian. Rains's linear-programming bound for general distance-2 quantum codes (1999, predating the source) gives $K\le 1$ at length 3: no 2-dimensional code of length 3 and distance 2 exists in any formalism, so no such code exists, with or without 2-local logical operations. This bound delimits the search space for items (A) and (B).

(A) Does there exist a computationally universal adiabatic quantum computation that computes in the ground space of its encoded Hamiltonian — the setting of the source's scheme — whose protected Hamiltonian has interaction locality at most 3 (in particular, 2-local) and nevertheless exhibits a constant, size-independent protection gap against one-qubit local noise? Here 'constant gap' means a protection gap bounded below by a positive constant independent of the number of encoded qubits (as in the source's 4-local construction), and 'computationally universal' means able to encode arbitrary circuit-model quantum computations with at most polynomial overhead. The source's constructions raise the locality to 4-local while keeping the gap constant, and asked whether this induced locality can be reduced without losing the size-independent gap. Known results delimit but do not settle the question: ground-space protection by commuting 2-local Hamiltonians is impossible (Marvian and Lidar, 2014); non-commuting 2-local universal constructions exist but their protection gaps shrink with system size (Marvian and Lloyd, 2019; Singkanipa, Xia, and Lidar, 2025); and a constant-gap 2-local commuting construction is achieved only by encoding into an excited eigenspace for Hamiltonian simulation (Cao et al., 2024), which lies outside the ground-state adiabatic paradigm. Open: whether a non-commuting 2-local, or any at-most-3-local, ground-state universal construction with a size-independent gap exists, or whether a no-go theorem excludes all such low-locality ground-state encodings.

(B) Does computationally universal adiabatic quantum computation admit passive protection against two-qubit (local) noise with interaction locality below the 6-local of the source's distance-3 (5-qubit-code) construction, while keeping a constant, size-independent protection gap? Two-local commuting penalties cannot protect any eigenspace against two-qubit or higher-weight errors (the generalized no-go of Cao et al., 2024); constructions with 3-, 4-, or 5-local interactions, or with non-commuting 2-local penalties, at distance 3 remain open.

(C) For the open-system dynamics of the scheme, the source established only the suppression of the initial transition rate out of the encoded ground space, in the weak-coupling (perturbative) master-equation regime. Which features of this suppression persist at long times and in stronger-coupling regimes? Settled cases: Markovian baths at arbitrary times, for commuting penalties and total evolution time polynomial in system size (Lidar, 2019), and exact small-system dynamics with finite penalty (Bookatz, Farhi, and Zhou, 2015). Open: non-Markovian environments, strong-coupling (nonperturbative) bath regimes, quantitative limits on the total computation time before the suppressed leakage terms accumulate to non-negligible weight, and how the spectral structure of the encoded computational Hamiltonian interacts with the penalty-induced suppression in those regimes.

References

1. Stephen P. Jordan, Edward Farhi, and Peter W. Shor, 'Error-correcting codes for adiabatic quantum computation', Phys. Rev. A 74, 052322 (2006). DOI: 10.1103/PhysRevA.74.052322, arXiv:quant-ph/0512170. https://doi.org/10.1103/PhysRevA.74.052322
2. Eric M. Rains, 'Quantum codes of minimum distance two', IEEE Transactions on Information Theory 45(1), 266 (1999). DOI: 10.1109/18.746807, arXiv:quant-ph/9704043. https://doi.org/10.1109/18.746807
3. E. M. Rains, R. H. Hardin, P. W. Shor, and N. J. A. Sloane, 'A nonadditive quantum code', Phys. Rev. Lett. 79, 953 (1997). DOI: 10.1103/PhysRevLett.79.953. https://doi.org/10.1103/PhysRevLett.79.953
4. Andrew M. Childs, Edward Farhi, and John Preskill, 'Robustness of adiabatic quantum computation', Phys. Rev. A 65, 012322 (2001). DOI: 10.1103/PhysRevA.65.012322. https://doi.org/10.1103/PhysRevA.65.012322
5. Isaac L. Chuang, Andrew W. Cross, Graeme Smith, John A. Smolin, and Bei Zeng, 'Codeword stabilized quantum codes: Algorithm and structure', Journal of Mathematical Physics 50, 042109 (2009). DOI: 10.1063/1.3086833, arXiv:0803.3232. https://doi.org/10.1063/1.3086833
6. Wen-Tai Yen and Li-Yi Hsu, 'Optimal Nonadditive Quantum Error-Detecting Code', arXiv:0901.1353 (2009). DOI: 10.48550/arXiv.0901.1353. https://arxiv.org/abs/0901.1353
7. Kevin C. Young, Mohan Sarovar, and Robin Blume-Kohout, 'Error Suppression and Error Correction in Adiabatic Quantum Computation: Techniques and Challenges', Phys. Rev. X 3, 041013 (2013). DOI: 10.1103/PhysRevX.3.041013, arXiv:1307.5893. https://doi.org/10.1103/PhysRevX.3.041013
8. Mohan Sarovar and Kevin C. Young, 'Error suppression and error correction in adiabatic quantum computation: non-equilibrium dynamics', New J. Phys. 15, 125032 (2013). DOI: 10.1088/1367-2630/15/12/125032. https://doi.org/10.1088/1367-2630/15/12/125032
9. Iman Marvian and Daniel A. Lidar, 'Quantum error suppression with commuting Hamiltonians: Two local is too local', Phys. Rev. Lett. 113, 260504 (2014). DOI: 10.1103/PhysRevLett.113.260504. https://doi.org/10.1103/PhysRevLett.113.260504
10. Anand Ganti, Uzoma Onunkwo, and Kevin Young, 'Family of [[6k,2k,2]] codes for practical and scalable adiabatic quantum computation', Phys. Rev. A 89, 042313 (2014). DOI: 10.1103/PhysRevA.89.042313, arXiv:1309.1674. https://doi.org/10.1103/PhysRevA.89.042313
11. Adam D. Bookatz, Edward Farhi, and Leo Zhou, 'Error suppression in Hamiltonian-based quantum computation using energy penalties', Phys. Rev. A 92, 022317 (2015). DOI: 10.1103/PhysRevA.92.022317, arXiv:1407.1485. https://doi.org/10.1103/PhysRevA.92.022317
12. F. Pastawski, A. Kay, N. Schuch, and I. Cirac, 'Limitations of passive protection of quantum information', Quantum Information and Computation 10, 580 (2010). DOI: 10.26421/QIC10.7-8-3. https://doi.org/10.26421/QIC10.7-8-3
13. Seth Lloyd and Barbara M. Terhal, 'Adiabatic and Hamiltonian computing on a 2D lattice with simple two-qubit interactions', New J. Phys. 18, 023042 (2016). DOI: 10.1088/1367-2630/18/2/023042, arXiv:1509.01278. https://doi.org/10.1088/1367-2630/18/2/023042
14. Martin Leib, Peter Zoller, and Wolfgang Lechner, 'A transmon quantum annealer: decomposing many-body Ising constraints into pair interactions', Quantum Science and Technology 1, 015008 (2016). DOI: 10.1088/2058-9565/1/1/015008, arXiv:1604.02359. https://doi.org/10.1088/2058-9565/1/1/015008
15. Milad Marvian and Daniel A. Lidar, 'Error Suppression for Hamiltonian-Based Quantum Computation Using Subsystem Codes', Phys. Rev. Lett. 118, 030504 (2017). DOI: 10.1103/PhysRevLett.118.030504, arXiv:1606.03795. https://doi.org/10.1103/PhysRevLett.118.030504
16. Milad Marvian and Daniel A. Lidar, 'Error suppression for Hamiltonian quantum computing in Markovian environments', Phys. Rev. A 95, 032302 (2017). DOI: 10.1103/PhysRevA.95.032302, arXiv:1612.01633. https://doi.org/10.1103/PhysRevA.95.032302
17. Milad Marvian and Seth Lloyd, 'Robust universal Hamiltonian quantum computing using two-body interactions', arXiv:1911.01354 (2019). DOI: 10.48550/arXiv.1911.01354. https://arxiv.org/abs/1911.01354
18. Daniel A. Lidar, 'Arbitrary-time error suppression for Markovian adiabatic quantum computing using stabilizer subspace codes', Phys. Rev. A 100, 022326 (2019). DOI: 10.1103/PhysRevA.100.022326, arXiv:1904.12028. https://doi.org/10.1103/PhysRevA.100.022326
19. Yingkang Cao, Suying Liu, Haowei Deng, Zihan Xia, Xiaodi Wu, and Yu-Xin Wang, 'Robust analog quantum simulators by quantum error-detecting codes', arXiv:2412.07764 (2024). DOI: 10.48550/arXiv.2412.07764. https://arxiv.org/abs/2412.07764
20. Phattharaporn Singkanipa, Zihan Xia, and Daniel A. Lidar, 'Families of d=2 2D subsystem stabilizer codes for universal Hamiltonian quantum computation with two-body interactions', Quantum 9, 1821 (2025). DOI: 10.22331/q-2025-08-05-1821, arXiv:2412.06744. https://doi.org/10.22331/q-2025-08-05-1821