Circuit-to-Hamiltonian approximate code

Circuit-to-Hamiltonian approximate code[1]

Description

Approximate qubit block code that forms the ground-state space of a frustration-free Hamiltonian with non-commuting terms. Its distance and logical-qubit number are both of order \(\Omega(n/\log^5 n)\) [1; Thm. 3.1]. The code is an approximate non-stabilizer QLWC code since the Hamiltonian consists of non-commuting weight-ten non-Pauli projectors, with each qubit acted on by order \(O(\text{polylog}(n)\) projectors.

The code is constructed by converting the encoding circuit of a Brown-Fawzi random Clifford-circuit code into a Hamiltonian using the spacetime circuit-to-Hamiltonian construction [2,3] (a generalization of the Feynman-Kitaev clock construction [4]). The ground-state subspace of this Hamiltonian is the \(\epsilon\)-approximate code with infidelity of recovery \(\epsilon = O(1/\text{polylog}(n))\).

Using Markov-chain techniques, the gap of the Hamiltonian can be proven to be of order \(\Omega(D^{-2}n^{-3.09}\log^{-6} n)\) for an \(n\)-qubit input circuit of depth \(D\).

Protection

Circuit-to-Hamiltonian approximate codes have nontrivial codespace complexity [5].

Encoding

There exists a circuit of size polynomial in \(n\) whose terms act on at most \(\log (n)+2\) qubits [1; Thm. 3.3].

Decoding

Local detection of Pauli errors can be done using circuits of depth \(O(\text{polylog}(n))\) based on exact decoders for the Brown-Fawzi code [1; Lemma 3.2].

Parents

Qubit code
Approximate quantum error-correcting code (AQECC)
Frustration-free Hamiltonian code — Circuit-to-Hamiltonian approximate codes form the ground-state space of a frustration-free non-commuting projector Hamiltonian whose projectors are constant weight, but such that each physical qubit is acted on by order \(O(\text{polylog}(n))\) projectors.

Cousins

Quantum low-weight check (QLWC) code — The circuit-to-Hamiltonian code construction yields approximate codes whose distance and logical-qubit number are both of order \(\Omega(n/\log^5 n)\) [1; Thm. 3.1]. These codes are approximate non-stabilizer QLWC codes since the Hamiltonian consists of non-commuting weight-ten non-Pauli projectors, with each qubit acted on by order \(O(\text{polylog}(n)\) projectors.
Brown-Fawzi random Clifford-circuit code — Circuit-to-Hamiltonian approximate codes are constructed by converting the encoding circuit of a Brown-Fawzi random Clifford-circuit code into a Hamiltonian using the spacetime circuit-to-Hamiltonian construction [2,3].

References

[1]: T. C. Bohdanowicz, E. Crosson, C. Nirkhe, and H. Yuen, “Good approximate quantum LDPC codes from spacetime circuit Hamiltonians”, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (2019) arXiv:1811.00277 DOI
[2]: A. Mizel, D. A. Lidar, and M. Mitchell, “Simple Proof of Equivalence between Adiabatic Quantum Computation and the Circuit Model”, Physical Review Letters 99, (2007) arXiv:quant-ph/0609067 DOI
[3]: N. P. Breuckmann and B. M. Terhal, “Space-time circuit-to-Hamiltonian construction and its applications”, Journal of Physics A: Mathematical and Theoretical 47, 195304 (2014) arXiv:1311.6101 DOI
[4]: A. Kitaev, A. Shen, and M. Vyalyi, Classical and Quantum Computation (American Mathematical Society, 2002) DOI
[5]: J. Yi, W. Ye, D. Gottesman, and Z.-W. Liu, “Complexity and order in approximate quantum error-correcting codes”, Nature Physics (2024) arXiv:2310.04710 DOI

Page edit log

Victor V. Albert (2024-05-27) — most recent

Cite as:

“Circuit-to-Hamiltonian approximate code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/circuit_to_hamiltonian

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/qubits/nonstabilizer/circuit_to_hamiltonian.yml.