research-article

QUEST: systematically approximating Quantum circuits for higher output fidelity

Authors:

Devesh TiwariAuthors Info & Claims

ASPLOS '22: Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems

Pages 514 - 528

https://doi.org/10.1145/3503222.3507739

Published: 22 February 2022 Publication History

Abstract

We present QUEST, a procedure to systematically generate approximations for quantum circuits to reduce their CNOT gate count. Our approach employs circuit partitioning for scalability with procedures to 1) reduce circuit length using approximate synthesis, 2) improve fidelity by running circuits that represent key samples in the approximation space, and 3) reason about approximation upper bound. Our evaluation results indicate that our approach of "dissimilar" approximations provides close fidelity to the original circuit. Overall, the results indicate that QUEST can reduce CNOT gate count by 30-80% on ideal systems and decrease the impact of noise on existing and near-future quantum systems.

References

[1]

https://github.com/BQSKit. BQSKit: Berkeley Quantum Synthesis Toolkit.

[2]

G Aleksandrowicz, T Alexander, P Barkoutsos, L Bello, Y Ben-Haim, and D Bucher. [n.d.]. Qiskit: An Open-source Framework for Quantum Computing.(2019).

[3]

Matthew Amy, Dmitri Maslov, Michele Mosca, and Martin Roetteler. 2013. A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 32, 6 (2013), 818–830.

Digital Library

[4]

Lindsay Bassman, Connor Powers, and Wibe A de Jong. 2021. ArQTiC: A Full-Stack Software Package for Simulating Materials on Quantum Computers. arXiv preprint arXiv:2106.04749.

[5]

Ethan Bernstein and Umesh Vazirani. 1997. Quantum Complexity Theory. SIAM Journal on computing, 26, 5 (1997), 1411–1473.

[6]

Sergey Bravyi, David Gosset, and Robert König. 2018. Quantum Advantage with Shallow Circuits. Science, 362, 6412 (2018), 308–311.

[7]

Heinz-Peter Breuer, Elsi-Mari Laine, and Jyrki Piilo. 2009. Measure for the Degree of Non-Markovian Behavior of Quantum Processes in Open Systems. Physical review letters, 103, 21 (2009), 210401.

[8]

Davide Castelvecchi. 2017. IBM’s Quantum Cloud Computer Goes Commercial. Nature News, 543, 7644 (2017), 159.

[9]

Steven A Cuccaro, Thomas G Draper, Samuel A Kutin, and David Petrie Moulton. 2004. A New Quantum Ripple-Carry Addition Circuit. arXiv preprint quant-ph/0410184.

[10]

Marc G Davis, Ethan Smith, Ana Tudor, Koushik Sen, Irfan Siddiqi, and Costin Iancu. 2020. Towards Optimal Topology Aware Quantum Circuit Synthesis. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). 223–234.

[11]

David Elieser Deutsch. 1989. Quantum Computational Networks. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 425, 1868 (1989), 73–90.

[12]

Edward Farhi and Aram W Harrow. 2016. Quantum Supremacy through the Quantum Approximate Optimization Algorithm. arXiv preprint arXiv:1602.07674.

[13]

Alexei Gilchrist, Nathan K Langford, and Michael A Nielsen. 2005. Distance Measures to Compare Real and Ideal Quantum Processes. Physical Review A, 71, 6 (2005), 062310.

[14]

Andrew Hancock, Austin Garcia, Jacob Shedenhelm, Jordan Cowen, and Calista Carey. 2019. Cirq: A Python Framework for Creating, Editing, and Invoking Quantum Circuits. URL https://github.com/quantumlib/Cirq.

[15]

Raban Iten, Roger Colbeck, Ivan Kukuljan, Jonathan Home, and Matthias Christandl. 2016. Quantum Circuits for Isometries. Physical Review A, 93, 3 (2016), 032318.

[16]

Raban Iten, Oliver Reardon-Smith, Emanuel Malvetti, Luca Mondada, Gabrielle Pauvert, Ethan Redmond, Ravjot Singh Kohli, and Roger Colbeck. 2019. Introduction to UniversalQCompiler. arXiv preprint arXiv:1904.01072.

[17]

Eric Jones, Travis Oliphant, and Pearu Peterson. 2016. SciPy: Open Source Scientific Tools for Python, 2001.

[18]

Sumeet Khatri, Ryan LaRose, Alexander Poremba, Lukasz Cincio, Andrew T Sornborger, and Patrick J Coles. 2019. Quantum-Assisted Quantum Compiling. Quantum, 3 (2019), 140.

[19]

Aleks Kissinger and Arianne Meijer-van de Griend. 2019. CNOT Circuit Extraction for Topologically-Constrained Quantum Memories. arXiv preprint arXiv:1904.00633.

[20]

Alexei Yu Kitaev, Alexander Shen, Mikhail N Vyalyi, and Mikhail N Vyalyi. 2002. Classical and Quantum Computation. American Mathematical Soc.

[21]

Vadym Kliuchnikov, Alex Bocharov, and Krysta M Svore. 2014. Asymptotically Optimal Topological Quantum Compiling. Physical review letters, 112, 14 (2014), 140504.

[22]

Ang Li and Sriram Krishnamoorthy. 2020. QASMBench: A Low-Level qasm Benchmark Suite for NISQ Evaluation and Simulation. arXiv preprint arXiv:2005.13018.

[23]

Gushu Li, Yufei Ding, and Yuan Xie. 2019. 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. 1001–1014.

Digital Library

[24]

Liam Madden and Andrea Simonetto. 2021. Best Approximate Quantum Compiling Problems. arXiv preprint arXiv:2106.05649.

[25]

Esteban A Martinez, Thomas Monz, Daniel Nigg, Philipp Schindler, and Rainer Blatt. 2016. Compiling Quantum Algorithms for Architectures with Multi-Qubit Gates. New Journal of Physics, 18, 6 (2016), 063029.

[26]

Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. 2016. The Theory of Variational Hybrid Quantum-Classical Algorithms. New Journal of Physics, 18, 2 (2016), 023023.

[27]

David C McKay, Thomas Alexander, Luciano Bello, Michael J Biercuk, Lev Bishop, Jiayin Chen, Jerry M Chow, Antonio D Córcoles, Daniel Egger, and Stefan Filipp. 2018. Qiskit Backend Specifications for OpenQASM and OpenPulse Experiments. arXiv preprint arXiv:1809.03452.

[28]

Prakash Murali, Jonathan M Baker, Ali Javadi-Abhari, Frederic T Chong, and Margaret Martonosi. 2019. 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. 1015–1029.

Digital Library

[29]

Prakash Murali, David C McKay, Margaret Martonosi, and Ali Javadi-Abhari. 2020. 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. 1001–1016.

Digital Library

[30]

Victor Namias. 1980. The Fractional order Fourier Transform and its Application to Quantum Mechanics. IMA Journal of Applied Mathematics, 25, 3 (1980), 241–265.

[31]

Beatrice Nash, Vlad Gheorghiu, and Michele Mosca. 2020. Quantum Circuit Optimizations for NISQ Architectures. Quantum Science and Technology, 5, 2 (2020), 025010.

[32]

Michael A Nielsen and Isaac L Chuang. 2010. Frontmatter. i–viii pages.

[33]

Tirthak Patel and Devesh Tiwari. 2020. Veritas: Accurately Estimating the Correct Output on Noisy Intermediate-Scale Quantum Computers. In 2020 SC20: International Conference for High Performance Computing, Networking, Storage and Analysis (SC). 188–203.

[34]

John Preskill. 2018. Quantum Computing in the NISQ Era and Beyond. Quantum, 2 (2018), 79.

[35]

Kenneth Regan, Amlan Chakrabarti, and Chaowen Guan. 2018. Algebraic and Logical Emulations of Quantum Circuits. In Transactions on Computational Science XXXI. Springer, 41–76.

[36]

Kemal H Sahin and Amy R Ciric. 1998. A Dual Temperature Simulated Annealing Approach for Solving Bilevel Programming Problems. Computers & chemical engineering, 23, 1 (1998), 11–25.

[37]

