Near-term quantum computers are expected to work in an environment where each operation is noisy, with no error correction. Therefore, quantum-circuit optimizers are applied to minimize the number of noisy operations. Today, physicists are constantly experimenting with novel devices and architectures. For every new physical substrate and for every modification of a quantum computer, we need to modify or rewrite major pieces of the optimizer to run successful experiments. In this paper, we present QUESO, an efficient approach for automatically synthesizing a quantum-circuit optimizer for a given quantum device. For instance, in 1.2 minutes, QUESO can synthesize an optimizer with high-probability correctness guarantees for IBM computers that significantly outperforms leading compilers, such as IBM's Qiskit and TKET, on the majority (85%) of the circuits in a diverse benchmark suite. A number of theoretical and algorithmic insights underlie QUESO: (1) An algebraic approach for representing rewrite rules and their semantics. This facilitates reasoning about complex symbolic rewrite rules that are beyond the scope of existing techniques. (2) A fast approach for probabilistically verifying equivalence of quantum circuits by reducing the problem to a special form of polynomial identity testing . (3) A novel probabilistic data structure, called a polynomial identity filter (PIF), for efficiently synthesizing rewrite rules. (4) A beam-search-based algorithm that efficiently applies the synthesized symbolic rewrite rules to optimize quantum circuits.Near-term quantum computers are expected to work in an environment where each operation is noisy, with no error correction. Therefore, quantum-circuit optimizers are applied to minimize the number of noisy operations. Today, physicists are constantly experimenting with novel devices and architectures. For every new physical substrate and for every modification of a quantum computer, we need to modify or rewrite major pieces of the optimizer to run successful experiments. In this paper, we present QUESO, an efficient approach for automatically synthesizing a quantum-circuit optimizer for a given quantum device. For instance, in 1.2 minutes, QUESO can synthesize an optimizer with high-probability correctness guarantees for IBM computers that significantly outperforms leading compilers, such as IBM's Qiskit and TKET, on the majority (85%) of the circuits in a diverse benchmark suite. A number of theoretical and algorithmic insights underlie QUESO: (1) An algebraic approach for representing rewrite rules and their semantics. This facilitates reasoning about complex symbolic rewrite rules that are beyond the scope of existing techniques. (2) A fast approach for probabilistically verifying equivalence of quantum circuits by reducing the problem to a special form of polynomial identity testing . (3) A novel probabilistic data structure, called a polynomial identity filter (PIF), for efficiently synthesizing rewrite rules. (4) A beam-search-based algorithm that efficiently applies the synthesized symbolic rewrite rules to optimize quantum circuits.

arXiv:2211.09691Proceedings of the ACM on Programming LanguagesJun 6, 202342 citations

Scalable Quantum Circuit Optimization Using Automated Synthesis

Xin-Chuan Wu, Costin Iancu, Frederic T. Chong

Bulletin of the American Physical SocietyMar 16, 20210 citations

Unitary synthesis with optimal brick wall circuits

David Wierichs, Korbinian Kottmann, Nathan Killoran

We present quantum circuits with a brick wall structure using the optimal number of parameters and two-qubit gates to parametrize $SU(2^n)$ , and provide evidence that these circuits are universal for $n\leq 5$ . For this, we successfully compile random matrices to the presented circuits and show that their Jacobian has full rank almost everywhere in the domain. Our method provides a new state of the art for synthesizing typical unitary matrices from $SU(2^n)$ for $n=3, 4, 5$ , and we extend it to the subgroups $SO(2^n)$ and $Sp^\ast(2^n)$ . We complement this numerical method by a partial proof, which hinges on an open conjecture that relates universality of an ansatz to it having full Jacobian rank almost everywhere.We present quantum circuits with a brick wall structure using the optimal number of parameters and two-qubit gates to parametrize $SU(2^n)$, and provide evidence that these circuits are universal for $n\leq 5$. For this, we successfully compile random matrices to the presented circuits and show that their Jacobian has full rank almost everywhere in the domain. Our method provides a new state of the art for synthesizing typical unitary matrices from $SU(2^n)$ for $n=3, 4, 5$, and we extend it to the subgroups $SO(2^n)$ and $Sp^\ast(2^n)$. We complement this numerical method by a partial proof, which hinges on an open conjecture that relates universality of an ansatz to it having full Jacobian rank almost everywhere.

quant-pharXiv:2511.16736Nov 24, 20250 citations

Optimal SAT Solver Synthesis of Quantum Circuits Representing Cryptographic Nonlinear Functions

Adam Jagielski

In this article we present a procedure that allows to synthesize optimal circuit representing any reversible function within reasonable size limits. The procedure allows to choose either the NCT or the MCT gate set and specify any number of ancillary qubits to be used in the circuit. We will explore efficacy of this procedure by synthesizing various sources of nonlinearity used in contemporary symmetric ciphers and draw conclusions about properties of those transformations in quantum setting. In particular we will try to synthesize optimal circuit representing ASCON cipher SBOX which recently won NIST competition for Lightweight Cryptography standard.In this article we present a procedure that allows to synthesize optimal circuit representing any reversible function within reasonable size limits. The procedure allows to choose either the NCT or the MCT gate set and specify any number of ancillary qubits to be used in the circuit. We will explore efficacy of this procedure by synthesizing various sources of nonlinearity used in contemporary symmetric ciphers and draw conclusions about properties of those transformations in quantum setting. In particular we will try to synthesize optimal circuit representing ASCON cipher SBOX which recently won NIST competition for Lightweight Cryptography standard.

International Journal of Electronics and TelecommunicationsMay 31, 20231 citation

Synthesis of Quantum Circuits

Philipp Niemann, Robert Wille

SpringerBriefs in physicsJan 1, 20170 citations

We present quantum circuits with a brick wall structure using the optimal number of parameters and two-qubit gates to parametrize

SU(2^n)

, and provide evidence that these circuits are universal for

n\leq 5

. For this, we successfully compile random matrices to the presented circuits and show that their Jacobian has full rank almost everywhere in the domain. Our method provides a new state of the art for synthesizing typical unitary matrices from

SU(2^n)

for

n=3, 4, 5

, and we extend it to the subgroups

SO(2^n)

and

Sp^\ast(2^n)

. We complement this numerical method by a partial proof, which hinges on an open conjecture that relates universality of an ansatz to it having full Jacobian rank almost everywhere.