⚛️ quantum physics

Direct U(2) approximation via repeat-until-success circuits

This paper presents a method using repeat-until-success circuits and lattice-based tools to directly and efficiently approximate arbitrary one-qubit unitaries and orthogonal matrices with multi-qubit gate sets, bypassing traditional Euler decomposition and magnitude approximation issues at the cost of a single ancillary qubit.

Original authors: Vadym Kliuchnikov, Jendrik Brachter, Marcus P. da Silva

Published 2026-04-23

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Vadym Kliuchnikov, Jendrik Brachter, Marcus P. da Silva

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.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 complex machine (a quantum computer) that can only use a very specific, limited set of Lego bricks. These bricks are your "fault-tolerant gate sets" (like Clifford and CS gates). The problem is that the instructions for your machine require you to build a specific, smooth curve or a perfect circle. But you only have square and triangular bricks. You can't build a perfect circle with squares, so you have to approximate it by stacking them in a clever way.

For a long time, the standard way to do this was like trying to build a circle by first building a square, then a triangle, then a hexagon, and hoping they look like a circle when you step back. This is called Euler decomposition. It's a bit clunky and requires a lot of steps.

This paper introduces a smarter, more direct way to build that "circle" using a special trick involving a helper brick (an ancillary qubit) and a "try again" strategy.

Here is the breakdown of their method using everyday analogies:

1. The "Try Again" Machine (Repeat-Until-Success)

Imagine you are trying to pour a glass of water perfectly into a cup, but you are blindfolded.

The Old Way: You try to calculate the exact angle and distance, pour, and if you miss, you have to start over from scratch with a new, complex calculation.
The New Way (RUS): You set up a machine that pours water.
- Success: 99% of the time, the water lands perfectly in the cup. You are done!
- Failure: 1% of the time, the water spills. But instead of panicking, the machine has a "recovery mode." It instantly cleans up the spill and resets itself so you can try again immediately.

The paper shows how to build this machine so that the "Success" outcome creates the exact quantum operation you wanted, and the "Failure" outcome leaves the system in a state where you can just try again without losing any data.

2. The "Magic Helper" (The Ancillary Qubit)

To make this "Try Again" machine work, you need one extra Lego brick that isn't part of the final machine. This is the ancillary qubit.

Think of it like a safety net. You throw your main operation into the air. If it lands safely (Success), you catch it and use it. If it falls (Failure), the safety net catches it, and you know exactly how to fix it so you can throw it again.
The paper proves that using just one extra brick is enough to make this work for any single-qubit operation, skipping the messy "Euler decomposition" steps entirely.

3. The "Mathematical Treasure Hunt" (Lattice Enumeration)

How do you actually build the machine that has a 99% success rate?

Imagine you are looking for a specific key in a giant, multi-dimensional field of grass (a lattice).
The "grass" represents all the possible combinations of your limited Lego bricks.
You need to find a specific clump of grass (a set of integers) that, when you build a machine out of it, looks almost exactly like your target circle.
The authors developed a way to quickly scan this field to find the perfect clump of grass that fits your needs, ensuring the "Success" probability is high and the "circle" is accurate.

4. The "Backup Plan" (Norm Equations)

Once you find that perfect clump of grass for the "Success" part, you still need to account for the "Failure" part.

Imagine you have a budget of 100 points. You spend 98 points on the "Success" machine. You have 2 points left.
The paper uses a mathematical rule called the Four Squares Theorem (a famous number theory fact) to prove that you can always use those remaining 2 points to build a "Recovery Machine."
This ensures that no matter what happens, the math always adds up to 100%, and the system never gets stuck.

Why is this a big deal?

Directness: It skips the middleman. Instead of breaking the problem into smaller, awkward pieces, it builds the solution in one go.
Efficiency: It often results in shorter, faster circuits (fewer steps) compared to old methods.
Versatility: It works not just for standard quantum computers, but also for those using "real" numbers (orthogonal matrices) or more complex multi-qubit gates.

Summary

Think of this paper as a new blueprint for a self-correcting 3D printer.
Old printers tried to print a curved object by layering straight lines (Euler decomposition). This new printer uses a safety net (the extra qubit) and a smart scanning system (lattice enumeration) to print the curve directly. If the printer misses a tiny bit, it doesn't crash; it just resets and tries again instantly. The result is a faster, more reliable way to build the complex shapes needed for future quantum computers.

1. Problem Statement

The central challenge addressed is the approximate synthesis of arbitrary single-qubit unitaries ( $U \in U(2)$ ) for fault-tolerant quantum computing.

Context: Fault-tolerant architectures support only a discrete set of native gates (e.g., Clifford + T, Clifford + CS). Arbitrary unitaries cannot be synthesized exactly and must be approximated by sequences of these gates.
Limitations of Existing Methods: Traditional approaches typically rely on Euler angle decomposition, breaking a target unitary into rotations around fixed axes (e.g., $Z-Y-Z$ ), and then approximating each rotation separately. This introduces intermediate steps and often requires solving the "magnitude approximation problem" (finding a sequence with a specific norm).
Goal: To develop a method that directly approximates the full $U(2)$ matrix without intermediate decomposition, optimizing for circuit depth and gate counts, potentially at the cost of using one ancillary qubit.

2. Methodology

