Efficient Preparation of Quantum States via Randomized Truncation

Technical Summary: Efficient Preparation of Quantum States via Randomized Truncation

Problem Statement
The preparation of general quantum states is a fundamental bottleneck in quantum algorithms, particularly for applications in quantum chemistry, differential equations, and machine learning. Realistic target states often exhibit a hierarchical amplitude structure: a small core of dominant configurations accompanied by a "heavy tail" of many small but non-negligible components. Standard deterministic truncation methods discard these small amplitudes to reduce circuit complexity. However, this approach incurs a severe linear trade-off between precision and resource cost: to achieve a trace-distance error $\epsilon$, one must retain enough amplitudes such that the discarded $\ell_2$ weight is $O(\epsilon)$. This requirement forces the encoding of a large number of small-amplitude components, leading to exponential growth in circuit depth and gate counts. Furthermore, these small components often necessitate high-precision gate synthesis (requiring extensive T-gate overhead) and high-control rotations (increasing CNOT counts), making the preparation of high-fidelity states prohibitive for both near-term and fault-tolerant hardware.

Methodology
The authors propose a randomized state-preparation protocol that circumvents the rigid limits of deterministic truncation by leveraging probabilistic amplification. Instead of coherently encoding the entire heavy tail in a single deep circuit, the method constructs a randomized ensemble of low-complexity circuits.

The protocol operates as follows:

1. Partitioning: The state amplitudes are partitioned into a significant set $A$ (amplitudes $|\alpha_i| \geq t$) and a negligible tail set $B$ ($|\alpha_i| < t$).
2. Ensemble Construction: For each index $m$ in the tail set $B$, a specific quantum state $|\tilde{\psi}_m\rangle$ is defined. This state retains all amplitudes in $A$ and includes a single element from $B$ (index $m$) with an amplified coefficient.
3. Sampling: The protocol samples an index $m$ from $B$ with probability $p_m = |\alpha_m| / \sum_{j \in B} |\alpha_j|$. The corresponding state $|\tilde{\psi}_m\rangle$ is prepared.
4. Resulting State: The final output is a mixed state $\rho_{\text{approx}} = \sum_m p_m |\tilde{\psi}_m\rangle\langle\tilde{\psi}_m|$.

Crucially, the amplification of the small coefficient $\alpha_m$ by a factor of $1/p_m$ ensures that the expected value of the ensemble recovers the original target state $|\psi\rangle$. The authors prove that while individual circuits in the ensemble are simple (retaining only one tail component), the resulting mixed state recovers the target with significantly reduced error compared to deterministic truncation.

Key Contributions and Theoretical Results
The primary theoretical contribution is the demonstration that this randomized approach improves the error scaling from linear to quadratic relative to the discarded amplitude mass.

• Quadratic Error Scaling: The authors prove (Theorem 1) that if the discarded $\ell_2$ weight is $\epsilon^2$, the trace-distance error of the randomized ensemble scales as $O(\epsilon^2)$, whereas deterministic truncation scales as $O(\epsilon)$.
• Resource Reduction: This quadratic improvement translates to a reduction in the number of encoded amplitudes required to achieve a fixed target fidelity.
  • For exponentially decaying states (common in quantum chemistry and gapped Hamiltonians), the randomized protocol requires approximately half the number of amplitudes compared to the deterministic approach ($K_{\text{det}} \approx 2K_{\text{rand}}$).
  • For power-law decaying states (common in many-body physics and data loading), the resource savings scale asymptotically as $O(\hat{\epsilon}^{-1/(2r_{\text{pow}}-1)})$, offering even greater gains as the desired precision increases.
• Gate-Level Savings: By amplifying small coefficients, the protocol lifts these contributions out of the highest-precision regime. This reduces the need for extremely high-precision multi-controlled rotations, thereby significantly lowering the T-gate count and CNOT overhead associated with resolving small angles.

Numerical Results
The authors validated the protocol on several realistic and synthetic instances:

• LiH Molecule: Using the ground state of the Lithium Hydride molecule (mapped to 12 qubits), the randomized protocol achieved a 82.2% reduction in CNOT counts and an 81.2% reduction in T-gate counts compared to deterministic truncation at a trace-norm error of $5.86 \times 10^{-4}$.
• Synthetic Power-Law State: For a 10-qubit state with amplitudes decaying as $j^{-5}$, the method demonstrated reductions of up to 98.9% in CNOT counts and 98.5% in T-gate counts at a trace-norm error of $1.04 \times 10^{-13}$.
• Machine Learning and Many-Body Physics: The protocol was also tested on states derived from a trained ResNet (10 qubits) and the ground state of the Transverse-field Ising Model (11 qubits). In both cases, the randomized method consistently achieved lower trace-norm errors at fixed costs compared to deterministic truncation, confirming its applicability beyond strictly power-law or exponential distributions.

Significance and Claims
The paper claims to establish a resource-efficient paradigm for initializing complex quantum states. By relaxing the gate-synthesis precision requirements and reducing the number of encoded amplitudes, the method addresses a critical bottleneck in end-to-end quantum algorithms.

The authors emphasize that this approach is compatible with both near-term and fault-tolerant regimes:

• For near-term devices, it replaces a single deep, monolithic circuit with sampling over simpler, shallower circuits, making state preparation feasible within coherence limits.
• For fault-tolerant architectures, it significantly reduces the T-gate overhead and CNOT costs associated with high-precision rotations, thereby expanding the class of quantum states that can be efficiently prepared on hardware.

The work concludes that this randomized truncation strategy offers a rigorous, controllable error bound that is proportional to the square of the discarded tail weight, enabling more efficient implementations of algorithms that rely on complicated state preparation without sacrificing accuracy.