Exact verification of Givens rotation circuits for efficient quantum phase estimation of iron-sulfur clusters

Technical Summary: Exact Verification of Givens Rotation Circuits for Efficient Quantum Phase Estimation of Iron–Sulfur Clusters

Problem Statement
Quantum Phase Estimation (QPE) on qubitized walk operators is the standard algorithm for computing the ground-state energy of metalloenzyme cofactors, such as iron–molybdenum cofactor (FeMoco) and iron–sulfur clusters. The computational cost is dominated by the number of Toffoli gates required per walk step. In the state-of-the-art approach by Low et al., which utilizes double-factorized tensor hypercontraction (DFTHC), block-invariant symmetry shifts (BLISS), and spectral amplification (SA), a significant portion (44–72%) of the Toffoli cost per step arises from networks of Givens rotations. These rotations utilize angles stored in quantum registers loaded from lookup tables.

Two critical issues regarding these rotations are identified:

1. Cost Discrepancy: There is an inconsistency in the published accounting of Low et al. regarding the Toffoli cost per rotation. While their totals and code charge $2b_{rot}$ Toffolis per rotation (where $b_{rot}$ is the angle precision), certain appendices and equations suggest a cost of $b_{rot}$. The authors argue that a single signed addition of the angle register cannot implement a full Givens rotation (which requires rotating two Majorana operators) without additional operations, making the $2b_{rot}$ baseline correct.
2. Verification Gap: Existing verification methods for quantum circuits, such as basis-state evaluators used in evolutionary searches (e.g., by Gu et al.), are designed for circuits that map basis states to basis states (up to a sign). Givens rotations create superpositions and involve phase-gradient resource states, rendering standard evaluators inapplicable. A coherent circuit that is incorrect on a small fraction of inputs can catastrophically fail when applied $10^4$ to $10^5$ times in QPE.

Methodology
The authors propose a two-pronged approach: an exact verification framework and a circuit optimization strategy.

1. Exact Verification Framework (Theorem 1):
   The authors develop a method to verify circuits that include a fixed Clifford change of basis, a core that permutes basis states with $Z_4$ phases, and a phase-gradient resource state. The method separates the circuit into a fixed basis change ($F$) and a core ($C$). Verification relies on four integer conditions checked for every basis input:

   • (a) At every uncomputation step, the measured temporary qubit must equal the logical AND of its inputs.
   • (b) At the end, temporary qubits must be reset to $|0\rangle$ and the control register must be unchanged.
   • (c) The core must map basis states $|c, y\rangle$ to $i^{k(c,y)}|c, \pi_c(y)\rangle$, where $\pi_c$ is a bijection.
   • (d) A modular arithmetic condition relating the permutation, the phase $k$, and the target phase function $T(c)$ must hold: $\pi_c(y) - y + 2^{b-2}k(c, y) \equiv T(c) \pmod{2^b}$.
     This framework allows for exhaustive verification of circuits that create superpositions, provided the non-classical parts are restricted to the specified structure.

2. Circuit Optimization and Cost Reduction:

   • Angle Grid Interpretation: The authors interpret Low et al.'s randomized rounding scheme as placing angles on a $2^{b_{rot}-1}$ grid rather than $2^{b_{rot}}$. Since the rotation is $2\pi$-periodic, the most significant bit of the angle register is never read, allowing the circuit to operate on a grid of width $b = b_{rot} - 1$.
   • Clifford Diagonalization: A Clifford unitary $F$ is applied to diagonalize the two commuting Pauli rotations of a Givens rotation. This transforms the operation into a controlled phase-gradient addition masked by a parity qubit.
   • Fused Circuit: Instead of performing two separate additions (costing $2b_{rot}$ Toffolis), the authors fuse the operations into a single masked addition. By replacing arithmetic on the two most significant gradient qubits with Clifford phase gates ($S^{\pm 1}$) and using a masked addition, the circuit reduces the Toffoli count to $2b_{rot} - 5$.
   • Simplified Adders: An intermediate construction using simplified adders on the $2^{b_{rot}-1}$ grid achieves a cost of $2b_{rot} - 4$.

Key Contributions

• Verification Certificate: The paper provides the first exact, exhaustive verification method for Givens rotations with quantum angles, proving correctness for all widths used in published benchmarks (up to $b=17$, covering $2^{38}$ basis states).
• Cost Correction and Reduction: The authors demonstrate that the published cost of $2b_{rot}$ Toffolis per rotation is accurate for the baseline, but can be reduced to $2b_{rot} - 5$ through the fused circuit. This reduction comprises:
  • Accounting Correction: 4 Toffolis saved per rotation by correctly identifying the grid size and using simplified adders ($2b_{rot} - 4$).
  • Fusion Savings: 1 additional Toffoli saved per rotation by fusing the two additions into one masked addition ($2b_{rot} - 5$).
• Exhaustive Validation: The fused circuit and its variants are verified exhaustively at every precision used in the published walks for FeMoco and other iron–sulfur clusters. The authors also verify that the fused circuit is correct for all widths, not just the specific instances used.

Results
The authors applied their optimized circuits to the 14 walk steps across eight benchmark systems (including Fe2S2, Fe4S4, FeMoco-54, FeMoco-76, and various ruthenium catalysts) under the error budgets defined by Low et al.

• Toffoli Reduction: Replacing only the rotation term (keeping the walk operator, $\lambda_{eff}$, and step count unchanged) reduces the total QPE Toffoli count by 9.5–14.3% under the Table V error budget and 6.1–12.9% under the statistical budget.
• Specific Benchmarks:
  • Fe2S2: The total QPE cost drops from $3.99 \times 10^7$ to $3.60 \times 10^7$ Toffolis (under the Table V budget).
  • FeMoco-76: The estimated runtime on 4.5 million physical qubits decreases from 8.71 hours to 7.81 hours.
• Comparison with Sparse Walks: The authors compare their results with the sparse Pauli walk optimized by Gu et al. They note that the large difference in resource estimates (nearly two orders of magnitude) stems from the representation (DFTHC+BLISS+SA vs. sparse Pauli) and associated approximation errors, rather than circuit optimization alone. However, within the DFTHC framework, their rotation optimization provides a further 11% reduction.

Significance and Claims
The paper claims that its primary significance lies in providing exact verification for a class of circuits that were previously unverifiable by standard basis-state evaluators. This ensures that the proposed cost reductions are not the result of subtle errors that would accumulate over the $10^5$ applications in QPE.

The authors modestly state that the cost reduction is largely an "accounting correction" (fixing the grid size interpretation and adder simplification) combined with a specific circuit fusion. They emphasize that:

• The fused circuit was developed via interactive sessions with an LLM coding agent, not an automated search.
• The verification method (Theorem 1) is general and could potentially drive future circuit searches if integrated with evaluators for non-classical parts.
• The results are strictly bounded by the assumptions of Low et al.'s angle grid and rotation convention; if these assumptions fail, the savings would be slightly lower (saving 3 Toffolis instead of 5 per rotation).
• The work does not claim to solve the entire QPE problem but specifically targets the rotation sub-circuit, which constitutes a substantial fraction of the total cost.