⚛️ quantum physics

Quantum Circuit Pre-Synthesis: Learning Local Edits to Reduce $T$ -count

This paper introduces \textsc{Q-PreSyn}, a reinforcement learning-based strategy that optimizes quantum circuit representations through local edits to achieve up to a 20% reduction in $T$ -count without introducing approximation errors, thereby enhancing the feasibility of fault-tolerant quantum computing.

Original authors: Daniele Lizzio Bosco, Lukasz Cincio, Giuseppe Serra, M. Cerezo

Published 2026-01-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Daniele Lizzio Bosco, Lukasz Cincio, Giuseppe Serra, M. Cerezo

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

The Big Picture: The "Toll Booth" Problem

Imagine you are trying to drive a car (a quantum computer program) from one city to another. To get there, you must pass through a series of toll booths. Most of these booths are free and easy to pass (these are the standard, easy gates in quantum computing). However, there is one specific type of toll booth called the "T-gate."

Passing through a T-gate is incredibly expensive, slow, and difficult. In fact, if you have too many T-gates, you might not be able to afford the trip at all, or the car might break down before you finish.

The problem is that when engineers design these routes (quantum circuits), they often accidentally create paths that go through way too many of these expensive T-gates. Sometimes, the route looks efficient on a map, but because of how the roads are laid out, it forces the car to stop at the toll booth unnecessarily.

The Solution: "Pre-Synthesis" (The Map Redrawer)

The authors of this paper propose a new tool called Q-PreSyn. Think of this not as a new car, but as a smart GPS that redraws your map before you even start driving.

Before the computer tries to build the actual expensive route (a process called "synthesis"), Q-PreSyn looks at the map and asks: "Can we rearrange these road segments to avoid the toll booths?"

It does this by performing "local edits." Imagine you have a string of beads. If you have a red bead followed immediately by a blue bead, and then another red bead, maybe you can snap them together into a single, new bead that does the exact same thing but takes up less space.

How It Works: The "Merge" Magic

The tool uses two main tricks to simplify the map:

The Single-File Merge: If you have a long line of single-lane roads (single-qubit gates) one after another, the tool snaps them together into one big road.
- Analogy: Imagine you have to turn left, then immediately turn right, then immediately turn left again. Instead of driving three separate turns, the GPS realizes you can just drive straight.
The Double-File Merge: If two lanes of traffic (two-qubit gates) are running parallel and interacting, the tool merges them into a single, more efficient interaction.
- Analogy: Imagine two people passing notes back and forth. Instead of passing five separate notes, they write one big letter that says everything.

The Catch: Sometimes, merging things in the wrong order makes the map more complicated. If you merge the wrong two roads first, you might block a shortcut you could have taken later. This is like trying to solve a puzzle where moving one piece makes it harder to fit the others.

The Brain: Reinforcement Learning (The Smart Student)

Because there are so many ways to rearrange the roads, a simple rule like "always merge the first two you see" (a "greedy" approach) doesn't work well. It might take a shortcut that leads to a dead end later.

To solve this, the authors used Reinforcement Learning (RL).

The Analogy: Imagine a student learning to solve a maze. At first, they just guess. Every time they find a shorter path, they get a treat (a reward). Every time they hit a wall or take a long path, they get a "no."
Over time, the student (the AI agent) learns the best sequence of moves. It learns that sometimes you have to take a slightly longer path now to unlock a massive shortcut later.

The AI doesn't just look at the immediate next step; it looks at the whole journey to find the sequence of merges that results in the fewest T-gates.

What They Found (The Results)

The team tested this "smart GPS" on many different quantum circuits, ranging from small ones (4 qubits) to larger ones (up to 25 qubits). They used it before running standard, well-known compilation methods.

The Result: In almost every case, the AI found a way to rearrange the circuit that reduced the number of expensive T-gates by 10% to 20%.
The Bonus: In some cases, the AI even reduced the total "error" of the route, making the trip more accurate, not just cheaper.
The Trade-off: Training the AI takes time (hours), but once trained, it can find better solutions than a simple, fast rule-based system. For very large circuits, the simple system is faster, but the AI gets better results.

Summary

In short, this paper introduces a method to rearrange quantum circuits before they are built. By using an AI to learn the best way to "merge" small parts of the circuit, they can significantly reduce the number of expensive, difficult-to-build components (T-gates). This doesn't change the math of the quantum computer; it just finds a smarter, cheaper way to draw the blueprint.

Key Takeaway: You don't need a better engine (hardware) to drive further; sometimes, you just need a better map (software optimization) to avoid the tolls.

Technical Summary: Quantum Circuit Pre-Synthesis (Q-PreSyn)

Problem Statement

Fault-tolerant quantum computing (FTQC) relies on decomposing unitary operations into sequences of gates from a discrete set, typically Clifford+T. In this regime, the T-count (the number of T gates) is the dominant cost metric, as T gates require expensive magic state injection or synthesis procedures.

While global synthesis (decomposing an entire $n$ -qubit unitary directly) is computationally intractable for large systems due to exponential scaling, practical compilers rely on local synthesis. This approach decomposes a circuit into smaller subcircuits (e.g., acting on 1 or 2 qubits), synthesizes them independently, and recombines them. However, a critical limitation exists: the quality of the final decomposition is highly sensitive to the circuit representation (i.e., how the unitary is factorized into local gates) prior to synthesis.

