Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Congress on Evolutionary Computation (CEC)

Level Compaction in Quantum Circuits

D. Maslov, Gerhard W. Dueck

Published Sep 22, 2006• 15 citations
Publisher

Abstract

Efficiency of a quantum computation realized in a circuit form depends on many parameters including (but not limited to) the number of gates, the number of auxiliary bits and the number of logic levels. While researchers paid some attention to the minimization of the number of gates and the number of auxiliary bits, the problem of minimizing the number of levels was set aside. However, gates that do not involve the same bits may be applied in parallel. In this paper we present an automated level compactor for quantum circuits. At its core are the templates -a local optimization tool developed for quantum/reversible circuit simplification. We show how the templates can be applied to compact logic levels in quantum circuits, which extends the boundaries of their usefulness. While our method for level compaction is basic, its application to the benchmark circuit specifications shows it has good potential.

DOI
10.1109/cec.2006.1688606

Related papers

Quantum Circuit Simplification and Level Compaction

Dmitri A Maslov, Gerhard W. Dueck, D. Michael Miller +1 more

Quantum circuits are time-dependent diagrams describing the process of quantum computation. Usually, a quantum algorithm must be mapped into a quantum circuit. Optimal synthesis of quantum circuits is intractable, and heuristic methods must be employed. With the use of heuristics, the optimality of circuits is no longer guaranteed. In this paper, we consider a local optimization technique based on templates to simplify and reduce the depth of nonoptimal quantum circuits. We present and analyze templates in the general case and provide particular details for the circuits composed of NOT, CNOT, and controlled-sqrt-of-NOT gates. We apply templates to optimize various common circuits implementing multiple control Toffoli gates and quantum Boolean arithmetic circuits. We also show how templates can be used to compact the number of levels of a quantum circuit. The runtime of our implementation is small, whereas the reduction in the number of quantum gates and number of levels is significant.

arXiv:quant-ph/0604001•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Feb 21, 2008•252 citations

Quantum Circuit Simplification Using Templates

D. Maslov, Cho Eun Young, D. Michael Miller +1 more

Optimal synthesis of quantum circuits is intractable and heuristic methods must be employed. Templates are a general approach to reversible quantum circuit simplification. We consider the use of templates to simplify a quantum circuit initially found by other means. We present and analyze templates in the general case, and then provide particular details for circuits composed of NOT, CNOT and controlled-sqrt-of-NOT gates. We introduce templates for this set of gates and apply them to simplify both known quantum realizations of Toffoli gates and circuits found by earlier heuristic Fredkin and Toffoli gate synthesis algorithms. While the number of templates is quite small, the reduction in quantum cost is often significant.

Design, Automation, and Test in Europe•Apr 1, 2005•114 citations

An Algorithm for Quantum Template Matching

Md. Mazder Rahman, Gerhard W. Dueck, Joseph D. Horton

Quantum circuits are often generated by decomposing gates from networks with classical reversible gates. Only in rare cases, the results are minimal. Post-optimization methods, such as template matching, are employed to reduce the quantum costs of circuits. Quantum templates are derived from identity circuits. All minimal realizations, within certain limitations, can be embedded into templates. Due to this property, templates matching has the potential to reduce quantum costs of circuits. However, one of the difficulties in finding templates matches is due to the mobility of the gates within the circuit. Thus far, template matching procedures have employed heuristics to reduce the search space. This article presents an in-depth study of exact template matching with a set of algorithms. A graph structure with the corresponding circuits facilitates the discovery of potential sequences of templates to be matched, and how exact minimization of circuits can be accomplished. The significance of the proposed method is verified in benchmarks optimization.

ACM Journal on Emerging Technologies in Computing Systems•Dec 30, 2014•20 citations

An efficient algorithm to synthesize quantum circuits and optimization

Ömercan Susam, Mustafa Altun

Quantum computers, more specifically quantum circuits, take on the eyes with their computational promises such as reversibility. In this paper, we perform synthesis and optimization of quantum circuits. In the first part, we propose a fast synthesis algorithm that implements any given reversible Boolean function with quantum gates. Instead of an exhaustive search on every given function, our algorithm creates a library of essential functions and performs sorting. As an example, to implement 4 bit circuits we only use 120 essential functions out of all 20922789888000 functions. In the second part, we optimize our circuits by using new templates. The proposed templates mainly consist of Toffoli gates with negative and positive controlling lines. These templates also show us that optimum area solutions proposed in the literature are not actually optimum; they can be improved.

IEEE International Conference on Electronics, Circuits and Systems (ICECS)•Dec 1, 2014•2 citations

AN ALGORITHM FOR MINIMUM SPACE QUANTUM BOOLEAN CIRCUITS CONSTRUCTION

I-Ming Tsai, Sy‐Yen Kuo

Implementing a quantum computer at the circuit level has emerged as an important field of research recently. An important topic of building a general-purpose quantum computer is to implement classical Boolean logic using quantum gates and devices. Since the Toffoli gate is universal in classical Boolean logic, any classical combinational circuit can be implemented by the straightforward replacement algorithm with auxiliary qubits as intermediate storage. However, this inefficient implementation causes a large number of auxiliary qubits to be used. In this paper, a systematic procedure is proposed to derive a minimum space quantum circuit for a given classical combinational logic. We first formulate the problem of transforming an m-to-n bit classical Boolean logic into a t-bit unitary quantum operation. The eligible solution set is then constructed such that a solution can be found simply by selecting any member from this set. Finally, we show that the algorithm is optimal in terms of the space consumption.

Journal of Circuits Systems and Computers•Oct 1, 2006•17 citations

Quantum Circuit Template Matching Optimization Method for Constrained Connectivity

Xiaofeng Gao, Zhijin Guan, Shiguang Feng +1 more

The execution of quantum algorithms requires two key considerations. On the one hand, it should meet the connectivity constraint requirements of quantum circuit mapping for quantum architectures, and on the other hand, it needs to consider reducing the probability of errors in the execution of quantum circuits as much as possible. This paper proposes a novel optimization technique based on template matching that to satisfy both requirements. The template matching optimization method can significantly reduce the number of gates in a quantum circuit and further enhance its practicality. It stands as advanced optimization technology available today. Our method optimizes quantum logic circuits mapped onto quantum architecture by initially selecting their linear substructure. We then zone the circuit according to the gate dependency graph and optimize each block through template matching. Finally, we reorganize the circuit to obtain the optimized version as the final result. Our proposed method is amenable to various quantum architectures. To evaluate its efficacy, we conduct a comparative analysis with the t|ket⟩ and Qiskit compiler using a set of benchmark test circuits. Specifically, compare to the t|ket⟩ compiler method, the highest average optimization rate of our method can reach 25.75%. Compare with the Qiskit compiler method, the highest average optimization rate can reach 32.72%. Overall, our approach has significant optimization advantages.

