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 International Symposium on Multiple-Valued Logic (ISMVL)

Optimal Quantum Circuits of Three Qubits

Md. Mushfiqur Rahman, Gerhard W. Dueck

Published May 1, 2012• 5 citations
Publisher

Abstract

This paper shows how to find the optimal quantum circuits for all 3-qubit functions with an exhaustive search. A circuit for a given function is said to be optimal, if no realization with fewer gates exists. It is important to have the optimal results for all three-input functions, since they can serve as benchmarks when evaluation heuristic optimization algorithms. The optimal results generated, are compared with optimized quantum circuits obtained from post synthesis algorithms. It is observed that the published templates do not lead to optimal results. Experimental results show, that optimal circuits can seldom be obtained with template matching. On average the optimal size of a 3-qubit circuit is 10.0, where as template matching only achieves an average of 11.9 gates. It is shown that this is due to the fact that not all templates have been discovered. The paper concludes with some directions for further research.

DOI
10.1109/ismvl.2012.43

Related papers

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 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 algorithm to find quantum templates

Md. Mazder Rahman, Gerhard W. Dueck

Identity circuits can be used as templates to minimize reversible circuits. This paper describes an algorithm to find all quantum templates with 3 qubits. The algorithm is used to find all templates with up to 8 gates. The method first finds a quantum identities of 3 qubits, template matching is used to verify if the identity is a template. Experiments show the significance of templates the new to reduce the quantum costs of benchmark circuits.

IEEE Congress on Evolutionary Computation (CEC)•Jun 1, 2012•12 citations

An efficient method for improving the performance of quantum boolean circuit synthesis algorithms

Shiou-An Wang, Chin-Yung Lu

So far there are no synthesis algorithms that can find all the optimal quantum boolean circuits except an exhaustive algorithm. In this paper, we propose a method based on the divide and conquer approach which can significantly improve the performance of the existing synthesis algorithms to synthesize quantum boolean circuits. A quantum boolean circuit is first divided into two subcircuits. The subcircuit with fewer gates will input all possible combinations of m gates excluding those with the same function specification. The other subcircuit can be synthesized by using the existing algorithm. The two subcircuits are combined and then we can choose the most simplified quantum boolean circuit. According to the experimental results of all the 3-variable functions, we can see that the performance of the existing algorithms can be significantly improved by using our method. Therefore the synthesized quantum boolean circuits are much more simplified than previous results.

International Conference on Multimedia Technology (ICMT)•Jul 1, 2011•0 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

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
This paper shows how to find the optimal quantum circuits for all 3-qubit functions with an exhaustive search. A circuit for a given function is said to be optimal, if no realization with fewer gates exists. It is important to have the optimal results for all three-input functions, since they can serve as benchmarks when evaluation heuristic optimization algorithms. The optimal results generated, are compared with optimized quantum circuits obtained from post synthesis algorithms. It is observed that the published templates do not lead to optimal results. Experimental results show, that optimal circuits can seldom be obtained with template matching. On average the optimal size of a 3-qubit circuit is 10.0, where as template matching only achieves an average of 11.9 gates. It is shown that this is due to the fact that not all templates have been discovered. The paper concludes with some directions for further research.
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.
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.
So far there are no synthesis algorithms that can find all the optimal quantum boolean circuits except an exhaustive algorithm. In this paper, we propose a method based on the divide and conquer approach which can significantly improve the performance of the existing synthesis algorithms to synthesize quantum boolean circuits. A quantum boolean circuit is first divided into two subcircuits. The subcircuit with fewer gates will input all possible combinations of m gates excluding those with the same function specification. The other subcircuit can be synthesized by using the existing algorithm. The two subcircuits are combined and then we can choose the most simplified quantum boolean circuit. According to the experimental results of all the 3-variable functions, we can see that the performance of the existing algorithms can be significantly improved by using our method. Therefore the synthesized quantum boolean circuits are much more simplified than previous results.
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.
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.