Equivalent circuit representations can yield vastly different T-counts. For instance, synthesizing two consecutive single-qubit rotations $R_z(\alpha_1)$ and $R_z(\alpha_2)$ independently often results in double the T-count compared to synthesizing their combined rotation $R_z(\alpha_1 + \alpha_2)$ directly. Current compilers often fail to identify these optimal representations, leading to suboptimal T-counts. The central question addressed is: Given a quantum circuit and a local synthesis algorithm, can we determine a circuit representation that enables more efficient synthesis?

Methodology: Q-PreSyn

The authors propose Q-PreSyn, a pre-synthesis framework that optimizes the circuit representation before the actual synthesis step. The method treats the search for an optimal representation as a planning problem solved via Reinforcement Learning (RL).

1. Action Space: Unitary-Preserving Merges

The framework operates by applying "merge" operations that preserve the global unitary implemented by the circuit but alter its local structure.

Single Qubit Merge: Consecutive unitaries acting exclusively on a single qubit $i$ are replaced by their product $W = U_{n_k} \dots U_{n_1}$ .
Two Qubit Merge: Consecutive unitaries acting exclusively on a pair of qubits $(i, j)$ are replaced by their product.
Constraints: The authors restrict merges to 1 or 2 qubits. While $K$ -qubit merges are theoretically possible, the search space grows combinatorially ( $\binom{n}{k}$ ), and synthesizing larger subcircuits is exponentially harder.

2. Planning as a Sequential Decision Problem

The sequence of merges is defined as a plan $\pi = (a_1, a_2, \dots, a_m)$ . The order of operations matters; applying merges in different sequences can lead to vastly different final representations (e.g., merging gates that cancel out vs. merging gates that create complex entanglement).
The objective is to find a plan $\pi^*$ that minimizes the cost function $L$ , defined as the T-count of the circuit after synthesis by a black-box local algorithm $A$ :
$\pi^* = \arg \min_{\pi \in \Pi} L(A(C_\pi))$

3. Search Strategies

To navigate the large combinatorial space of plans, the authors evaluate two strategies:

Greedy Search: Iteratively selects the merge action that yields the immediate largest reduction in T-count. This serves as a baseline but may miss global optima due to short-sightedness.
Reinforcement Learning (RL): The plan construction is modeled as a sequential decision process.
- Agent: Implemented using Proximal Policy Optimization (PPO).
- State: A three-channel tensor ( $n \times n \times 3$ ) encoding T-gate counts, potential mergeable gates, and a binary matrix representing the merge history.
- Reward: The immediate reduction in T-count upon synthesis.
- Refinement: To mitigate RL stochasticity, plans generated by the RL agent are further refined using a greedy completion strategy (evaluating greedy extensions for every prefix of the RL plan).

4. Implementation Details

Memoization: To reduce computational overhead, the system caches synthesized decompositions for unitary blocks encountered during the search.
Synthesis Algorithms: The framework is synthesis-agnostic. Experiments utilize combinations of decomposition tools (KAK, BQSKit) and synthesis algorithms (Solovay-Kitaev, Gridsynth).

Key Contributions

Q-PreSyn Framework: A novel approach for representation-level optimization of quantum circuits, distinct from the synthesis algorithm itself. It modifies circuit structure via unitary-preserving merges to improve downstream synthesis efficiency.
Formalization of Plan Optimization: The problem of identifying advantageous merge sequences is formalized as a plan optimization task. The authors demonstrate that RL can effectively explore this space, uncovering long-term dependencies between merges that greedy strategies miss.
Universal Preprocessing: The method is designed as a universal preprocessing stage compatible with any local synthesis pipeline (e.g., Gridsynth, Solovay-Kitaev, matchgate synthesis).
Open Source: The authors provide all code necessary to reproduce the method and experiments.

Experimental Results

The authors evaluated Q-PreSyn on various tasks, including random circuits, linear connectivity circuits, real-time dynamics of the Quantum Ising model, and matchgate circuits.

T-Count Reduction: Across different synthesis frameworks and circuit types, Q-PreSyn achieved T-count reductions ranging from 10% to 25%.
- Random Circuits: Up to 20% reduction for Gridsynth+BQSKit; 10–18% for KAK-based methods.
- Scalability: The method was tested on circuits up to 25 qubits. While RL agents provided better reductions than greedy agents on smaller circuits, the greedy agent remained effective and computationally cheaper for larger scales (up to 25 qubits).
Approximation Error: The pre-synthesis process does not introduce additional approximation error. In fact, by reducing the number of synthesis steps (merging gates before synthesis), the total accumulated approximation error often decreases compared to direct synthesis.
Comparison of Strategies: RL-based strategies generally outperformed greedy baselines, particularly in finding plans with longer sequences of merges that unlock larger reductions. However, the computational cost of training RL agents (hours) is significantly higher than greedy search (minutes).

Significance and Limitations

The paper positions Q-PreSyn as a practical, synthesis-agnostic technique to lower the cost of fault-tolerant implementations without altering the underlying synthesis algorithms. By treating circuit representation as an optimizable object, the work bridges the gap between high-level algorithmic descriptions and low-level hardware constraints.

Limitations and Future Directions noted by the authors:

Search Space Complexity: Exploring merges on more than two qubits could yield further savings but is currently limited by the exponential growth of the search space and synthesis difficulty.
Scalability of RL: Training RL agents for very large circuits remains computationally demanding. The authors suggest hybrid strategies (combining RL with Monte Carlo Tree Search or curriculum learning) to improve scalability.
Topology and Benchmarks: Future work should integrate topology awareness and standardized benchmark suites to facilitate broader comparison and deployment in end-to-end compilers.

In summary, the authors claim that learning-guided structural transformations are a viable and effective method for reducing non-native gate costs in fault-tolerant synthesis, offering a significant improvement over current standard compilation pipelines.