Beyond Reinforcement Learning: Fast and Scalable Quantum Circuit Synthesis

1. Problem Definition: Quantum Unitary Synthesis (QUS)

The core problem addressed is Quantum Unitary Synthesis (QUS): the task of translating an abstract target unitary matrix ($U^\star$) into a sequence of hardware-executable quantum gates from a specific set (e.g., Clifford+T).

• Challenge: The search space for gate sequences grows exponentially with the number of qubits and circuit depth.
• Limitations of Existing Methods:
  • Exact Optimization: Methods like mixed-integer programming (e.g., QuantumCircuitOpt) are computationally infeasible for larger circuits due to combinatorial explosion.
  • Heuristic Search: Simulated annealing or genetic algorithms often struggle with scalability and finding optimal solutions in complex regimes.
  • Reinforcement Learning (RL): Recent RL-based approaches (e.g., AlphaZero variants) show promise but suffer from high training costs, poor generalization across different qubit counts (requiring retraining for each $n$), and difficulty in optimizing for high T-count circuits.
  • Objective Mismatch: Standard numerical distance metrics (e.g., Hilbert-Schmidt distance) do not correlate well with the "symbolic" difficulty of a circuit, leading to suboptimal search guidance.

2. Methodology

The authors propose a Reinforcement Learning-free approach that combines Supervised Learning (SL) with Stochastic Beam Search, guided by the Minimum Description Length (MDL) principle.

A. The MDL Framework

Instead of minimizing numerical error, the method frames synthesis as finding the shortest sequence of gates (minimum description length) to represent a residual unitary.

• Residual Unitary: Given a partial circuit prefix $C_{1:t}$ with unitary $U_{1:t}$, the residual is $R_t = U_{1:t}^\dagger U^\star$.
• Goal: Predict the remaining gate count required to synthesize $R_t$ to the identity. This acts as a heuristic value function for the search.

B. Supervised Learning for MDL Prediction

• Model Architecture: A lightweight Multi-Layer Perceptron (MLP) (hidden dimensions 1024, 512, 128). Surprisingly, this outperformed Transformer architectures in this specific task.
• Input Representation: The residual unitary matrix is converted to a real-valued tensor by stacking real and imaginary parts. Crucially, a global phase normalization is applied to ensure invariance to unobservable global phases.
• Training Data Generation:
  • Synthetic data is generated via rejection sampling of random Clifford+T circuits.
  • Curriculum Learning: The dataset is biased toward "hard" states (high T-counts) by strategically cutting circuits at non-Clifford structure points to create diverse residual targets.
  • Labels: The "ground truth" label is the gate count of a heuristic-optimized suffix of the circuit, serving as a proxy for the true MDL.
• Training Cost: Significantly lower than RL; takes ~6 hours on standard hardware (30 CPU cores, 4GB GPU) compared to days for RL baselines.

C. Inference: Stochastic Beam Search

• Search Strategy: The trained MLP acts as a value function ($V^*(R_t) \approx -f_\theta(R_t)$) to guide a beam search.
• Stochastic Selection: To avoid getting stuck in local optima, the method uses Gumbel-top-B sampling. It adds Gumbel noise to the negative predicted MDL scores before selecting the top $B$ candidates. This balances exploration and exploitation without the overhead of complex RL training.
• Zero-Shot Generalization: A single model trained on $n=5$ qubits is used for all evaluations. For $n < 5$, the target unitary is padded with identity matrices ($U_{pad} = U \otimes I$). The model generalizes effectively without retraining.

3. Key Contributions

1. MDL-Guided Synthesis: Formulates QUS as estimating the remaining optimal gate cost using MDL, providing a structurally meaningful heuristic that outperforms numerical distance metrics.
2. Lightweight & Efficient: Demonstrates that a simple MLP is sufficient and faster than complex Transformers or RL agents, drastically reducing training overhead.
3. Zero-Shot Scalability: Achieves generalization across different qubit counts ($n=2$ to $5$) using a single model, eliminating the need for per-qubit-count retraining required by prior RL methods.
4. State-of-the-Art Performance: Surpasses existing classical and RL-based baselines in both synthesis success rate and wall-clock time, particularly for complex, high-T-count circuits.

4. Experimental Results

The method was evaluated on synthetic data and the QAS-Bench (Quantum Algorithm Synthesis Benchmark) suite.

• Success Rate:
  • On 4 and 5-qubit instances with high T-counts (up to 20), the proposed method maintained high success rates, whereas RL baselines dropped off significantly and simulated annealing failed on most hard instances.
  • On QAS-Bench, the method achieved 15/15 success in almost every bucket (varying qubit counts and layer depths), outperforming brute force, genetic algorithms, and differentiable search (DQAS).
• Runtime & Efficiency:
  • Wall-Clock Time: Achieved an average runtime of ~22 seconds per instance (with a fixed budget of 8,000 trials).
  • Comparison: Outperformed Synthetiq (simulated annealing) which took longer and produced larger circuits, and QuantumCircuitOpt which timed out (>1 hour) on all tested instances.
  • Solution Quality: Consistently returned the smallest gate counts, matching brute-force optima where feasible, and producing compact circuits where brute force was intractable.
• Zero-Shot Capability: The model trained on 5 qubits successfully synthesized circuits for 2, 3, and 4 qubits without any fine-tuning.

5. Significance and Impact

• Paradigm Shift: Moves away from expensive Reinforcement Learning training toward efficient Supervised Learning for heuristic generation in quantum compilation.
• Scalability: Addresses the critical bottleneck of scaling quantum circuit synthesis to larger qubit counts and deeper circuits, a prerequisite for practical fault-tolerant quantum computing.
• Practicality: The combination of a lightweight predictor and stochastic beam search offers a practical, deployable heuristic that improves both the speed and quality of circuit generation, making it a viable tool for automated quantum compiler design.

Limitations: The method still relies on dense matrix representations ($\Theta(4^n)$ memory), limiting practical application to small-to-medium qubit counts ($n \le 5$ in this study). However, within this regime, it significantly improves efficiency over existing state-of-the-art methods.