Learning Clifford-structured quantum unitaries and Hamiltonians

AI summary

Overview

Research area: Quantum learning theory and quantum process tomography — specifically, learning algorithms for quantum unitaries and Hamiltonians that are structured with respect to the Clifford group rather than the Pauli basis.

Technical level: Advanced. The paper is a theoretical computer science / quantum information result built on stabilizer-state formalism, Choi-state isomorphisms, entanglement entropy, and quasipolynomial-time algorithm analysis. Readers should be comfortable with Clifford circuits, stabilizer states, and fidelity/norm measures on operators.

Scope (one sentence): The paper gives a proper, quasipolynomial-time agnostic tomography algorithm for Clifford unitaries and uses it to build tomography protocols for unitaries and Hamiltonians that are dense in the Pauli basis but have bounded Clifford extent or Clifford rank.

What This Paper Is About

Most efficient tomography algorithms for quantum dynamics assume the unknown process is local or sparse when written as a sum of Pauli operators. This paper instead studies processes that may have exponentially many nonzero Pauli coefficients but still admit a short description as a linear combination of Clifford unitaries, with bounded Clifford extent (the sum of the absolute values of the coefficients).

The goal is twofold: first, to learn the Clifford unitary closest to an arbitrary unknown unitary (agnostic tomography), and second, to use that primitive to reconstruct unitaries and Hamiltonians that are dense in the Pauli basis yet concise over Cliffords.

Key Contributions

1. Proper agnostic tomography of Clifford unitaries (Theorem 1.1). Given query access to an unknown n-qubit unitary U with optimal Clifford fidelity opt, the algorithm outputs an actual Clifford unitary V (not an arbitrary state or operator) satisfying |⟨⟨U|V⟩⟩|² ≥ opt − ε with probability at least 1 − δ. Query and time complexity is poly(n, (1/ε)^{log(1/ε)}, log(1/δ)). The authors state this resolves an open question on proper agnostic tomography of Cliffords; prior work gave only an improper algorithm whose output need not be a Clifford or even unitary.

2. Tomography of unitaries with bounded Clifford extent (Corollary 4.3). For an unknown unitary U with Clifford extent ≤ ξ, the algorithm outputs an operator V with Clifford rank O(ξ²/ε²) such that min over θ of ‖V − e^{iθ}U‖ (normalized Frobenius norm) ≤ ε, with complexity poly(n, (ξ/ε)^{log(ξ/ε)}, log(1/δ)). The output is a linear operator that need not be unitary, so this protocol is not proper.

3. Tomography of Hamiltonians with bounded Clifford extent (Theorem 4.4). Given query access to exp(−iHt) for a Hamiltonian H with Clifford extent ≤ ξ and Tr(H) = 0, the algorithm outputs Ĥ with Clifford rank O(ξ⁴/ε⁴) satisfying ‖Ĥ − H‖ ≤ ε in normalized Frobenius norm, using poly(n, (ξ/ε)^{log(ξ/ε)}, log(1/δ)) query complexity, time complexity, and time evolution.

4. A separation result and new learnable classes. The paper shows (Appendix B) that the stabilizer extent of the Choi state |U⟩⟩ and the Clifford extent of U can be exponentially separated, and identifies classes of Hamiltonians that are dense in Paulis but Clifford-sparse, such as sums of exchange interactions (which swap subsets of k qubits) and sums of few stabilizer projectors.

Main Findings

• Strong, not just weak, agnostic learning is possible. A naive approach — learn the closest stabilizer state to the Choi state, then round — loses a factor of opt in fidelity and yields only a weak guarantee that is polynomial in opt. The paper's analysis recovers the additive guarantee opt − ε.

• Stabilizer-neighbor graph controls the rounding loss. The graph has stabilizer states as vertices, with an edge between two states when their fidelity is 1/2. Starting from a Clifford Choi state with fidelity opt, following improving edges to a γ-approximate local maximizer takes t = O(log(1/opt)) steps, each increasing fidelity by at least a factor 1/γ while changing entanglement entropy by at most one.

• Rounding back costs at most a factor 2^t. Because the maximizer is within distance t of a maximally entangled stabilizer state, it can be written as a superposition of at most t maximally entangled stabilizer states; using the normal form of bipartite stabilizer states, the algorithm searches over at most 2^t candidates. Combined with the gain γ^{−t}, the final fidelity is opt/(2γ)^t, and choosing γ only slightly above 1/2 gives opt − ε.

• Tolerant testing comes for free. The agnostic protocol implies a quasipolynomial-time tolerant tester of Clifford unitaries up to 1/poly(n) additive gap.

• Short-time evolution converts Hamiltonian extent into unitary extent. If H has Clifford extent ≤ ξ, then U(t) = exp(−iHt) has Clifford extent ≤ e^t ξ, which is made small by choosing t ≤ 1/ξ. Using the expansion U(t) = I − iHt + O(t²), the estimate Ĥ = (I − Û(t))/(it) is close to H once the Taylor truncation error is controlled.

• A second Hamiltonian algorithm can beat the first in some regimes. When H is written as Σ_{j,k} h_{j,k}|s_j⟩⟨s_k| over R stabilizer states |s_j⟩, learning the stabilizer decomposition of |e^{−iHt}⟩⟩ gives complexity poly(n(gh/ε)^{log(gh/ε)}), where h* is the largest eigenvalue of the coefficient matrix and g* the largest eigenvalue of the Gram matrix of {|s_j⟩}. This can be independent of R, and is favorable when R ≪ 2^{n/3}, compared with poly(n(R/ε)^{log(R/ε)}) for the first approach.

• Exponential separation between Clifford and stabilizer complexity. There exist unitaries for which the stabilizer extent of the Choi state and the Clifford extent of the unitary are exponentially far apart. The long-range controlled-Z operator C^nZ = I − 2|1^n⟩⟨1^n| has Choi state of stabilizer rank 2, while decomposing it into Clifford unitaries is expected to require exponentially many terms.

Methodology in Plain English

The starting point is a known "stabilizer bootstrapping" algorithm that, given copies of an unknown quantum state, lists stabilizer states with high fidelity to it. The obvious idea is to apply it to the Choi state of the unknown unitary and then invert the Choi map. The obstacle is that the closest stabilizer state to a Choi state need not itself be the Choi state of a Clifford — the resulting matrix may not be unitary at all.

The authors fix this by studying how entanglement behaves along the path the bootstrapping algorithm takes. If a stabilizer state is far from being maximally entangled, that very fact forces its fidelity to be correspondingly high, so the subsequent "rounding" step back to a maximally entangled (i.e., Clifford-Choi) state costs exactly what the extra fidelity had gained. The two effects cancel, leaving fidelity opt − ε. The search over rounded candidates stays efficient because the number of candidates is at most 2^t with t = O(log(1/opt)).

For unitaries with bounded Clifford extent, the agnostic Clifford learner is combined with a known algorithmic decomposition result to express the Choi state as a compact combination of Clifford Choi states plus a low-fidelity residual. For Hamiltonians, the authors sidestep the fact that a Hamiltonian is not a unitary by learning a short-time evolution operator instead and inverting a first-order Taylor expansion to recover the Hamiltonian, with a careful error analysis of the truncation.

Why This Matters

The paper broadens the set of quantum dynamics that can be efficiently learned from "sparse in the Pauli basis" to "concise over Clifford unitaries," a class that includes objects with exponentially many Pauli coefficients. This matches the class of circuits known to be classically simulable and gives a process-level analogue of recent work on state tomography with bounded extent.

Real-world applications (as discussed by the authors):

• Circuit verification: the learned Clifford acts as the best Clifford explanation of an implemented circuit, exposing coherent Clifford-frame or compilation errors.
• Error mitigation: the learned Clifford provides a classically simulable surrogate usable in the spirit of Clifford-data regression and probabilistic error-cancellation approaches.
• Complementing benchmarking: the protocol supplements fidelity estimation and randomized benchmarking methods.
• Direct compilation and simulation: because the output of the agnostic protocol is a genuine Clifford, it can be compiled, simulated, and compared against an intended circuit without further processing.

Industry relevance: the work targets practical diagnosis of quantum processors whose intended operations are Clifford circuits or are well approximated by them, and the author list includes an IBM Research affiliation alongside Tufts University, indicating relevance to hardware-oriented verification and error-mitigation workflows. The bounded-extent Hamiltonian results also cover physically motivated models such as sums of exchange interactions.

Future Directions

• Faster and more query-efficient agnostic tomography: the current protocol uses query access mainly to prepare the Choi state, requiring n ancilla qubits. The authors ask whether more elaborate use of queries could reduce time complexity, and what is achievable with limited quantum memory.
• A proper protocol for bounded-extent unitaries: the output of the bounded-Clifford-extent tomography is a linear operator that need not be unitary; making it proper is left open.
• Extending to richer simulable classes: agnostic tomography for Clifford circuits with few T gates or fermionic Gaussian unitaries, and corresponding bounded-extent decompositions over those classes.
• Long-time Hamiltonian tomography: the Hamiltonian algorithm relies on access to arbitrarily short-time evolutions, which is difficult in practice; removing this requirement is flagged as important. Open questions also remain on the exact relationship between Clifford complexity of U and stabilizer complexity of its Choi state, including whether an exponential separation between Clifford rank and stabilizer rank follows from the quadratic uncertainty principle.

Target Audience

Researchers in quantum learning theory, quantum process tomography, and quantum complexity theory; theorists working on classical simulation of quantum circuits and on stabilizer-state methods; and quantum computing practitioners interested in circuit verification, benchmarking, and error mitigation for Clifford-dominated workloads. The paper assumes familiarity with the Clifford group, Choi states, and entanglement entropy, so it is best suited to readers with graduate-level quantum information backgrounds.

Authors’ abstract

Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning $n$-qubit quantum unitaries $U$ and Hamiltonians $H$, given query access to $U$ or the unitary evolution of $H$, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form $U = \sum_i α_i C_i$ over Cliffords $C_i$ with bounded Clifford extent $\sum_i |α_i|$. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary $U$ with optimal Clifford fidelity $\textsf{opt}$, outputs a Clifford unitary witnessing fidelity $\geq \textsf{opt} - \varepsilon$ for some error $\varepsilon > 0$, in time $\textsf{poly}(n,(1/\varepsilon)^{\log(1/\varepsilon)})$. We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity $Ω(2^n)$) in the Pauli basis but are Clifford structured.