The authors propose a framework combining Repeat-Until-Success (RUS) circuits with lattice-based exact synthesis and number-theoretic techniques.

A. Repeat-Until-Success (RUS) Framework

The core mechanism uses a circuit with one ancillary qubit.

Circuit Structure: A unitary $W$ acts on the system qubit and the ancilla.
Measurement: The ancilla is measured.
- Success (Outcome 0): The system qubit undergoes the target unitary $R_0$ (approximation of $U$ ).
- Failure (Outcome $j > 0$ ): A recovery unitary $R_j$ is applied, and the circuit is repeated.
Probability: The success probability is $|\alpha_0|^2$ . By tuning parameters, the failure probability can be kept below a threshold $p$ .

B. The Three-Step Algorithm

To construct the unitary $W$ required for the RUS circuit, the authors employ a three-step process:

Point Enumeration (Convex Optimization):
- The goal is to find an integer vector $u_0 \in \mathbb{Z}^4$ corresponding to a matrix $U_0$ such that the normalized matrix $U_0/\|u_0\|$ is within distance $\epsilon$ of the target $U$ .
- Constraint Transformation: The approximation constraint $\|U_0/\|u_0\| - U\| \le \epsilon$ and the norm constraint $(1-p)2^N \le \langle u_0, u_0 \rangle \le 2^N$ are reformulated as convex constraints (specifically, a hyperbolic cone and linear inequalities).
- Solution: This reduces the problem to enumerating integer points within a convex body, solvable in polynomial time.
Norm Equation (Number Theory):
- Once $u_0$ is found, a second integer vector $u_1$ must be found to complete the isometry.
- Equation: Solve $\langle u_1, u_1 \rangle = 2^N - \langle u_0, u_0 \rangle$ .
- Theory: This is a variation of the Four Squares Theorem (Lagrange's theorem), ensuring a solution always exists. The authors relate this to finding quaternions in the Lipschitz order, which aids in generalizing to other gate sets.
Exact Synthesis of Isometries:
- Using the vectors $u_0$ and $u_1$ , the first two columns of the $4 \times 4$ unitary $W$ are constructed as a $4 \times 2$ isometry.
- Synthesis: Recent algorithms (based on $A^*$ search with heuristics) are used to find an exact circuit for $W$ over the specific gate set (e.g., Clifford + CS).
- Optimization: Since the relationship between the integer parameter $N$ and the final gate count is not strictly linear, the algorithm iterates over multiple solutions for $u_0$ and $u_1$ to find the circuit with the minimal cost.

3. Key Contributions

Direct U(2) Approximation: The method bypasses Euler decomposition entirely, approximating the full unitary matrix directly. This avoids the accumulation of errors and overhead associated with decomposing into rotations.
Ancilla-Assisted Efficiency: While it requires one ancillary qubit, the authors argue this trade-off yields shorter circuit depths and lower gate counts compared to ancilla-free methods or traditional decomposition strategies.
Generalizability: The framework is not limited to Clifford+T. It is explicitly demonstrated for:
- Clifford + CS (Complex orthogonal).
- Clifford + CCZ and Real Clifford + CCZ (Orthogonal matrices).
- Higher-degree number fields: The method extends to gate sets defined over fields like $\mathbb{Q}(\zeta_8)$ (Clifford+T) and $\mathbb{Q}(\sqrt{2})$ by utilizing embeddings of totally real subfields.
Handling Real Orthogonal Matrices: The paper provides a specific adaptation for approximating orthogonal matrices using real gate sets, discussing the necessity of adding extra qubits to ensure the norm equation has solutions (moving from 2-squares to 6-squares problems if necessary).

4. Results and Performance Characteristics

Success Probability: The algorithm guarantees a success probability of at least $1-p$ in the first iteration.
Accuracy: The resulting unitary $R_0$ satisfies $\|U - R_0\| \le \epsilon$ .
Gate Sets: The paper details compatibility with various gate sets defined in Table 2.1, including those involving $\sqrt{T}$ , $CS$, $CCZ$, and their real counterparts.
Theoretical vs. Practical: The paper establishes the theoretical basis (convex reduction, existence of solutions). It notes that the precise scaling of circuit cost with $\epsilon$ and $p$ requires numerical study, as the link between the algebraic parameter $N$ and the physical gate count is not yet tightly bounded analytically.

5. Significance

Architectural Flexibility: By offering a method that trades an ancilla qubit for reduced circuit depth, this approach provides a valuable alternative for quantum architectures where qubit connectivity or coherence time is the bottleneck, but ancilla availability is sufficient.
Unified Framework: It unifies the approximation of complex unitaries and real orthogonal matrices under a single mathematical framework based on RUS and lattice enumeration.
Beyond Decomposition: It challenges the standard paradigm of "decompose-then-approximate," suggesting that direct synthesis via probabilistic circuits can be more efficient for general $U(2)$ targets.
Foundation for Future Work: The paper sets the stage for optimizing the "point enumeration" and "norm equation" steps to minimize the specific gate counts for emerging fault-tolerant gate sets (like those based on CCZ or CS).

In summary, this paper presents a robust, number-theoretically grounded algorithm for directly synthesizing arbitrary single-qubit unitaries using repeat-until-success circuits, offering a compelling trade-off between ancilla usage and circuit efficiency while supporting a wide variety of fault-tolerant gate sets.