Article

Quantum circuit placement: optimizing qubit-to-qubit interactions through mapping quantum circuits into a physical experiment

Authors:

Sean M. Falconer,

Michele MoscaAuthors Info & Claims

DAC '07: Proceedings of the 44th annual Design Automation Conference

Pages 962 - 965

https://doi.org/10.1145/1278480.1278717

Published: 04 June 2007 Publication History

Abstract

We study the problem of the practical realization of an abstract quantum circuit when executed on quantum hardware. By practical, we mean adapting the circuit to particulars of the physical environment which restricts/complicates the establishment of certain direct interactions between qubits. This is a quantum version of the classical circuit placement problem. We study the theoretical aspects of the problem and also present empirical results that match the best known solutions that have been developed by experimentalists. Finally, we discuss the efficiency of the approach and scalability of its implementation with regards to the future development of quantum hardware.

References

[1]

D. Copsey et al. IEEE Journal of Selected Topics in Quantum Electronics, 9(6):1552--1569, 2003.

[2]

L. P. Cordella et al. 10th ICIAP, vol. 2, pages 1172--1178, 1999. The VFLib graph matching library, http://amalfi.dis.unina.it/graph/.

[3]

D. G. Cory et al. quant-ph/0004104, April 2000.

[4]

H. K. Cummins et al. Physical Review Letters, 88:187901, 2002.

[5]

H. Häffner et al. Nature, 438:643--646, 2005.

[6]

R. Hughes et al. http://qist.lanl.gov/qcomp_map.shtml, 2004.

[7]

E. Knill et al. Physical Review Letters, 86(5811), 2001.

[8]

M. Laforest et al. Physical Review A, 75(012331), 2007.

[9]

L. Lavagno, G. Martin, and L. Scheffer, editors. Electronic Design Automation for Integrated Circuits Handbook. Taylor & Francis, 2006.

[10]

D. Maslov, S. M. Falconer, and M. Mosca. quant-ph/0703256.

[11]

R. Van Meter and K. M. Itoh. Physical Review A, 71(052320), May 2005.

[12]

R. Van Meter and M. Oskin. ACM Journal of Emerging Technologies in Computing Systems, 2(1):31--63, 2006.

Digital Library

[13]

C. Negrevergne et al. Physical Review Letters, 96(170501), 2006.

[14]

M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.

Digital Library

[15]

P. W. Shor. SIAM Journal of Computing, 26(5):1484--1509, 1997.

Digital Library

Cited By

Klusch MLässig JMüssig DMacaluso AWilhelm F(2024)Quantum Artificial Intelligence: A Brief SurveyKI - Künstliche Intelligenz10.1007/s13218-024-00871-8Online publication date: 4-Nov-2024
https://doi.org/10.1007/s13218-024-00871-8
Peham TBurgholzer LWille R(2023)On Optimal Subarchitectures for Quantum Circuit MappingACM Transactions on Quantum Computing10.1145/35935944:4(1-20)Online publication date: 25-Jul-2023
https://dl.acm.org/doi/10.1145/3593594
Zhou XFeng YLi S(2023)Supervised Learning Enhanced Quantum Circuit TransformationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.317922342:2(437-447)Online publication date: Feb-2023
https://doi.org/10.1109/TCAD.2022.3179223
Show More Cited By

Index Terms

Quantum circuit placement: optimizing qubit-to-qubit interactions through mapping quantum circuits into a physical experiment
1. Hardware
  1. Emerging technologies
  2. Very large scale integration design
2. Theory of computation
  1. Models of computation
    1. Abstract machines

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. ...
Quantum Circuit Placement

We study the problem of the practical realization of an abstract quantum circuit when executed on a quantum hardware. By practical, we mean adapting the circuit to particulars of the physical environment which restricts/complicates the establishment of ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '07: Proceedings of the 44th annual Design Automation Conference

June 2007

1016 pages

ISBN:9781595936271

DOI:10.1145/1278480

General Chair:
Steven P. Levitan
Univ. of Pittsburgh, Pittsburgh, PA

Copyright © 2007 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

The EDA Consortium
IEEE/CASS/CANDE/CEDA
SIGDA: ACM Special Interest Group on Design Automation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

DAC07

Sponsor:

SIGDA

DAC07: The 44th Annual Design Automation Conference 2007

June 4 - 8, 2007

California, San Diego

Acceptance Rates

DAC '07 Paper Acceptance Rate 152 of 659 submissions, 23%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
205
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Klusch MLässig JMüssig DMacaluso AWilhelm F(2024)Quantum Artificial Intelligence: A Brief SurveyKI - Künstliche Intelligenz10.1007/s13218-024-00871-8Online publication date: 4-Nov-2024
https://doi.org/10.1007/s13218-024-00871-8
Peham TBurgholzer LWille R(2023)On Optimal Subarchitectures for Quantum Circuit MappingACM Transactions on Quantum Computing10.1145/35935944:4(1-20)Online publication date: 25-Jul-2023
https://dl.acm.org/doi/10.1145/3593594
Zhou XFeng YLi S(2023)Supervised Learning Enhanced Quantum Circuit TransformationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.317922342:2(437-447)Online publication date: Feb-2023
https://doi.org/10.1109/TCAD.2022.3179223
Oddi ARasconi RBaioletti MSantucci VBeck H(2023)Quantum Circuit Compilation for the Graph Coloring ProblemAIxIA 2022 – Advances in Artificial Intelligence10.1007/978-3-031-27181-6_26(374-386)Online publication date: 11-Mar-2023
https://doi.org/10.1007/978-3-031-27181-6_26
Zhou XFeng YLi S(2022)Quantum Circuit Transformation: A Monte Carlo Tree Search FrameworkACM Transactions on Design Automation of Electronic Systems10.1145/351423927:6(1-27)Online publication date: 27-Jun-2022
https://dl.acm.org/doi/10.1145/3514239
Molavi AXu ADiges MPick LTannu SAlbarghouthi A(2022)Qubit Mapping and Routing via MaxSAT2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO)10.1109/MICRO56248.2022.00077(1078-1091)Online publication date: Oct-2022
https://doi.org/10.1109/MICRO56248.2022.00077
Zhu PZheng SWei LCheng XGuan ZFeng S(2022)The complexity of quantum circuit mapping with fixed parametersQuantum Information Processing10.1007/s11128-022-03698-021:10Online publication date: 27-Oct-2022
https://doi.org/10.1007/s11128-022-03698-0
Tannu SQureshi M(2019)Mitigating Measurement Errors in Quantum Computers by Exploiting State-Dependent BiasProceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3352460.3358265(279-290)Online publication date: 12-Oct-2019
https://dl.acm.org/doi/10.1145/3352460.3358265
Tannu SQureshi M(2019)Ensemble of Diverse MappingsProceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture10.1145/3352460.3358257(253-265)Online publication date: 12-Oct-2019
https://dl.acm.org/doi/10.1145/3352460.3358257
Tannu SQureshi MBahar IHerlihy MWitchel ELebeck A(2019)Not All Qubits Are Created EqualProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304007(987-999)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297858.3304007
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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents