research-article

Checking equivalence of quantum circuits and states

Authors:

George F. Viamontes,

Igor L. Markov,

John P. HayesAuthors Info & Claims

ICCAD '07: Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design

Pages 69 - 74

Published: 05 November 2007 Publication History

Abstract

Among the post-CMOS technologies currently under investigation, quantum computing (QC) holds a special place. QC offers not only extremely small size and low power, but also exponential speed-ups for important simulation and optimization problems. It also poses new CAD problems that are similar to, but more challenging, than the related problems in classical (non-quantum) CAD, such as determining if two states or circuits are functionally equivalent. While differences in classical states are easy to detect, quantum states, which are represented by complex-valued vectors, exhibit subtle differences leading to several notions of equivalence. This provides flexibility in optimizing quantum circuits, but leads to difficult new equivalence-checking issues for simulation and synthesis. We identify several different equivalence-checking problems and present algorithms for practical benchmarks, including quantum communication and search circuits, which are shown to be very fast and robust for hundreds of qubits.

References

[1]

M. H. S. Amin et al., "Superconducting quantum storage and processing," Digest ISSCC, pp. 296--299, Feb. 2004.

[2]

R. I. Bahar et al., "Algebraic decision diagrams and their applications," Journal of Formal Methods in System Design, 10 (2/3), 1997.

Digital Library

[3]

A. Barenco et al., "Elementary gates for quantum computation," Phys. Rev. A, 52, 3457--3467, 1995.

[4]

C. H. Bennett and G. Brassard, "Quantum cryptography: public key distribution and coin tossing", In Proc. of IEEE Intl. Conf. on Computers, Systems, and Signal Processing, pp. 175--179, 1984.

[5]

C. H. Bennett, "Quantum cryptography using any two nonorthogonal states", Phys. Rev. Lett. 68, 3121, 1992.

[6]

G. P. Berman, G. V. López, and V. I. Tsifrinovich, "Teleportation in a nuclear spin quantum computer," Phys. Rev. A 66, 042312, 2002.

[7]

R. Bryant, "Graph-based algorithms for Boolean function manipulation." IEEE Trans. on Computers, C35, pp. 677--691, 1986.

Digital Library

[8]

S. A. Cuccaro, T. G. Draper, S. A. Kutin, and D. P. Moulton, "A new quantum ripple-carry addition circuit," quant-ph/0410184, 2004.

[9]

D. Gottesman, "The Heisenberg representation of quantum computers," Plenary speech at the 1998 International Conference on Group Theoretic Methods in Physics, quant-ph/9807006, 1998.

[10]

L. Grover, "Quantum mechanics helps in searching for a needle in a haystack," Phys. Rev. Lett. 79, 325, 1997.

[11]

A. J. G. Hey, ed., Feynman and Computation: Exploring the Limits of Computers, Perseus Books, 1999.

Digital Library

[12]

D. Maslov, S. M. Falconer, and M. Mosca, "Quantum Circuit Placement: Optimizing Qubit-to-qubit Interactions through Mapping Quantum Circuits into a Physical Experiment," Proc. DAC, pp. 962--965, June 2007.

Digital Library

[13]

M. A. Nielsen, I. L. Chuang, Quantum Computation and Quantum Information, Cambridge Univ. Press, 2000.

Digital Library

[14]

A. K. Prasad, V. V. Shende, K. N. Patel, I. L. Markov, and J. P. Hayes, "Algorithms and data structures for simplifying reversible circuits", to appear in ACM J. of Emerging Technologies in Computing, 2007.

Digital Library

[15]

V. V. Shende, S. S. Bullock, and I. L. Markov, "Synthesis of quantum logic circuits," IEEE Trans. on CAD 25, pp. 1000--1010, 2006.

Digital Library

[16]

V. V. Shende and I. L. Markov, "Quantum circuits for incompletely specified two-qubit operators," Quantum Information and Computation 5 (1), pp. 49--57, 2005.

Digital Library

[17]

P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer," SIAM J. of Computing 26, p. 1484, 1997.

Digital Library

[18]

G. Song and A. Klappenecker, "Optimal realizations of simplified Toffoli gates," Quantum Information and Computation 4, pp. 361--372, 2004.

Digital Library

[19]

R. T. Stanion, D. Bhattacharya, and C. Sechen, "An efficient method for generating exhaustive test sets," IEEE Trans. on CAD 14, pp. 1516--1525, 1995.

Digital Library

[20]

R. Van Meter and K. M. Itoh, "Fast quantum modular exponentiation," Phys. Rev. A 71, 052320, 2005.

[21]

G. F. Viamontes, I. L. Markov, and J. P. Hayes, "Graph-based simulation of quantum computation in the density matrix representation," Quantum Information and Computation 5 (2), pp. 113--130, 2005.

Digital Library

[22]

G. F. Viamontes, I. L. Markov, and J. P. Hayes, "Improving gate-level simulation of quantum circuits," Quantum Information Processing 2, pp. 347--380, 2003.

Digital Library

[23]

G. Vidal, "Efficient classical simulation of slightly entangled quantum computations," Phys. Rev. Lett. 91, 147902, 2003.

[24]

J. Yepez, "A quantum lattice-gas model for computational fluid dynamics," Phys. Rev. E 63, 046702, 2001.

Cited By

Hong XFeng YLi SYing MMitra TYoung EXiong J(2022)Equivalence Checking of Dynamic Quantum CircuitsProceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design10.1145/3508352.3549479(1-8)Online publication date: 30-Oct-2022
https://dl.acm.org/doi/10.1145/3508352.3549479
Liu JBello LZhou HLee J(2021)Relaxed peephole optimizationProceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO51591.2021.9370310(301-314)Online publication date: 27-Feb-2021
https://dl.acm.org/doi/10.1109/CGO51591.2021.9370310
Burgholzer LWille RLi Z(2020)The power of simulation for equivalence checking in quantum computingProceedings of the 57th ACM/EDAC/IEEE Design Automation Conference10.5555/3437539.3437748(1-6)Online publication date: 20-Jul-2020
https://dl.acm.org/doi/10.5555/3437539.3437748
Show More Cited By

Recommendations

Equivalence Checking of Dynamic Quantum Circuits
ICCAD '22: Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design

Despite the rapid development of quantum computing these years, state-of-the-art quantum devices still contain only a limited number of qubits. One possible way to execute more realistic algorithms in near-term quantum devices is to employ dynamic ...
Fast Equivalence Checking of Quantum Circuits of Clifford Gates
Automated Technology for Verification and Analysis
Abstract
Checking whether two quantum circuits are equivalent is important for the design and optimization of quantum-computer applications with real-world devices. We consider quantum circuits consisting of Clifford gates, a practically-relevant subset of ...
Commuting quantum circuits: efficient classical simulations versus hardness results

The study of quantum circuits composed of commuting gates is particularly useful to understand the delicate boundary between quantum and classical computation. Indeed, while being a restricted class, commuting circuits exhibit genuine quantum effects ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '07: Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design

November 2007

933 pages

ISBN:1424413826

General Chair:
Georges Gielen
ESAT-MICAS, Katholieke Univ. Leuven, Leuven, Belgium

Sponsors

CEDA: Council on Electronic Design Automation
SIGDA: ACM Special Interest Group on Design Automation
IEEE CASS/CANDE
IEEE-CS\DATC: IEEE Computer Society

Publisher

IEEE Press

Publication History

Published: 05 November 2007

Check for updates

Qualifiers

Research-article

Conference

ICCAD07

Sponsor:

CEDA
SIGDA
IEEE-CS\DATC

ICCAD07: The International Conference on Computer-Aided Design 2007

November 5 - 8, 2007

California, San Jose

Acceptance Rates

ICCAD '07 Paper Acceptance Rate 139 of 510 submissions, 27%;

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
200
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hong XFeng YLi SYing MMitra TYoung EXiong J(2022)Equivalence Checking of Dynamic Quantum CircuitsProceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design10.1145/3508352.3549479(1-8)Online publication date: 30-Oct-2022
https://dl.acm.org/doi/10.1145/3508352.3549479
Liu JBello LZhou HLee J(2021)Relaxed peephole optimizationProceedings of the 2021 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO51591.2021.9370310(301-314)Online publication date: 27-Feb-2021
https://dl.acm.org/doi/10.1109/CGO51591.2021.9370310
Burgholzer LWille RLi Z(2020)The power of simulation for equivalence checking in quantum computingProceedings of the 57th ACM/EDAC/IEEE Design Automation Conference10.5555/3437539.3437748(1-6)Online publication date: 20-Jul-2020
https://dl.acm.org/doi/10.5555/3437539.3437748
Zulehner AHillmich SMarkov IWille RCheng KYang H(2020)Approximation of Quantum States Using Decision DiagramsProceedings of the 25th Asia and South Pacific Design Automation Conference10.1109/ASP-DAC47756.2020.9045454(121-126)Online publication date: 17-Jan-2020
https://dl.acm.org/doi/10.1109/ASP-DAC47756.2020.9045454
Burgholzer LWille RCheng KYang H(2020)Improved DD-Based Equivalence Checking of Quantum CircuitsProceedings of the 25th Asia and South Pacific Design Automation Conference10.1109/ASP-DAC47756.2020.9045153(127-132)Online publication date: 17-Jan-2020
https://dl.acm.org/doi/10.1109/ASP-DAC47756.2020.9045153
Roetteler MSvore KWecker DWiebe N(2017)Design automation for quantum architecturesProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130689(1312-1317)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130689
Saeedi MMarkov I(2013)Synthesis and optimization of reversible circuits—a surveyACM Computing Surveys10.1145/2431211.243122045:2(1-34)Online publication date: 12-Mar-2013
https://dl.acm.org/doi/10.1145/2431211.2431220
Drechsler RWille R(2012)Reversible circuitsProceedings of the 16th international conference on Progress in VLSI Design and Test10.1007/978-3-642-31494-0_53(383-392)Online publication date: 1-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31494-0_53
Soeken MFrehse SWille RDrechsler R(2011)RevKitProceedings of the Third international conference on Reversible Computation10.1007/978-3-642-29517-1_6(64-76)Online publication date: 4-Jul-2011
https://dl.acm.org/doi/10.1007/978-3-642-29517-1_6
Yamashita SMarkov IDas SBahar INiemier M(2010)Fast equivalence-checking for quantum circuitsProceedings of the 2010 IEEE/ACM International Symposium on Nanoscale Architectures10.5555/1835957.1835965(23-28)Online publication date: 17-Jun-2010
https://dl.acm.org/doi/10.5555/1835957.1835965
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.

Figures

Tables

Media

View Table of Conten