research-article

Exact and Practical Pattern Matching for Quantum Circuit Optimization

Authors:

Stefan WoernerAuthors Info & Claims

ACM Transactions on Quantum Computing, Volume 3, Issue 1

Article No.: 4, Pages 1 - 41

https://doi.org/10.1145/3498325

Published: 22 January 2022 Publication History

Abstract

Quantum computations are typically performed as a sequence of basic operations, called quantum gates. Different gate sequences, called quantum circuits, can implement the same overall quantum computation. Since every additional quantum gate takes time and introduces noise into the system, it is important to find the smallest possible quantum circuit that implements a given computation, especially for near-term quantum devices that can execute only a limited number of quantum gates before noise renders the computation useless. An important building block for many quantum circuit optimization techniques is pattern matching: given a large and small quantum circuit, we would like to find all maximal matches of the small circuit, called a pattern, in the large circuit, considering pairwise commutation of quantum gates. In this work, we present the first classical algorithm for pattern matching that provably finds all maximal matches and is efficient enough to be practical for circuit sizes typical for near-term devices. We demonstrate numerically that combining our algorithm with known pattern-matching-based circuit optimization techniques reduces the gate count of a random quantum circuit by ∼ 30% and can further improve practically relevant quantum circuits that were already optimized with state-of-the-art techniques.

References

[1]

N. Abdessaied, M. Soeken, R. Wille, and R. Drechsler. 2013. Exact template matching using Boolean satisfiability. In IEEE 43rd International Symposium on Multiple-Valued Logic, Toyama, Japan. 328–333.https://doi.org/10.1109/ISMVL.2013.26

Digital Library

[2]

Héctor Abraham et al. 2019. Qiskit: An Open-source Framework for Quantum Computing. https://doi.org/10.5281/zenodo.2562110

[3]

M. Boehner. 1988. LOGEX-An automatic logic extractor from transistor to gate level for CMOS technology. In 25th ACM/IEEE, Design Automation Conference, Washington, DC, United States. 517–522. https://doi.org/10.1109/DAC.1988.14809

Digital Library

[4]

Stephen A. Cook. 1971. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing (Shaker Heights, OH) (STOC’71). ACM, New York, NY, 151–158. https://doi.org/10.1145/800157.805047

Digital Library

[5]

Ross Duncan, Aleks Kissinger, Simon Perdrix, and John van de Wetering. 2019. Graph-theoretic simplification of quantum circuits with the ZX-calculus. ArXiv 1902.03178 (2019).

[6]

Lov K. Grover. 1996. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (Philadelphia, PA) (STOC’96). ACM, New York, NY, 212–219. https://doi.org/10.1145/237814.237866

Digital Library

[7]

Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. 2009. Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103 (Oct 2009), 150502. Issue 15. https://doi.org/10.1103/PhysRevLett.103.150502

[8]

Raban Iten, Roger Colbeck, Ivan Kukuljan, Jonathan Home, and Matthias Christandl. 2016. Quantum circuits for isometries. Physical Review A 93, 3 (March 2016), 032318. https://doi.org/10.1103/PhysRevA.93.032318

[9]

Raban Iten, Oliver Reardon-Smith, Luca Mondada, Ethan Redmond, Ravjot Singh Kohli, and Roger Colbeck. 2019. Introduction to UniversalQCompiler. ArXiv:1904.01072 (April 2019). http://arxiv.org/abs/1904.01072.

[10]

K. Iwama, Y. Kambayashi, and S. Yamashita. 2002. Transformation rules for designing CNOT-based quantum circuits. In Proceedings of the 2002 Design Automation Conference, New Orleans, LA, USA. 419–424. https://doi.org/10.1109/DAC.2002.1012662

Digital Library

[11]

Dominik Janzing, Pawel Wocjan, and Thomas Beth. 2003. Identity check is QMA-complete. ArXiv:0305050 (2003).

[12]

Vadym Kliuchnikov and Dmitri Maslov. 2013. Optimization of Clifford circuits. Physical Review A 88, 5 (Nov. 2013), 052307. https://doi.org/10.1103/PhysRevA.88.052307

[13]

Robin Kothari. [n.d.]. Private communication.

[14]

F. Luellau, T. Hoepken, and E. Barke. 1984. A technology independent block extraction algorithm. In 21st Design Automation Conference Proceedings, Albuquerque, NM, USA. 610–615. https://doi.org/10.1109/DAC.1984.1585862

Digital Library

[15]

D. Maslov, G. W. Dueck, and D. M. Miller. 2003. Simplification of Toffoli networks via templates. In 16th Symposium on Integrated Circuits and Systems Design, Sao Paulo, Brazil. 53–58. https://doi.org/10.1109/SBCCI.2003.1232806

Digital Library

[16]

D. Maslov, G. W. Dueck, and D. M. Miller. 2005. Synthesis of Fredkin-Toffoli reversible networks. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 13, 6 (June 2005), 765–769. https://doi.org/10.1109/TVLSI.2005.844284

Digital Library

[17]

D. Maslov, G. W. Dueck, and D. M. Miller. 2007. Techniques for the synthesis of reversible Toffoli networks. ACM Transactions on Design Automation of Electronic Systems 12, 4 (Sep 2007), 42. https://doi.org/10.1145/1278349.1278355

Digital Library

[18]

D. Maslov, G. W. Dueck, D. M. Miller, and C. Negrevergne. 2008. Quantum circuit simplification and level compaction. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27, 3 (March 2008), 436–444. https://doi.org/10.1109/TCAD.2007.911334

Digital Library

[19]

D. M. Miller, D. Maslov, and G. W. Dueck. 2003. A transformation based algorithm for reversible logic synthesis. In Proceedings of the 2003 Design Automation Conference, Anaheim, CA, USA. 318–323. https://doi.org/10.1145/775832.775915

Digital Library

[20]

Luca Mondada. 2018. UniversalQCompiler: a quantum compiler from arbitrary isometries to elementary gates. Semester Thesis at ETH Zurich.

[21]

Yunseong Nam, Neil J. Ross, Yuan Su, Andrew M. Childs, and Dmitri Maslov. 2018. Automated optimization of large quantum circuits with continuous parameters. npj Quantum Information 4, 1 (May 2018). https://doi.org/10.1038/s41534-018-0072-4

[22]

Michael A. Nielsen and Isaac L. Chuang. 2000. Quantum Computation and Quantum Information. Cambridge University Press.

Digital Library

[23]

M. Ohlrich, C. Ebeling, E. Ginting, and L. Sather. 1993. SubGemini: Identifying subcircuits using a fast subgraph isomorphism algorithm. In 30th ACM/IEEE Design Automation Conference, Dallas, Texas, USA. 31–37. https://doi.org/10.1145/157485.164556

Digital Library

[24]

Aditya K. Prasad, Vivek V. Shende, Igor L. Markov, John P. Hayes, and Ketan N. Patel. 2006. Data structures and algorithms for simplifying reversible circuits. J. Emerg. Technol. Comput. Syst. 2, 4 (Oct. 2006), 277–293. https://doi.org/10.1145/1216396.1216399

Digital Library

[25]

Aditya K. Prasad, Vivek V. Shende, Igor L. Markov, John P. Hayes, and Ketan N. Patel. 2006. Data structures and algorithms for simplifying reversible circuits. ACM Journal on Emerging Technologies in Computing Systems 2, 4 (Oct. 2006), 277–293. https://doi.org/10.1145/1216396.1216399

Digital Library

[26]

John Preskill. 2018. Quantum computing in the NISQ era and beyond. Quantum 2 (2018), 79.

[27]

Md. Mazder Rahman, Gerhard W. Dueck, and Joseph D. Horton. 2014. An algorithm for quantum template matching. J. Emerg. Technol. Comput. Syst. 11, 3, Article 31 (Dec. 2014), 20 pages. https://doi.org/10.1145/2629537

Digital Library

[28]

Vivek V. Shende, Stephen S. Bullock, and Igor L. Markov. 2004. Recognizing small-circuit structure in two-qubit operators. Physical Review A 70, 1 (July 2004), 012310. https://doi.org/10.1103/PhysRevA.70.012310

[29]

Peter W. Shor. 1997. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 5 (Oct. 1997), 1484–1509. https://doi.org/10.1137/S0097539795293172

Digital Library

[30]

J. R. Ullmann. 1976. An algorithm for subgraph isomorphism. J. ACM 23, 1 (Jan. 1976), 31–42. https://doi.org/10.1145/321921.321925

Digital Library

[31]

T. Watanabe, Makoto Endo, and N. Miyahara. 1983. A new automatic logic interconnection verification system for VLSI design. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 2, 2 (April 1983), 70–82. https://doi.org/10.1109/TCAD.1983.1270023

Digital Library

Cited By

Peres FWagner RGalvão E(2024)Non-stabilizerness and entanglement from cat-state injectionNew Journal of Physics10.1088/1367-2630/ad1b8026:1(013051)Online publication date: 29-Jan-2024
https://doi.org/10.1088/1367-2630/ad1b80
Huang JEmeakaroha V(2024)Performing Distributed Quantum Calculations in a Multi-cloud Architecture Secured by the Quantum Key Distribution ProtocolSN Computer Science10.1007/s42979-024-02761-05:4Online publication date: 8-Apr-2024
https://dl.acm.org/doi/10.1007/s42979-024-02761-0
Prajapati MKillana K(2024)An Efficient Quantum Circuit Design: Properties and Optimization TechniquesIntelligent Informatics10.1007/978-981-97-2147-4_28(407-419)Online publication date: 18-Oct-2024
https://doi.org/10.1007/978-981-97-2147-4_28
Show More Cited By

Index Terms

Exact and Practical Pattern Matching for Quantum Circuit Optimization
1. Computer systems organization
  1. Architectures
    1. Other architectures
      1. Quantum computing
2. Hardware
  1. Electronic design automation
    1. Logic synthesis
      1. Circuit optimization

Recommendations

Universal quantum circuit for N-qubit quantum gate: a programmable quantum gate

Quantum computation has attracted much attention, among other things, due to its potentialities to solve classical NP problems in polynomial time. For this reason, there has been a growing interest to build a quantum computer. One of the basic steps is ...
Construction of quantum gates for concatenated Greenberger---Horne---Zeilinger-type logic qubit

Concatenated Greenberger---Horne---Zeilinger (C-GHZ) state is a kind of logic qubit which is robust in noisy environment. In this paper, we encode the C-GHZ state as the logic qubit and design two kinds of quantum gates for such logic qubit. The first ...
Template-based mapping of reversible circuits to IBM quantum computers
Abstract
In order to make the most of the increasing computational power of recently developed quantum computers, it is crucial to perform an efficient mapping of a given quantum circuit that realizes the desired quantum algorithm to the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Quantum Computing

ACM Transactions on Quantum Computing Volume 3, Issue 1

March 2022

112 pages

EISSN:2643-6817

DOI:10.1145/3505212

Editors:
Travis S. Humble
Oak Ridge National Laboratory, USA
,
Mingsheng Ying
University of Technology Sydney, Australia

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 January 2022

Accepted: 01 November 2021

Revised: 01 October 2021

Received: 01 December 2020

Published in TQC Volume 3, Issue 1

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Funding Sources

Swiss National Science Foundation
National Centre of Competence in Research Quantum Science and Technology (QSIT)
Quantum Center of ETH Zurich

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
1,071
Total Downloads

Downloads (Last 12 months)279
Downloads (Last 6 weeks)37

Reflects downloads up to 01 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Peres FWagner RGalvão E(2024)Non-stabilizerness and entanglement from cat-state injectionNew Journal of Physics10.1088/1367-2630/ad1b8026:1(013051)Online publication date: 29-Jan-2024
https://doi.org/10.1088/1367-2630/ad1b80
Huang JEmeakaroha V(2024)Performing Distributed Quantum Calculations in a Multi-cloud Architecture Secured by the Quantum Key Distribution ProtocolSN Computer Science10.1007/s42979-024-02761-05:4Online publication date: 8-Apr-2024
https://dl.acm.org/doi/10.1007/s42979-024-02761-0
Prajapati MKillana K(2024)An Efficient Quantum Circuit Design: Properties and Optimization TechniquesIntelligent Informatics10.1007/978-981-97-2147-4_28(407-419)Online publication date: 18-Oct-2024
https://doi.org/10.1007/978-981-97-2147-4_28
Puram VKaruppasamy KThomas J(2024)Optimizing Quantum Circuits Using Algebraic ExpressionsComputational Science – ICCS 202410.1007/978-3-031-63778-0_19(268-276)Online publication date: 2-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-63778-0_19
Gao XGuan ZFeng SJiang Y(2023)Quantum Circuit Template Matching Optimization Method for Constrained ConnectivityAxioms10.3390/axioms1207068712:7(687)Online publication date: 14-Jul-2023
https://doi.org/10.3390/axioms12070687
Brandhofer SKim JNiu SBronn N(2023)SAT-Based Quantum Circuit Adaptation2023 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE56975.2023.10137140(1-6)Online publication date: Apr-2023
https://doi.org/10.23919/DATE56975.2023.10137140
gao xguan zfeng sliu rqian ycheng xzhu p(2023)Template matching-based connected constraint mapping optimization method for quantum circuitsThird International Conference on Mechanical, Electronics, and Electrical and Automation Control (METMS 2023)10.1117/12.2679552(71)Online publication date: 18-Jul-2023
https://doi.org/10.1117/12.2679552
Wen ZLiu YTan SChen JZhu MHan DYin JXu MChen W(2023)Quantivine: A Visualization Approach for Large-Scale Quantum Circuit Representation and AnalysisIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2023.332714830:1(573-583)Online publication date: 25-Oct-2023
https://dl.acm.org/doi/10.1109/TVCG.2023.3327148
Liu JYounis EWeiden MHovland PKubiatowicz JIancu C(2023)Tackling the Qubit Mapping Problem with Permutation-Aware Synthesis2023 IEEE International Conference on Quantum Computing and Engineering (QCE)10.1109/QCE57702.2023.00090(745-756)Online publication date: 17-Sep-2023
https://doi.org/10.1109/QCE57702.2023.00090
Huang T(2023)qTask: Task-parallel Quantum Circuit Simulation with Incrementality2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS54959.2023.00080(746-756)Online publication date: May-2023
https://doi.org/10.1109/IPDPS54959.2023.00080
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents