Optimizing Quantum Circuits, Fast and Slow

Title: Optimizing Quantum Circuits, Fast and Slow
Reviewer: The Guardian

---

Summary

The authors present GUOQ, a stochastic optimization algorithm for quantum circuits. The method is an application of simulated annealing that operates over a set of "circuit transformations" which unify two distinct optimization strategies: fast, local rewrite rules and slow, global unitary resynthesis. The latter is permitted to introduce a bounded degree of approximation error. The central claim is that this simple, unified approach significantly outperforms a wide range of state-of-the-art quantum circuit optimizers on benchmarks for both NISQ and FTQC architectures, primarily by achieving superior 2-qubit gate count reduction.

Strengths

1. Empirical Results: The numerical results presented, particularly for NISQ-era gate sets (Figure 8, page 8), are impressive on their face. The reported average 2-qubit gate reduction of 28% surpasses other superoptimizers and standard compilers by a significant margin under the specified experimental conditions.

2. Ablation Studies: The paper provides a clear justification for its hybrid approach through effective ablation studies. Figure 10 (page 9) convincingly demonstrates that the synergistic combination of rewrite rules and resynthesis is more powerful than either strategy in isolation. Furthermore, the analysis in Q3 (Figure 11, page 10) provides evidence that the authors' stochastic search is more effective than more structured approaches like sequential application or beam search for this problem.

3. Conceptual Framework: The abstraction of both rewriting and resynthesis into a common "circuit transformation" τ_ε (Section 4.1, page 5) is a clean and logical formalism. It provides a sound basis for composing approximate and exact operations, with the error bound proof (Theorem 4.2) providing a necessary, albeit straightforward, theoretical guarantee.

Weaknesses

My primary concerns with this work lie in the methodology's justification, the fairness of the experimental comparison, and the strength of the claims, particularly regarding the FTQC regime.

1. Methodological Novelty vs. Hyperparameter Tuning: The authors describe their algorithm as "radically simple." This is accurate; it is a direct application of simulated annealing, a well-established metaheuristic from the 1980s. The novelty therefore does not lie in the search algorithm itself but in its application. However, the performance of such an algorithm is critically dependent on its hyperparameters. The paper provides scant justification for its key choices:

   • The 1.5% probability of choosing the expensive resynthesis operation (Section 5.3, page 7) is presented as a fixed value with no justification.
   • The temperature parameter t is set to 10 based on an "empirical sweep" (Section Q1, page 8).
     These appear to be magic numbers. Without a thorough sensitivity analysis, it is impossible to know if the reported success is a general property of the method or the result of careful tuning to this specific benchmark suite. This raises serious questions about the method's robustness and generality.

2. Incongruous Experimental Comparison: The evaluation in Q1 compares GUOQ against a heterogeneous set of tools under a uniform one-hour time limit. This is a fundamentally flawed comparison. Tools like Qiskit and TKET are production compilers designed to produce reasonable results in seconds, not engage in hour-long superoptimization. Comparing them in this regime is an apples-to-oranges comparison that inflates GUOQ's apparent superiority. The only truly fair competitors in this setup are other superoptimizers like BQSKit, QUESO, and Quarl. While GUOQ performs well against them, the narrative of outperforming the entire field is based on this mismatched framing.

3. Overstated Claims in the FTQC Regime: The paper's claims of strong performance are significantly weakened in the FTQC setting. The primary goal for FTQC optimization is T-gate reduction, as T-gates are extremely expensive to implement fault-tolerantly. Figure 12 (page 11) clearly shows that the specialized optimizer PyZX substantially outperforms GUOQ on this critical metric. The authors concede this and pivot to showing that GUOQ can be used as a post-processing step to PyZX to reduce the secondary CX-gate metric (Figure 14, page 11). While this is a useful result, it directly contradicts the paper's central narrative of providing a single, unified framework that is broadly superior. The framework is demonstrably not the best for the most important FTQC optimization task.

4. Superficial Treatment of Approximation: The framework treats resynthesis as a black box that returns a circuit with some error ε. Theorem 4.2 provides a simple additive bound on this error. However, this treatment is superficial. It fails to discuss how accumulating approximation error might interact with the optimization process itself. For instance, an approximate subcircuit may no longer syntactically match the pattern of an exact rewrite rule, potentially closing off optimization pathways. The dynamics of searching through a space of approximate circuits are more complex than the paper acknowledges.

Questions to Address In Rebuttal

1. Please provide a sensitivity analysis for the key hyperparameters: the 1.5% resynthesis probability and the temperature t=10. How does the performance of GUOQ degrade as these values are perturbed? This is essential to establish the robustness of the method beyond the specific benchmarks used.

2. Can the authors justify the one-hour time limit comparison against fast production compilers? To make a more compelling case, please provide results comparing GUOQ to Qiskit and TKET at time scales relevant to their intended use (e.g., 10 seconds, 1 minute).

3. Please clarify the paper's primary claim in light of the FTQC results. Is GUOQ a comprehensive, unified optimizer that should be chosen over other tools, or is it a complementary technique that is best used in a pipeline with specialized optimizers like PyZX? The current framing is contradictory.

4. Could the authors elaborate on the interaction between approximate and exact transformations? Does the introduction of approximation error ε via resynthesis ever prevent the subsequent application of beneficial, exact rewrite rules that would have otherwise matched? Does your search algorithm account for this possibility?

Paper Title: Optimizing Quantum Circuits, Fast and Slow
Reviewer Persona: The Synthesizer (Contextual Analyst)

---

Summary

This paper presents GUOQ, a novel approach to quantum circuit optimization that elegantly unifies two traditionally disparate techniques: fast, local rewrite rules and slow, globally-aware unitary resynthesis. The core contribution is twofold. First, the authors introduce a clean theoretical framework that abstracts both optimization methods into a single concept: an (ε)-approximate circuit transformation. This provides a common language and allows for a formal analysis of error accumulation. Second, they propose a "radically simple" search algorithm inspired by simulated annealing to apply these transformations. This stochastic, lightweight approach randomly alternates between fast and slow optimization techniques on random subcircuits.

The central thesis, supported by an extensive empirical evaluation, is that this simple, randomized search strategy significantly outperforms more complex and structured state-of-the-art optimizers, including industrial toolkits like Qiskit/TKET and specialized superoptimizers like Quarl. The work makes a compelling "bitter lesson" argument for the power of scalable search over intricate, hand-crafted heuristics in the complex landscape of quantum circuit optimization.

---

Strengths

1. Conceptual Elegance and Unification: The paper's primary strength is its beautiful and effective unification of rewriting and resynthesis. By abstracting both into the transformation concept (Section 4.1, page 5), the authors provide a powerful and flexible framework. This is a significant intellectual contribution that simplifies the conceptual model of circuit optimization and allows disparate methods to be combined in a principled way.

2. A Compelling "Bitter Lesson" for Quantum Compilation: The work positions itself as an example of Rich Sutton's "bitter lesson," where simple methods that leverage computation (in this case, rapid random search) ultimately outperform more complex approaches based on human-designed heuristics or learning policies. The stunningly strong results against Quarl—a sophisticated reinforcement learning-based optimizer that requires a GPU (Figure 1, page 1; Figure 8, page 8)—provide powerful evidence for this claim. This is an important and timely perspective for the quantum compilation community, which is at risk of developing increasingly complex and brittle optimization strategies.

3. Extensive and Convincing Empirical Evaluation: The evaluation is thorough and robust. The authors compare GUOQ against seven state-of-the-art tools on a diverse benchmark suite of 247 circuits. They consider multiple gate sets (IBMQ, IonQ, etc.) and crucially, address optimization objectives for both the NISQ and FTQC eras (Sections Q1-Q4). The results are not just incrementally better; they are substantially and consistently superior across most benchmarks and metrics. The ablation study in Q2 (Figure 10, page 9) effectively demonstrates the synergy between rewriting and resynthesis, showing that the whole is truly greater than the sum of its parts.

