Sparse quantum state preparation with improved Toffoli cost

Technical Summary: Sparse Quantum State Preparation with Improved Toffoli Cost

Problem Statement
The preparation of quantum states is a fundamental primitive in quantum computing, essential for applications ranging from linear-system solvers and quantum machine learning to quantum simulation. While generic state preparation has been extensively studied, sparse quantum states—states on $n$ qubits containing only $s \ll 2^n$ non-zero computational basis states—require specialized, efficient algorithms.

In fault-tolerant quantum computing, the primary resource metric is often the number of Toffoli gates (and T-gates), as these non-Clifford operations are significantly more costly to implement than Clifford gates due to the overhead of magic-state distillation. Existing approaches for sparse state preparation generally fall into two categories:

1. Iterative construction: Building the state in $s$ steps, each preparing a single basis state. This typically incurs a Toffoli cost exceeding $s \lceil \log(s) \rceil$.
2. Two-step approach (Dense Preparation + Isometry): First preparing a dense state on a $\lceil \log(s) \rceil$-qubit sub-register, then mapping it to the target sparse state via an isometry. While the dense preparation cost is well-optimized (e.g., via Grover-Rudolph algorithms), the isometry step has historically been the bottleneck. Prior art, such as the method by Malvetti et al., requires a worst-case Toffoli cost of $s(\lceil \log(s) \rceil - 1)$ for the isometry, which dominates the total algorithm cost.

Methodology
The authors propose a refined two-step framework (illustrated in Figure 1) that optimizes the isometry step and integrates it with dense state preparation:

1. Batched Isometry Construction:
   The core innovation is a new classical algorithm for constructing the isometry circuit. Instead of applying individual multi-controlled-X gates to zero out non-subspace qubits for each of the $s$ states (as done in Malvetti et al.), the authors group states into batches of size $m$, where $m$ is the largest power of two fitting in the available non-subspace register ($m \le n - \lceil \log(s) \rceil$).

   • For each batch, the algorithm transforms the states into a form where the non-subspace register contains a single $|1\rangle$ at distinct positions (e.g., $|k\rangle_s |e_0\rangle_r, \dots, |k+m-1\rangle_s |e_{m-1}\rangle_r$).
   • A Partial Unary Iteration (PUI) circuit is then applied to simultaneously zero out the non-subspace registers for the entire batch.

2. Partial Unary Iteration (PUI) Circuits:
   The authors introduce two variants of PUI circuits, which iterate over a specific interval $[l, r]$ of an address register rather than the full space:

   • Restricted PUI: Guarantees that unitaries are applied only to states within the target interval $[l, r]$.
   • Unrestricted PUI: Allows the circuit to apply non-trivial unitaries to states with address values greater than $r$. This relaxation significantly reduces the Toffoli count. The "unwanted" effects on higher address values are tracked classically and corrected in subsequent steps or batches.

3. Joint Optimization with Dense State Preparation:
   The authors analyze the trade-off between the isometry cost and the dense state preparation cost. They propose "outsourcing" certain sub-tasks from the dense preparation to the isometry circuit:

   • Sign Fixes: Instead of uncomputing the angle register after dense preparation (which requires additional Toffolis for sign correction), the sign information is encoded directly into the isometry using restricted PUIs.
   • Real States: For target states with purely real coefficients, the phase encoding step of the dense preparation is entirely removed and handled within the isometry, potentially reducing the dense preparation Toffoli cost by a factor of up to three.

Key Contributions

• Improved Isometry Algorithm: A new classical algorithm (Algorithm 1) that constructs isometry circuits with a worst-case Toffoli cost bounded by:
  $$\left\lceil \frac{s}{m} \right\rceil \left( 2m + \frac{\log(\tilde{s}/m)}{2} - 3 \right) + \log(\tilde{s}^2/m)$$
  where $\tilde{s} = 2^{\lceil \log(s) \rceil}$. This represents a roughly $\log(s)/2$ improvement over the state-of-the-art method by Malvetti et al.
• PUI Variants: The definition and cost analysis of restricted and unrestricted partial unary iteration circuits. The unrestricted version achieves lower Toffoli counts by allowing "leakage" of operations to higher address values, which is manageable in the context of the batched isometry construction.
• Resource Trade-off Analysis: A comprehensive analysis (Table 1) of the combined Toffoli and qubit costs for sparse state preparation, demonstrating how optimizing the isometry allows for better utilization of ancilla qubits to reduce the dense preparation cost, particularly for real-valued states.
• Implementation: The circuits are implemented in the Qualtran framework, with the classical isometry-finding algorithm optimized using SIMD-accelerated Rust code.

Results

• Theoretical Bounds: The worst-case Toffoli cost for the isometry is reduced from $O(s \log s)$ to approximately $O(s)$ for sufficiently large $n$. Specifically, the cost approaches $s$ in numerical benchmarks on random states, compared to the previous best of roughly $s \log s$.
• Numerical Benchmarks:
  • For random $s$-sparse states, the number of Toffolis per $s$ approaches 1 as $n$ increases (Figure 2, right).
  • For purely real states, the joint optimization reduces the total Toffoli count significantly compared to generic complex states (Figure 9).
  • The classical algorithm runs efficiently, finding isometries for $s=10^7$ states in roughly 10–20 minutes on standard CPU hardware.
• Comparison: The proposed method outperforms existing literature (e.g., [4, 14, 20, 21]) in terms of Toffoli count while maintaining comparable or lower qubit overhead.

Significance and Claims
The paper claims to present the most efficient sparse state preparation circuits in the literature in terms of Toffoli and qubit counts. The significance lies in:

1. Bottleneck Removal: By reducing the isometry cost from the dominant factor to a level comparable with dense preparation, the overall algorithm becomes more efficient.
2. Scalability: The approach scales favorably with the number of qubits $n$, making it suitable for large-scale fault-tolerant quantum algorithms where $s$ is large but $s \ll 2^n$.
3. Practicality: The method is compatible with existing fault-tolerant resource estimation frameworks (focusing on Toffoli counts) and is implemented in a modular software framework (Qualtran).

The authors remain modest regarding future implications, noting that while Toffoli count is the current standard metric, advances in magic-state generation (cultivation/distillation) may shift the focus to runtime metrics in the future. They also leave open the question of whether sub-linear Toffoli costs in $s$ are achievable with limited ancilla resources.