Approximate Sparse State Preparation with the Grover-Rudolph Algorithm

This paper proposes two improvements to the Grover-Rudolph algorithm for sparse quantum state preparation: a gate-merging technique that reduces CNOTs and control qubits by utilizing virtual zero-angle gates, and an approximate variant that merges similar rotations to further optimize resources while providing a classically computable bound on the resulting state error.

The Gist

Imagine you are trying to build a very specific, complex sculpture out of a giant block of marble. In the world of quantum computing, this "sculpture" is a quantum state, and the "block of marble" is a blank slate of information (all zeros).

Usually, carving this sculpture is incredibly hard. If you want to create a specific pattern on a block with 20 layers, you might need to make millions of tiny, precise cuts. This is too slow and expensive for current quantum computers.

However, the paper focuses on a special type of sculpture called a "sparse state." Think of this as a sculpture where 99.9% of the marble is just empty space, and only a few tiny spots actually have the shape you want. Because most of the block is empty, you shouldn't have to cut the whole thing; you should only cut the parts that matter.

The authors are improving a known method (the Grover–Rudolph algorithm) that tries to carve these sparse sculptures. They found two clever ways to make the carving process much faster and use fewer tools.

1. The "Ghost Cut" Trick (Exact Optimization)

Imagine you are following a recipe to carve your sculpture. The original recipe says: "If the marble is in the 'top-left' corner, make a cut. If it's in the 'top-right' corner, make the exact same cut."

The authors realized that if you have two instructions that are almost identical (differing by just one tiny detail), you can combine them into one bigger instruction. Even better, they found a way to combine a real instruction with a "ghost" instruction.

• The Metaphor: Imagine a recipe says, "If the marble is in the 'bottom-left' corner, cut it." But you know for a fact that the 'bottom-left' corner is empty (it's just air). The original recipe might still say, "If it's in the 'bottom-right' corner (which is also empty), do nothing."
• The Innovation: The authors realized they could merge the "bottom-left" cut with the "bottom-right" nothing. Since the "bottom-right" area is empty, doing nothing there doesn't hurt anything. By merging them, they can remove a complicated "control" mechanism (a tool that checks where the marble is) entirely.
• The Result: This is like realizing you don't need a specific sensor for a room that is always empty. By removing these unnecessary sensors, they reduced the number of complex "CNOT" gates (the quantum equivalent of logic switches) by up to 90% for very sparse states.

2. The "Good Enough" Compromise (Approximate Optimization)

The first trick was perfect, but the authors asked: "What if we are willing to accept a tiny, almost invisible flaw in the sculpture to save even more time?"

• The Metaphor: Imagine you are painting a wall. The exact recipe says, "Mix red paint to a shade of 50.1% red and 49.9% white." Another instruction says, "Mix red paint to 50.2% red and 49.8% white." These are slightly different.
• The Innovation: Instead of mixing two separate batches of paint, the authors say, "Let's just mix one batch at 50.15%." It's not exactly what the recipe asked for, but it's so close that the wall looks the same to the human eye.
• The Safety Net: They didn't just guess. They created a mathematical "calculator" that predicts exactly how much the final sculpture will differ from the perfect one. They set a safety limit (e.g., "The sculpture must be 99% perfect"). If the calculator says a merge will keep the sculpture above 99% perfect, they allow the merge.
• The Result: By allowing these tiny, controlled imperfections, they were able to cut the number of tools needed by an additional 20–30% compared to the already-optimized method.

Summary of the Journey

1. The Problem: Loading specific data into a quantum computer is usually too slow because it requires too many steps.
2. The Opportunity: If the data is "sparse" (mostly empty), we can skip steps.
3. Improvement 1 (Exact): They found a way to merge instructions and remove unnecessary checks, specifically targeting the empty parts of the data. This saved 90% of the work.
4. Improvement 2 (Approximate): They allowed the computer to take "shortcuts" by merging slightly different instructions, as long as a mathematical safety check guaranteed the result was still very close to perfect. This saved another 20–30%.

In short, the authors took a slow, rigid process for building quantum states and turned it into a flexible, efficient one by realizing that empty space can be ignored and tiny errors can be safely managed.

Technical Summary

1. Problem Statement

Quantum State Preparation (QSP) is a fundamental subroutine in quantum computing, tasked with loading classical data into the amplitudes of a quantum state $|\psi\rangle$. While preparing general (unstructured) states requires exponential resources, many practical algorithms utilize sparse states, where the number of non-zero amplitudes $d$ is much smaller than the total Hilbert space dimension $2^n$ ($d \ll 2^n$).

The Grover–Rudolph (GR) algorithm is a standard method for preparing such states using controlled rotations. However, even for sparse states, the resulting quantum circuits often remain prohibitively expensive in terms of gate count (specifically CNOTs) and control qubit depth, particularly for early fault-tolerant quantum computers that have limited ancilla qubits (specifically $\Theta(n)$ ancillas).

The paper addresses the challenge of reducing the circuit complexity (gate count and control qubits) of the Grover–Rudolph algorithm for sparse states without significantly compromising the fidelity of the prepared state.

2. Methodology

The authors propose a two-pronged approach to optimize the GR algorithm: an Exact Optimization and an Approximate Optimization.

A. Exact Optimization (Control Stripping and Merging)

The authors build upon existing gate-merging techniques (from prior work [11]) and introduce a novel "control stripping" mechanism.

• Neighboring Merges: Gates with identical rotation angles on the same layer but control patterns differing by only one bit (Hamming distance 1) are merged. This reduces the number of control qubits.
• Control Stripping (New Contribution): The authors allow merging an active rotation gate with a virtual zero-angle gate located on an "unreachable" branch of the preparation tree (a branch with zero probability amplitude).
  • Mechanism: If a control pattern $x$ has a neighbor $x'$ that is unreachable (zero amplitude), the control bit distinguishing them can be removed (replaced by a "don't care" or 'e' control).
  • Result: This reduces the number of control qubits and CNOTs without altering the final state, as the removed control never affects the non-zero amplitudes.
• Hybrid Strategy: The algorithm evaluates whether to use the optimized sparse decomposition (singular rotations) or a Uniformly Controlled Rotation (UCR) decomposition at each layer, selecting the one with the lower CNOT count.

B. Approximate Optimization (Bounded Error Merging)

To achieve further reductions, the authors introduce an approximate variant where the prepared state is allowed to deviate slightly from the target, provided the overlap (fidelity) remains above a user-defined threshold $F_{min}$.

• Approximate Merging: Similar to the exact method, gates are merged (neighbors or control stripping), but the resulting rotation angle is re-calculated to minimize the error introduced by the merge.
• Overlap Estimation: A critical contribution is the derivation of a classically computable estimator for the overlap between the target state and the approximate state after a merge.
  • The method uses "clusters" of basis states absorbed into a single gate.
  • It calculates an optimal merged angle $\theta_C$ that maximizes the overlap for the cluster.
  • It derives a rigorous lower bound on the final overlap ($F_{LB}$) to guarantee the error remains within limits.
• Greedy Algorithm: The algorithm proceeds greedily, sorting candidate merges by their estimated post-merge overlap. It processes merges in intervals of the target fidelity, re-evaluating candidates after each step to ensure the threshold is met.

3. Key Contributions

1. Control Stripping for Sparse States: The identification and formalization of merging active gates with virtual zero-angle gates on unreachable branches. This is shown to be a highly effective "control stripping" move that significantly reduces CNOT counts for sparse vectors.
2. Approximate Sparse QSP Framework: Extending approximate state preparation techniques (previously applied to smooth distributions) to the highly discontinuous case of sparse states.
3. Classical Overlap Estimator: Deriving a formula to estimate the overlap loss ($L_C$) for a cluster of merged gates and a rigorous lower bound theorem (Theorem 8) to verify the final fidelity classically.
4. Complexity Analysis: Providing the classical computational cost of the optimization routines, showing they are polynomial in $d$ and $n$ ($O(d^2 n^4)$ for exact, $O((M+dn)d^2 n^2)$ for approximate).

4. Results

The authors validated their methods using numerical simulations on random sparse states with $n=20$ qubits.

• Exact Optimization Performance:

  • For sparsity levels of $D = d/2^n \approx 10^{-5}$, the exact optimization reduces the CNOT count by ~90% compared to the unoptimized Grover–Rudolph circuit.
  • The reduction scales with sparsity: as the state becomes sparser, more branches become unreachable, enabling more control stripping.
  • For very sparse states, the method approaches a 99.9% reduction compared to standard UCR decomposition.

• Approximate Optimization Performance:

  • Allowing a small, controllable error (e.g., $F_{min} = 0.9$) yields an additional 20–30% reduction in CNOTs compared to the exact optimized circuit.
  • For extremely sparse states, the additional reduction can reach 50%.
  • The overlap estimator ($F_{est}$) was found to be highly accurate, closely tracking the true overlap and often acting as a lower bound itself, justifying its use for guiding the greedy merging process.
  • The parameter $M$ (number of fidelity intervals) showed diminishing returns beyond $M=20$.

5. Significance

• Resource Efficiency: The proposed methods drastically reduce the resource requirements (CNOTs and control qubits) for sparse state preparation, making it more feasible for near-term and early fault-tolerant quantum computers with limited connectivity and ancilla counts.
• Scalability: By exploiting the sparsity structure directly, the algorithms avoid the exponential scaling associated with dense state preparation.
• Practical Trade-off: The approximate method provides a tunable knob for practitioners to trade off circuit depth against state fidelity, which is crucial for algorithms where a small error in state preparation is tolerable (e.g., in variational quantum algorithms).
• Foundation for Future Work: The paper sets a baseline for further improvements, such as handling complex amplitudes (phases) and integrating with advanced decomposition techniques (e.g., Toffoli count reduction).

In summary, this work transforms the Grover–Rudolph algorithm from a theoretically efficient but practically expensive subroutine into a highly optimized tool for sparse quantum data loading, offering both exact and approximate pathways to significant circuit compression.