⚛️ quantum physics

Algebraic Reduction to Improve an Optimally Bounded Quantum State Preparation Algorithm

This paper proposes a simpler algebraic decomposition that improves the optimally bounded quantum state preparation algorithm by Sun et al., achieving reductions in circuit depth, total gates, and CNOT count through the use of a single operator for uniformly controlled gates when ancillary qubits are available.

Original authors: Giacomo Belli, Michele Amoretti

Published 2026-02-09

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Giacomo Belli, Michele Amoretti

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build a very specific, complex sculpture out of light. In the world of quantum computing, this "sculpture" is a quantum state—a specific arrangement of information held by a group of tiny particles called qubits. Preparing this state is like setting up a stage before a play can begin; if the stage isn't set perfectly, the play (the quantum algorithm) fails.

The paper you provided is about a new, smarter way to build this stage. Here is the breakdown in simple terms:

The Problem: Building a Ladder Too Slowly

For years, scientists have used a method to build these quantum states that is like climbing a very long, winding ladder.

The Old Way (Sun et al.): To get to the top of the ladder (the final state), you have to pass through several "checkpoints." At every single checkpoint, you have to perform three distinct tasks (like checking your shoes, adjusting your hat, and tying your shoelaces) before you can move to the next rung.
The Cost: Doing three tasks at every step makes the ladder very deep and takes a long time to climb. In quantum computing, "time" is precious because the particles are fragile and lose their information quickly (a problem called "coherence").

The New Idea: A Shortcut Through Algebra

The authors, Giacomo Belli and Michele Amoretti, found a mathematical trick (an algebraic reduction) to simplify this process.

Think of the quantum state as having two parts:

The Shape (Real Part): The physical structure of the sculpture.
The Color (Complex Part): The specific "flavor" or phase of the light.

The Old Method tried to build the Shape and the Color simultaneously at every single step of the ladder. This required the three-task routine at every level.

The New Method (OSUN) splits the job:

Step 1: They build the entire Shape first. Because they are only building the shape, they don't need to do all three tasks at every step. They can do just one task (a single "operator") at each checkpoint.
Step 2: Once the shape is done, they apply a single, final "paint job" (the complex part) at the very end to add the correct colors.

The Analogy: Painting a House

Imagine you are painting a house with 10 rooms.

The Old Way: To paint each room, you have to: 1) Sand the wall, 2) Prime the wall, and 3) Paint the wall. You do all three steps for Room 1, then all three for Room 2, and so on.
The New Way: You realize that for the structure of the house, you only need to sand and prime. So, you go through all 10 rooms doing only the sanding and priming (which is faster). Once the whole house is prepped, you go back and do the final painting in one big, efficient sweep.

What Did They Achieve?

By using this "split the job" strategy, they didn't change the type of work needed (the complexity class is the same), but they made the work significantly faster and shorter.

Fewer Steps: Instead of doing 3 things at every step, they do 1 thing for most of the journey.
The Result:
- Depth: The "ladder" is shorter. The circuit (the sequence of instructions) is less deep, meaning it finishes faster.
- Efficiency: They reduced the number of specific "CNOT" gates (a common type of quantum instruction) and total gates needed.
- The Math: They proved that for a certain range of resources, this new method is 3 times faster in the linear part of the calculation and 2 times faster in the exponential part compared to the previous best method.

The Proof

The authors didn't just do the math on paper; they built a simulation using a library called PennyLane. They tested their new algorithm on:

Famous quantum states (like Bell states and GHZ states).
Random, messy states.
States with up to 10 qubits.

The results showed that their new method (called OSUN) consistently built the quantum states with a shallower depth (faster execution) than the old standard methods, especially as the number of qubits grew.

Summary

The paper presents a clever mathematical shortcut. Instead of doing three heavy tasks at every step of building a quantum state, the authors realized they could do just one task for the "structure" and handle the "complex details" in one final step. This makes the process significantly faster and more efficient, which is a huge win for building reliable quantum computers.

Technical Summary: Algebraic Reduction to Improve an Optimally Bounded Quantum State Preparation Algorithm

Problem Statement
Quantum State Preparation (QSP) is a fundamental subroutine required for numerous quantum algorithms, including linear system solvers, Hamiltonian simulation, quantum chemistry, and machine learning. The primary challenge lies in minimizing the circuit complexity (depth, gate count, and CNOT count) of the unitary operator $U$ that maps the initial state $|0\rangle^{\otimes n}$ to a desired target state $|\psi\rangle = \sum c_i |i\rangle$ . While the algorithm by Sun et al. (SUN) is known to be optimally bounded regarding the asymptotic space-time trade-off (utilizing ancillary qubits to reduce depth), its implementation involves a decomposition that uses three $\Lambda$ -type operators for each Uniformly Controlled Gate (UCG). This paper addresses the opportunity to reduce the circuit depth and gate counts of the SUN algorithm through a more efficient algebraic decomposition, particularly in the parametric range where the number of ancillary qubits $m$ satisfies $2^n \leq m \leq 2^n/n$ .

Methodology
The authors propose a novel QSP algorithm, termed OSUN, which introduces a simpler algebraic decomposition of the unitary operator. The core methodological shift involves separating the preparation of the desired state into two distinct unitary blocks:

Real Part ( $U_{mod}$ ): A unitary responsible for preparing the real moduli (amplitudes) of the target state coefficients.
Complex Part ( $D_{ph}$ ): A diagonal unitary responsible for applying the necessary complex phases.

In the traditional SUN framework, each UCG in the ladder structure is decomposed into three $\Lambda$ -type operators (handling diagonal phase shifts for real and complex components separately). The proposed OSUN algorithm exploits the fact that $U_{mod}$ only requires the preparation of real amplitudes. By restricting the UCGs in this block to $R_y$ -block diagonal matrices and utilizing a specific gate set change ( $R_y(\gamma) \equiv SH \cdot R_z(\gamma) \cdot HS^\dagger$ ), the authors demonstrate that each UCG in the real-part preparation can be implemented using a single $\Lambda$ -type operator instead of three. The complex phase information is then applied at the end of the circuit via a single, maximum-dimensional $\Lambda$ operator.

This decomposition allows for the parallelization of operations on the ancillary register using the same 5-stage Fourier space summation method established in previous SUN implementations, but with a reduced number of $\Lambda$ constructors per level.

Key Contributions
The paper outlines six specific contributions:

Optimization of SUN: A new QSP algorithm that improves upon the SUN algorithm in terms of depth and gate counts across the entire first range of the optimal space-time trade-off defined in Sun et al. [40, Theorem 1].
Algebraic Decomposition: A derivation showing that separating real and complex parts allows each UCG to be implemented with a single $\Lambda$ -type constructor, reducing the count from three to one per gate level.
Tighter Asymptotic Bounds: A formal analysis providing tighter asymptotic optimal bounds for the space-time trade-off in the specified parametric range.
Implementation: The full implementation of the OSUN algorithm using the PennyLane library, made available on GitHub.
Extensive Verification: A comprehensive battery of tests executed on the University of Parma's HPC system, covering dense and sparse states, random coefficients (real positive, real negative, complex), and physically relevant states (Bell, GHZ, W, Dicke) for qubit counts up to 10.
Comparative Analysis: A direct performance comparison with Möttönen et al.'s algorithm (the standard for QSP without ancillae) and the original SUN implementation, evaluating metrics such as depth, total gates, CNOT count, and gate types.

Results
Simulation results indicate that the OSUN algorithm achieves a systematic reduction in circuit depth compared to the original SUN implementation.

Complexity Analysis: Theoretical analysis confirms that while the asymptotic complexity class remains $O(n^2 + 2^n/m)$ , the prefactors of the dominant terms are significantly reduced. Specifically, the linear-logarithmic term ( $n \log m$ ) shows a factor of 3 improvement, and the exponential term ( $2^n/m$ ) shows a factor of 2 improvement.
Simulation Metrics: For random states with complex coefficients, OSUN demonstrates a shallower depth starting from 6 qubits compared to both the original SUN and Möttönen's algorithm. The growth curve of the depth is smoother than the original version.
Gate Counts: While OSUN reduces depth, the total number of gates and CNOTs does not show a reduction compared to Möttönen's algorithm. However, the authors note a shift in the gate set composition: Möttönen's approach uses CNOTs and rotations, whereas OSUN utilizes CNOTs and phase shifts (diagonal operators).
Fidelity: The algorithm maintains high fidelity (close to 1) and low trace distance across all tested state types and qubit counts (2 to 10).

Significance and Claims
The paper claims that the proposed algebraic reduction offers a practical improvement to the state-of-the-art SUN algorithm without altering its fundamental asymptotic complexity class. By reducing the constant factors in the depth and gate count, OSUN provides a more efficient circuit for state preparation in the regime where ancillary qubits are available ( $m \geq 2^n$ ). The authors position this work as a refinement of the optimal space-time trade-off, highlighting that the reduction in the number of $\Lambda$ operators (from 3 to 1 per UCG) is the primary driver of the performance gain.

The authors explicitly state that this optimization applies to the entire first parametric range of the optimal trade-off. They suggest that future work could extend these benefits to other points in the domain where ancillary registers grow exponentially. The paper concludes by noting that while OSUN improves depth, future investigations should address qubit connectivity on real hardware and the translation of these circuits into the Clifford+T gate set to fully assess their complexity in fault-tolerant contexts. The work does not claim to solve the general QSP problem for all hardware constraints but offers a specific, verified improvement to the SUN framework using existing ancillary strategies.