Vivek V Shende, Stephen S Bullock, and Igor L Markov. 2006. Synthesis of Quantum-Logic Circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25, 6 (2006), 1000–1010.

Digital Library

[38]

Yunong Shi, Nelson Leung, Pranav Gokhale, Zane Rossi, David I Schuster, Henry Hoffmann, and Frederic T Chong. 2019. Optimized Compilation of Aggregated Instructions for Realistic Quantum Computers. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. 1031–1044.

Digital Library

[39]

Ethan Smith, Marc G Davis, Jeffrey M Larson, Ed Younis, Costin Iancu, and Wim Lavrijsen. 2021. LEAP: Scaling Numerical Optimization Based Synthesis Using an Incremental Approach. arXiv preprint arXiv:2106.11246.

[40]

Kaitlin N Smith and Mitchell A Thornton. 2019. A Quantum Computational Compiler and Design Tool for Technology-Specific Targets. In Proceedings of the 46th International Symposium on Computer Architecture. 579–588.

Digital Library

[41]

Swamit S Tannu and Moinuddin Qureshi. 2019. Ensemble of Diverse Mappings: Improving Reliability of Quantum Computers by Orchestrating Dissimilar Mistakes. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture. 253–265.

Digital Library

[42]

Swamit S Tannu and Moinuddin K Qureshi. 2019. Not All Aubits are Created Equal: A Case for Variability-Aware Policies for NISQ-Era Quantum Computers. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. 987–999.

Digital Library

[43]

Robert R Tucci. 2005. An introduction to Cartan’s KAK decomposition for QC programmers. arXiv preprint quant-ph/0507171.

[44]

Bo-Ying Wang and Fuzhen Zhang. 1994. A Trace Inequality for Unitary Matrices. The American Mathematical Monthly, 101, 5 (1994), 453–455.

[45]

Robert Wille, Lukas Burgholzer, and Alwin Zulehner. 2019. Mapping Quantum Circuits to IBM QX Architectures Using the Minimal Number of SWAP and H Operations. In Proceedings of the 56th Annual Design Automation Conference 2019. 142.

Digital Library

[46]

Ed Younis, Koushik Sen, Katherine Yelick, and Costin Iancu. 2021. QFAST: Conflating Search and Numerical Optimization for Scalable Quantum Circuit Synthesis. arXiv preprint arXiv:2103.07093.

[47]

Chi Zhang, Ari B Hayes, Longfei Qiu, Yuwei Jin, Yanhao Chen, and Eddy Z Zhang. 2021. Time-optimal Qubit Mapping. In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems. 360–374.

Digital Library

[48]

Alwin Zulehner and Robert Wille. 2019. Compiling SU (4) Quantum Circuits to IBM QX Architectures. In Proceedings of the 24th Asia and South Pacific Design Automation Conference. 185–190.

Digital Library

Cited By

Sistla MLiu YFu X(2024)Towards High Performance QNNs via Distribution-Based CNOT Gate ReductionACM Transactions on Architecture and Code Optimization10.1145/369587221:4(1-22)Online publication date: 20-Nov-2024
https://dl.acm.org/doi/10.1145/3695872
Sharma RAchour S(2024)Compilation of Qubit Circuits to Optimized Qutrit CircuitsProceedings of the ACM on Programming Languages10.1145/36563888:PLDI(272-295)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656388
Anagolum SAlavisamani NDas PQureshi MShi YTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Elivagar: Efficient Quantum Circuit Search for ClassificationProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640354(336-353)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620665.3640354
Show More Cited By

Index Terms

QUEST: systematically approximating Quantum circuits for higher output fidelity
1. Computer systems organization
  1. Architectures
    1. Other architectures
      1. Quantum computing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Stochastic approximation

Recommendations

Geyser: a compilation framework for quantum computing with neutral atoms
ISCA '22: Proceedings of the 49th Annual International Symposium on Computer Architecture

Compared to widely-used superconducting qubits, neutral-atom quantum computing technology promises potentially better scalability and flexible arrangement of qubits to allow higher operation parallelism and more relaxed cooling requirements. The high ...
Scaling and Better Approximating Quantum Fourier Transform by Higher Radices

Quantum Fourier Transform (QFT) plays a principal role in the development of efficient quantum algorithms. Since the number of quantum bits that can currently be built is limited, while many quantum technologies are inherently three (or more) valued, we ...
GRAPHINE: Enhanced Neutral Atom Quantum Computing using Application-Specific Rydberg Atom Arrangement
SC '23: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis

Multiple technologies for realizing quantum computing are currently under development. Neutral atom quantum computing is one such promising technology; it offers advantages such as the ability to perform long-distance interactions and gates consisting of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPLOS '22: Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems

February 2022

1164 pages

ISBN:9781450392051

DOI:10.1145/3503222

General Chairs:
Babak Falsafi
EPFL, Switzerland
,
Michael Ferdman
Stony Brook University, USA
,
Program Chairs:
Shan Lu
University of Chicago, USA
,
Tom Wenisch
University of Michigan, USA / Google, USA

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 [email protected]

Sponsors

In-Cooperation

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 February 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Conference

ASPLOS '22

Sponsor:

ASPLOS '22: 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems

February 28 - March 4, 2022

Lausanne, Switzerland

Acceptance Rates

Overall Acceptance Rate 535 of 2,713 submissions, 20%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
942
Total Downloads

Downloads (Last 12 months)284
Downloads (Last 6 weeks)24

Reflects downloads up to 01 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sistla MLiu YFu X(2024)Towards High Performance QNNs via Distribution-Based CNOT Gate ReductionACM Transactions on Architecture and Code Optimization10.1145/369587221:4(1-22)Online publication date: 20-Nov-2024
https://dl.acm.org/doi/10.1145/3695872
Sharma RAchour S(2024)Compilation of Qubit Circuits to Optimized Qutrit CircuitsProceedings of the ACM on Programming Languages10.1145/36563888:PLDI(272-295)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656388
Anagolum SAlavisamani NDas PQureshi MShi YTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Elivagar: Efficient Quantum Circuit Search for ClassificationProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640354(336-353)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620665.3640354
Saravanan VSaeed S(2024)Noise Adaptive Quantum Circuit Mapping Using Reinforcement Learning and Graph Neural NetworkIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.334060843:5(1374-1386)Online publication date: May-2024
https://doi.org/10.1109/TCAD.2023.3340608
Clark JThapliyal H(2024)Peephole Optimization for Quantum Approximate Synthesis2024 25th International Symposium on Quality Electronic Design (ISQED)10.1109/ISQED60706.2024.10528701(1-8)Online publication date: 3-Apr-2024
https://doi.org/10.1109/ISQED60706.2024.10528701
Zhou JLiu YShi YJavadi-Abhari ALi G(2024)Bosehedral: Compiler Optimization for Bosonic Quantum Computing2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA59077.2024.00028(261-276)Online publication date: 29-Jun-2024
https://doi.org/10.1109/ISCA59077.2024.00028
Fu ZYang MChu CXu YHuang GChen F(2024)QuantumLeak: Stealing Quantum Neural Networks from Cloud-based NISQ Machines2024 International Joint Conference on Neural Networks (IJCNN)10.1109/IJCNN60899.2024.10651540(1-8)Online publication date: 30-Jun-2024
https://doi.org/10.1109/IJCNN60899.2024.10651540
Rasmussen CSaeed S(2024)Time-Aware Re-Synthesis for Secure Quantum Systems2024 IEEE International Symposium on Hardware Oriented Security and Trust (HOST)10.1109/HOST55342.2024.10545389(01-06)Online publication date: 6-May-2024
https://doi.org/10.1109/HOST55342.2024.10545389
Wang RBaba-Yara FChen FKim T(2024)JustQ: Automated Deployment of Fair and Accurate Quantum Neural NetworksProceedings of the 29th Asia and South Pacific Design Automation Conference10.1109/ASP-DAC58780.2024.10473829(121-126)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1109/ASP-DAC58780.2024.10473829
Xu AMolavi APick LTannu SAlbarghouthi A(2023)Synthesizing Quantum-Circuit OptimizersProceedings of the ACM on Programming Languages10.1145/35912547:PLDI(835-859)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591254
Show More Cited By

View Options

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents