research-article
Authors: Mingyu Chen, Yu Zhang, Yongshang Li, Zhen Wang, Jun Li, Xiangyang Li
ICCAD '22: Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design
Article No.: 55, Pages 1 - 8
Published: 22 December 2022 Publication History
Metrics
Total Citations1Total Downloads138Last 12 Months77
Last 6 weeks5
New Citation Alert added!
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Manage my Alerts
New Citation Alert!
Please log in to your account
Get Access
- Get Access
- References
- Media
- Tables
- Share
Abstract
Due to multiple limitations of quantum computers in the NISQ era, quantum compilation efforts are required to efficiently execute quantum algorithms on NISQ devices Program rewriting based on pattern matching can improve the generalization ability of compiler optimization. However, it has rarely been explored for quantum circuit optimization, further considering physical features of target devices.
In this paper, we propose a pattern-matching based quantum circuit optimization framework QCIR with a novel pattern description format, enabling the user-configured cost model and two categories of patterns, i.e., generic patterns and folding patterns. To get better compilation latency, we propose a DAG representation of quantum circuit called QCir-DAG, and QVF algorithm for subcircuit matching. We implement continuous single-qubit optimization pass constructed by QCIR, achieving 10% and 20% optimization rate for benchmarks from Qiskit and ScaffCC, respectively. The practicality of QCIR is demonstrated by execution time and experimental results on the quantum simulator and quantum devices.
References
[1]
Originqc. https://www.originqc.com.cn/.
[2]
Ibm q. https://www.research.ibm.com/ibm-q/, cited in Jan. 2019.
[3]
Nabila Abdessaied, Matthias Soeken, Robert Wille, and Rolf Drechsler. Exact template matching using boolean satisfiability. In 2013 IEEE 43rd International Symposium on Multiple-Valued Logic, pages 328--333. IEEE, 2013.
Digital Library
[4]
Ali Javadi Abhari, Shruti Patil, Daniel Kudrow, Jeff Heckey, Alexey Lvov, Frederic T. Chong, and Margaret Martonosi. ScaffCC: A framework for compilation and analysis of quantum computing programs. In 11th CF, pages 1:1--1:10, New York, NY, USA, 2014. ACM.
[5]
JavadiAbhari Ali, Nation Paul, and Gambetta Jay. Qiskit - write once, target multiple architectures. IBM Research Blog, https://www.ibm.com/blogs/research/2019/11/qiskit-for-multiple-architectures/, November 2019.
[6]
Frank Arute, Kunal Arya, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574:505--510, 2019.
[7]
Amazon Braket. Azure Quantum - Quantum Service: Microsoft Azure. https://azure.microsoft.com/en-us/services/quantum/, Accessed May. 2022.
[8]
H-J Briegel, Tommaso Calarco, Dieter Jaksch, Juan Ignacio Cirac, and Peter Zoller. Quantum computing with neutral atoms. Journal of modern optics, 47(2--3):415--451, 2000.
[9]
A. Chi-Chih Yao. Quantum circuit complexity. In Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pages 352--361, 1993.
[10]
Luigi P Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. A (sub) graph isomorphism algorithm for matching large graphs. IEEE transactions on pattern analysis and machine intelligence, 26(10):1367--1372, 2004.
[11]
Andrew W. Cross, Lev S. Bishop, John A. Smolin, and Jay M. Gambetta. Open quantum assembly language. arXiv:1707.03429, 2017.
[12]
S. Debnath, N. M. Linke, C. Figgatt, K. A. Landsman, K. Wright, and C. Monroe. Demonstration of a small programmable quantum computer with atomic qubits. Nature, 536:63--66, 2016.
[13]
Haowei Deng, Yu Zhang, and Quanxi Li. Codar: a contextual duration-aware qubit mapping for various NISQ devices. In 2020 57th ACM/IEEE Design Automation Conference (DAC), pages 1--6. IEEE, 2020.
[14]
Simon J. Devitt. Performing quantum computing experiments in the cloud. 94, 2016.
[15]
IBM. QISKit. https://qiskit.org/, visited in Jan 2019.
[16]
Raban Iten, Romain Moyard, Tony Metger, David Sutter, and Stefan Woerner. Exact and practical pattern matching for quantum circuit optimization. ACM Transactions on Quantum Computing, 3(1), jan 2022.
[17]
Kazuo Iwama, Yahiko Kambayashi, and Shigeru Yamash*ta. Transformation rules for designing cnot-based quantum circuits. In Proceedings of the 39th annual Design Automation Conference, pages 419--424, 2002.
Digital Library
[18]
Sangil Kwon, Akiyoshi Tomonaga, Gopika Lakshmi Bhai, Simon J Devitt, and Jaw-Shen Tsai. Gate-based superconducting quantum computing. Journal of Applied Physics, 129(4):041102, 2021.
[19]
Gushu Li, Yufei Ding, and Yuan Xie. Tackling the qubit mapping problem for NISQ-era quantum devices. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 1001--1014, 2019.
Digital Library
[20]
Chris Lomont. Quantum circuit identities. arXiv preprint quant-ph/0307111, 2003.
[21]
Dmitri Maslov. Advantages of using relative-phase toffoli gates with an application to multiple control toffoli optimization. Physical Review A, 93(2):022311, 2016.
[22]
Giulia Meuli, Mathias Soeken, and Giovanni De Micheli. Xor-and-inverter graphs for quantum compilation. npj Quantum Information, 8(1):1--11, 2022.
[23]
D Michael Miller, Dmitri Maslov, and Gerhard W Dueck. A transformation based algorithm for reversible logic synthesis. In Proceedings 2003. design automation conference (ieee cat. no. 03ch37451), pages 318--323. IEEE, 2003.
Digital Library
[24]
Prakash Murali, Jonathan M Baker, Ali Javadi-Abhari, Frederic T Chong, and Margaret Martonosi. Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 1015--1029, 2019.
Digital Library
[25]
Prakash Murali, Norbert Matthias Linke, Margaret Martonosi, Ali Javadi Abhari, Nhung Hong Nguyen, and Cinthia Huerta Alderete. Full-stack, real-system quantum computer studies: architectural comparisons and design insights. In Proceedings of the 46th International Symposium on Computer Architecture, pages 527--540, 2019.
Digital Library
[26]
Prakash Murali, David C McKay, Margaret Martonosi, and Ali Javadi-Abhari. Software mitigation of crosstalk on noisy intermediate-scale quantum computers. In Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 1001--1016, 2020.
Digital Library
[27]
Yun Seong Nam, Neil J Ross, Yuan Su, Andrew M Childs, and Dmitri Maslov. Automated optimization of large quantum circuits with continuous parameters. npj Quantum Information, 4(1):23, 2018.
[28]
T. Nguyen and A. Mccaskey. Enabling pulse-level programming, compilation, and execution in XACC. IEEE Transactions on Computers, pages 1:1--14, 2021.
[29]
Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O'brien. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5:4213, 2014.
[30]
Md Mazder Rahman, Gerhard W Dueck, and Joseph D Horton. An algorithm for quantum template matching. ACM Journal on Emerging Technologies in Computing Systems (JETC), 11(3):1--20, 2014.
[31]
Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. t|ket>: A retargetable compiler for NISQ devices. Quantum Science and Technology, 6(1):014003, 2021.
[32]
IBM Q team. IBM Q Eagle Quantum Processor. https://research.ibm.com/blog/127-qubit-quantum-processor-eagle, 2021.
[33]
James D Whitfield, Jacob Biamonte, and Alán Aspuru-Guzik. Simulation of electronic structure hamiltonians using quantum computers. Molecular Physics, 109(5):735--750, 2011.
Cited By
View all
- 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
Index Terms
QCIR: Pattern Matching Based Universal Quantum Circuit Rewriting Framework
Applied computing
Physical sciences and engineering
Hardware
Electronic design automation
Software and its engineering
Software notations and tools
Index terms have been assigned to the content through auto-classification.
Recommendations
- Quantum Circuit Simplification and Level Compaction
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. ...
Read More
- Contextuality Supplies the Magic for Quantum Computation
ISMVL '15: Proceedings of the 2015 IEEE 45th International Symposium on Multiple-Valued Logic
We know that quantum mechanics enables the performance of computational and cryptographic tasks that are impossible (or impracticable) using only classical physics. It seems natural to examine manifestations of inherently quantum behaviour as potential ...
Read More
- Near-optimal circuit mapping with reduced search paths on IBM quantum architectures
Abstract
Due to technological constraints in the quantum devices, two-qubit gates can be executed only if their qubits are physically connected (neighbours). If all the qubits of the two-qubit gates in a circuit cannot be kept adjacent to each ...
Read More
Comments
Information & Contributors
Information
Published In
ICCAD '22: Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design
October 2022
1467 pages
ISBN:9781450392174
DOI:10.1145/3508352
- Conference Chair:
- Tulika Mitra
National University of Singapore
, - Program Chairs:
- Evangeline Young
The Chinese University of Hong Kong
, - Jinjun Xiong
University at Buffalo (UB)
Copyright © 2022 ACM.
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 [emailprotected]
Sponsors
- SIGDA: ACM Special Interest Group on Design Automation
In-Cooperation
- IEEE-EDS: Electronic Devices Society
- IEEE CAS
- IEEE CEDA
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 22 December 2022
Permissions
Request permissions for this article.
Check for updates
Author Tags
- circuit optimization
- pattern matching
- quantum computing
Qualifiers
- Research-article
Funding Sources
- Fundamental Research Funds for the Central Universities
- Innovation Program for Quantum Science and Technology
Conference
ICCAD '22
Sponsor:
- SIGDA
ICCAD '22: IEEE/ACM International Conference on Computer-Aided Design
October 30 - November 3, 2022
California, San Diego
Acceptance Rates
Overall Acceptance Rate 457 of 1,762 submissions, 26%
Contributors
Other Metrics
View Article Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations
1
Total Citations
138
Total Downloads
- Downloads (Last 12 months)77
- Downloads (Last 6 weeks)5
Reflects downloads up to 04 Aug 2024
Other Metrics
View Author Metrics
Citations
Cited By
View all
- 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
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.
Sign in
Full Access
Get this Publication
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderMedia
Figures
Other
Tables