4. Flexibility and Synergy with Existing Tools: The framework is not presented as a monolithic replacement for all other tools, but as a flexible engine. The experiment in Q4 where GUOQ is used to post-process the output of PyZX is particularly insightful (Figure 14, page 11). It shows that GUOQ can drastically reduce the CX-count of circuits already optimized for T-count by a domain-specific tool. This demonstrates its potential as a powerful, general-purpose component in a larger, multi-stage compilation toolchain, capable of optimizing for multifaceted objectives.

---

Weaknesses

While the paper is excellent, a few points could be strengthened to further solidify its contribution:

1. Analysis of the Search Landscape: The paper convincingly shows that the randomized approach works well, but could benefit from a more explicit discussion of why. The optimization landscape for quantum circuits is likely vast, non-convex, and riddled with local minima. A structured search (like beam search in GUOQ-BEAM, Figure 11, page 10) or a fixed sequence of passes (like in Qiskit) can easily get trapped. The authors hint that resynthesis allows the search to "teleport" to new regions of the solution space (Section 3, page 5). A more direct and detailed discussion of this intuition would elevate the paper's theoretical contribution beyond just the empirical results.

2. Sensitivity to Hyperparameters: The algorithm's simplicity is a major strength, but it relies on a few key hyperparameters, namely the simulated annealing temperature t and the probability of choosing resynthesis (set to 1.5% in Section 5.3, page 7). The paper mentions that t=10 was chosen empirically, but a brief discussion on the sensitivity of the results to these choices would be valuable. Is the performance robust across a range of values, or is it highly tuned? This is important for understanding the algorithm's practicality.

3. Future Scalability of Random Subcircuit Selection: The current strategy of random subcircuit selection appears highly effective. However, as quantum circuits scale to millions of gates and thousands of qubits, one can imagine that purely random sampling might become inefficient, spending most of its time on non-optimizable regions. While beyond the scope of this paper's evaluation, a brief discussion on potential future scaling challenges and whether a hybrid approach (e.g., lightweight heuristics to bias the "random" selection) might eventually be necessary would show foresight.

---

Questions to Address In Rebuttal

1. The comparison against GUOQ-BEAM (Figure 11, page 10) is very interesting. It suggests that making many rapid, stochastic moves is more effective than carefully cultivating a smaller set of high-quality candidates. Could you elaborate on your intuition for why beam search, a powerful technique in many other search domains, falls short here? Does this reveal something fundamental about the structure of the quantum circuit optimization problem?

2. Could you comment on the sensitivity of GUOQ's performance to its key hyperparameters, specifically the simulated annealing temperature t and the 1.5% probability of invoking resynthesis? How does the balance between "fast" and "slow" moves affect convergence, and is there a risk of "over-exploring" with resynthesis if the probability is set too high?

3. The paper makes a compelling argument for the power of simple, randomized search today. Looking ahead to the fault-tolerant era with potentially millions of gates, do you foresee any fundamental scaling limitations to the random subcircuit selection strategy? Would the "bitter lesson" still hold, or might there be a place for more structured or guided search techniques to work in concert with the stochastic engine you have proposed?

Reviewer: The Innovator (Novelty Specialist)

Summary

This paper presents GUOQ, a quantum circuit optimizer that aims to unify two distinct optimization strategies: fast, local rewrite rules and slow, global unitary resynthesis. The authors propose a formal framework that treats both strategies as abstract "circuit transformations" with an associated error ε. The core of their contribution is a "radically simple" algorithm based on simulated annealing to stochastically apply these transformations to subcircuits, searching for a lower-cost circuit configuration under a global error budget. The empirical results are strong, showing significant improvements in gate count reduction over several state-of-the-art optimizers.

The central novel claim is not the invention of a new optimization algorithm, but rather the insight that a well-established, simple stochastic search heuristic, when applied to a unified set of both fast (rewrite) and slow (resynthesis) transformations, can dramatically outperform more complex, domain-specific search strategies in quantum circuit optimization.

Strengths

The primary strength of this work lies in its compelling empirical demonstration. The authors show that a conceptually simple approach can outperform more sophisticated and computationally expensive methods, such as the reinforcement learning-based Quarl [32]. This is a valuable "bitter lesson" [62] style contribution for the quantum compiler community. The proposed framework for unifying transformations under a single abstraction with a composable error bound (Section 4) is clean and provides a solid foundation for the algorithm.

Weaknesses

My evaluation focuses exclusively on the novelty of the core ideas presented. From this perspective, the paper's contributions are more evolutionary than revolutionary. The core algorithmic machinery is a direct application of pre-existing and well-understood concepts.

1. The Core Algorithm is Not Novel: The proposed search strategy is explicitly described as being "inspired by simulated annealing" [28], a 40-year-old optimization heuristic. The process of maintaining a candidate solution, proposing a random "move" (in this case, applying a transformation τ_ε), and probabilistically accepting it based on a cost function is textbook simulated annealing or, more broadly, a Metropolis-Hastings style MCMC search.

2. Strong Precedent in Classical Superoptimization: The high-level concept of using stochastic MCMC search to find optimal program representations is the cornerstone of classical superoptimization. Specifically, STOKE [55] (Schkufza et al., 2013) uses MCMC to search the space of x86 assembly programs. STOKE's methodology is conceptually identical to GUOQ's: it randomly mutates a program (the "move") and uses a cost function and correctness checks (the "acceptance probability") to guide the search toward an optimal equivalent program. GUOQ can be accurately characterized as an instantiation of the STOKE methodology in the quantum domain, where the "mutations" are applications of rewrite rules or resynthesis instead of changes to opcodes and operands. While the domain and specific transformations are new, the foundational search paradigm is not. The paper mentions STOKE in its related work (Section 7), but it does not sufficiently address this deep conceptual overlap.

3. The Unifying Framework Builds Directly on Prior Art: The framework for composing transformations with error bounds is presented as a key contribution. However, the theoretical heavy lifting for composing approximate operations appears to be borrowed from prior work. The proof of Theorem 4.2, which provides the additive upper bound on error, explicitly relies on the analysis from Patel et al. [45] (QUEST). The novelty here is the abstraction of packaging both exact rewrite rules (ε=0) and approximate resynthesis (ε>0) into this existing error-composition model, which is a useful engineering abstraction but not a fundamental theoretical advance.

The "delta" between this work and the prior art is therefore the application of a classical stochastic superoptimization strategy to a new set of operators (quantum rewrite rules and resynthesis) in the quantum domain. The key contribution is the insight that this simple, non-novel combination is highly effective, not the invention of the combination itself.

Questions to Address In Rebuttal

1. The authors frame GUOQ as a "radically simple algorithm." Given the direct mapping to simulated annealing and the strong conceptual precedent set by MCMC-based classical superoptimizers like STOKE [55], could the authors more precisely articulate what, if any, part of the core search algorithm is novel? Please position your work more directly against STOKE and clarify why it should be considered more than a straightforward application of that search paradigm to the quantum domain.

2. The paper claims to "unify two disparate ideas" (Abstract, page 1). Is the novelty in the idea of combining them, or in the specific method of randomized interleaving that the simulated annealing approach provides? Many compilers combine disparate optimization techniques using a fixed pass schedule. Is the primary insight here that for quantum circuits, a randomized schedule is superior to a deterministic one?

3. The ablation study in Q3 (Figure 11, page 10) compares GUOQ to fixed-sequence and beam-search alternatives. This convincingly shows GUOQ's search strategy is effective. Does this effectiveness stem primarily from the tight, random interleaving of fast and slow operations, or from the stochastic nature of the search which allows it to escape local minima that trap deterministic or more greedy approaches like beam search? A clearer diagnosis of why this well-known algorithm works so well here would strengthen the paper's contribution.