Axioms•Jul 14, 2023•8 citations
Efficiency of a quantum computation realized in a circuit form depends on many parameters including (but not limited to) the number of gates, the number of auxiliary bits and the number of logic levels. While researchers paid some attention to the minimization of the number of gates and the number of auxiliary bits, the problem of minimizing the number of levels was set aside. However, gates that do not involve the same bits may be applied in parallel. In this paper we present an automated level compactor for quantum circuits. At its core are the templates -a local optimization tool developed for quantum/reversible circuit simplification. We show how the templates can be applied to compact logic levels in quantum circuits, which extends the boundaries of their usefulness. While our method for level compaction is basic, its application to the benchmark circuit specifications shows it has good potential.
Quantum circuits are time-dependent diagrams describing the process of quantum computation. Usually, a quantum algorithm must be mapped into a quantum circuit. Optimal synthesis of quantum circuits is intractable, and heuristic methods must be employed. With the use of heuristics, the optimality of circuits is no longer guaranteed. In this paper, we consider a local optimization technique based on templates to simplify and reduce the depth of nonoptimal quantum circuits. We present and analyze templates in the general case and provide particular details for the circuits composed of NOT, CNOT, and controlled-sqrt-of-NOT gates. We apply templates to optimize various common circuits implementing multiple control Toffoli gates and quantum Boolean arithmetic circuits. We also show how templates can be used to compact the number of levels of a quantum circuit. The runtime of our implementation is small, whereas the reduction in the number of quantum gates and number of levels is significant.
Optimal synthesis of quantum circuits is intractable and heuristic methods must be employed. Templates are a general approach to reversible quantum circuit simplification. We consider the use of templates to simplify a quantum circuit initially found by other means. We present and analyze templates in the general case, and then provide particular details for circuits composed of NOT, CNOT and controlled-sqrt-of-NOT gates. We introduce templates for this set of gates and apply them to simplify both known quantum realizations of Toffoli gates and circuits found by earlier heuristic Fredkin and Toffoli gate synthesis algorithms. While the number of templates is quite small, the reduction in quantum cost is often significant.
Quantum circuits are often generated by decomposing gates from networks with classical reversible gates. Only in rare cases, the results are minimal. Post-optimization methods, such as template matching, are employed to reduce the quantum costs of circuits. Quantum templates are derived from identity circuits. All minimal realizations, within certain limitations, can be embedded into templates. Due to this property, templates matching has the potential to reduce quantum costs of circuits. However, one of the difficulties in finding templates matches is due to the mobility of the gates within the circuit. Thus far, template matching procedures have employed heuristics to reduce the search space. This article presents an in-depth study of exact template matching with a set of algorithms. A graph structure with the corresponding circuits facilitates the discovery of potential sequences of templates to be matched, and how exact minimization of circuits can be accomplished. The significance of the proposed method is verified in benchmarks optimization.
Quantum computers, more specifically quantum circuits, take on the eyes with their computational promises such as reversibility. In this paper, we perform synthesis and optimization of quantum circuits. In the first part, we propose a fast synthesis algorithm that implements any given reversible Boolean function with quantum gates. Instead of an exhaustive search on every given function, our algorithm creates a library of essential functions and performs sorting. As an example, to implement 4 bit circuits we only use 120 essential functions out of all 20922789888000 functions. In the second part, we optimize our circuits by using new templates. The proposed templates mainly consist of Toffoli gates with negative and positive controlling lines. These templates also show us that optimum area solutions proposed in the literature are not actually optimum; they can be improved.
Implementing a quantum computer at the circuit level has emerged as an important field of research recently. An important topic of building a general-purpose quantum computer is to implement classical Boolean logic using quantum gates and devices. Since the Toffoli gate is universal in classical Boolean logic, any classical combinational circuit can be implemented by the straightforward replacement algorithm with auxiliary qubits as intermediate storage. However, this inefficient implementation causes a large number of auxiliary qubits to be used. In this paper, a systematic procedure is proposed to derive a minimum space quantum circuit for a given classical combinational logic. We first formulate the problem of transforming an m-to-n bit classical Boolean logic into a t-bit unitary quantum operation. The eligible solution set is then constructed such that a solution can be found simply by selecting any member from this set. Finally, we show that the algorithm is optimal in terms of the space consumption.
The execution of quantum algorithms requires two key considerations. On the one hand, it should meet the connectivity constraint requirements of quantum circuit mapping for quantum architectures, and on the other hand, it needs to consider reducing the probability of errors in the execution of quantum circuits as much as possible. This paper proposes a novel optimization technique based on template matching that to satisfy both requirements. The template matching optimization method can significantly reduce the number of gates in a quantum circuit and further enhance its practicality. It stands as advanced optimization technology available today. Our method optimizes quantum logic circuits mapped onto quantum architecture by initially selecting their linear substructure. We then zone the circuit according to the gate dependency graph and optimize each block through template matching. Finally, we reorganize the circuit to obtain the optimized version as the final result. Our proposed method is amenable to various quantum architectures. To evaluate its efficacy, we conduct a comparative analysis with the t|ket⟩ and Qiskit compiler using a set of benchmark test circuits. Specifically, compare to the t|ket⟩ compiler method, the highest average optimization rate of our method can reach 25.75%. Compare with the Qiskit compiler method, the highest average optimization rate can reach 32.72%. Overall, our approach has significant optimization advantages.