Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices
Open accessAbstract
Due to little considerations in the hardware constraints, e.g., limited connections between physical qubits to enable two-qubit gates, most quantum algorithms cannot be directly executed on the Noisy Intermediate-Scale Quantum (NISQ) devices. Dynamically remapping logical qubits to physical qubits in the compiler is needed to enable the two-qubit gates in the algorithm, which introduces additional operations and inevitably reduces the fidelity of the algorithm. Previous solutions in finding such remapping suffer from high complexity, poor initial mapping quality, and limited flexibility and control. To address these drawbacks mentioned above, this paper proposes a SWAP-based Bidirectional heuristic search algorithm (SABRE), which is applicable to NISQ devices with arbitrary connections between qubits. By optimizing every search attempt, globally optimizing the initial mapping using a novel reverse traversal technique, introducing the decay effect to enable the trade-off between the depth and the number of gates of the entire algorithm, SABRE outperforms the best known algorithm with exponential speedup and comparable or better results on various benchmarks.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
For mid-size circuits such as the SABRE-large benchmark, Duostra improves mapping costs by 4.5%, 5.2%, 16.3%, 20.7%, and 25.7%, when compared to QMAP, TOQM, t|ket>, Qiskit, and SABRE, respectively.
“Besides, for mid-size circuits such as the SABRE-large benchmark, we improve the mapping costs by 4.5%, 5.2%, 16.3%, 20.7%, and 25.7%, when compared to QMAP, TOQM, t | 𝑘𝑒𝑡 ⟩ , Qiskit, and SABRE, respectively.”
From Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits (2024) · cites this paper as [28]
Cites
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830 · see citing works
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830 · see citing works
A variational eigenvalue solver on a photonic quantum processor
Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P. J., Aspuru-Guzik, A., & O’Brien, J. L. (2014) · Nature Communications · doi:10.1038/ncomms5213 · Cited by 4,552 · cited 1× · see citing works
“Quantum Computing (QC) has been rapidly growing in the last decades because of its potential in various important applications, including integer factorization [1], database search [2], quantum simulation [3], etc.”
BackgroundElementary gates for quantum computation
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., & Weinfurter, H. (1995) · Physical Review A · doi:10.1103/physreva.52.3457 · Cited by 4,311 · see citing works
Floyd, R. W. (1962) · Communications of the ACM · doi:10.1145/367766.368168 · Cited by 4,094 · see citing works
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904 · see citing works
Charge-insensitive qubit design derived from the Cooper pair box
Koch, J., Yu, T. M., Gambetta, J., Houck, A. A., Schuster, D. I., Majer, J., Blais, A., Devoret, M. H., Girvin, S. M., & Schoelkopf, R. J. (2007) · Physical Review A · doi:10.1103/physreva.76.042319 · Cited by 3,351 · see citing works
Quantum information with Rydberg atoms
Saffman, M. E., Walker, T. G., & Mølmer, K. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.2313 · Cited by 2,796 · see citing works
Quantum Computation and Quantum Information: 10th Anniversary Edition
Nielsen, M. A., & Chuang, I. L. (2011) · Cited by 2,724 · see citing works
Characterizing quantum supremacy in near-term devices
Boixo, S., Isakov, S. V., Smelyanskiy, V. N., Babbush, R., Ding, N., Jiang, Z., Bremner, M. J., Martinis, J. M., & Neven, H. (2018) · Nature Physics · doi:10.1038/s41567-018-0124-x · Cited by 1,175 · see citing works
State preservation by repetitive error detection in a superconducting quantum circuit
Kelly, J., Barends, R., Fowler, A. G., Megrant, A., Jeffrey, E. R., White, T., Sank, D., Mutus, J., Campbell, B., Chen, Y., et al. (2015) · Nature · doi:10.1038/nature14270 · Cited by 913 · see citing works
An Efficient Algorithm for Exploiting Multiple Arithmetic Units
Tomasulo, R. M. (1967) · IBM Journal of Research and Development · doi:10.1147/rd.111.0025 · Cited by 898 · see citing works
Register allocation & spilling via graph coloring
Chaitin, G. J. (1982) · ACM SIGPLAN Notices · doi:10.1145/872726.806984 · Cited by 771 · see citing works
Qubit Architecture with High Coherence and Fast Tunable Coupling
Chen, Y., Neill, C., Roushan, P., Leung, N., Fang, M., Barends, R., Kelly, J., Campbell, B., Chen, Z., Chiaro, B., et al. (2014) · Physical Review Letters · doi:10.1103/physrevlett.113.220502 · Cited by 583 · see citing works
RevLib: An Online Resource for Reversible Functions and Reversible Circuits
Wille, R., Grosse, D. J., Teuber, L., Dueck, G. W., & Drechsler, R. (2008) · IEEE International Symposium on Multiple-Valued Logic (ISMVL) · doi:10.1109/ismvl.2008.43 · Cited by 509 · see citing works
Quantum computations on a topologically encoded qubit
Nigg, D., Müller, M., Martinez, E. A., Schindler, P., Hennrich, M., Monz, T., Martin-Delgado, M. A., & Blatt, R. (2014) · Science · doi:10.1126/science.1253742 · Cited by 400 · see citing works
Rapid High-Fidelity Single-Shot Dispersive Readout of Superconducting Qubits
Walter, T., Kurpiers, P., Gasparinetti, S., Magnard, P., Potočnik, A., Salathé, Y., Pechal, M., Mondal, M., Oppliger, M., Eichler, C., et al. (2017) · Physical Review Applied · doi:10.1103/physrevapplied.7.054020 · Cited by 372 · see citing works
Linear scan register allocation
Poletto, M., & Sarkar, V. (1999) · ACM Transactions on Programming Languages and Systems · doi:10.1145/330249.330250 · Cited by 360 · see citing works
Green, A. S., Lumsdaine, P. L., Ross, N. J., Selinger, P., & Valiron, B. (2013) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/2491956.2462177 · Cited by 341 · see citing works
Quantum computing and the entanglement frontier
Preskill, J. (2012) · arXiv · doi:10.48550/arxiv.1203.5813 · Cited by 308 · see citing works
Scalable Gate Architecture for a One-Dimensional Array of Semiconductor Spin Qubits
Zajac, D. M., Hazard, T., Mi, X., Nielsen, E., & Petta, J. R. (2016) · Physical Review Applied · doi:10.1103/physrevapplied.6.054013 · Cited by 291 · see citing works
Postpass Code Optimization of Pipeline Constraints
Hennessy, J. L., & Gross, T. R. (1983) · ACM Transactions on Programming Languages and Systems · doi:10.1145/2166.357217 · Cited by 272 · see citing works
Siraichi, M. Y., Santos, V. F. D., Collange, C., & Pereira, F. M. Q. (2018) · Proceedings of the 2018 International Symposium on Code Generation and Optimization · doi:10.1145/3168822 · Cited by 254 · see citing works
Programming languages and compiler design for realistic quantum hardware
Chong, F. T., Franklin, D. M., & Martonosi, M. (2017) · Nature · doi:10.1038/nature23459 · Cited by 233 · see citing works
Synthesis of quantum circuits for linear nearest neighbor architectures
Saeedi, M., Wille, R., & Drechsler, R. (2010) · Quantum Information Processing · doi:10.1007/s11128-010-0201-2 · Cited by 213 · see citing works
Green, A. S., Lumsdaine, P. L., Ross, N. J., Selinger, P., & Valiron, B. (2013) · ACM SIGPLAN Notices · doi:10.1145/2499370.2462177 · Cited by 158 · see citing works
(2014) · doi:10.1145/2597917.2597939 · Cited by 152 · see citing works
Compiling quantum circuits to realistic hardware architectures using temporal planners
Venturelli, D., Do, M., Rieffel, E. G., & Frank, J. (2017) · Quantum Science and Technology · doi:10.1088/2058-9565/aaa331 · Cited by 137 · see citing works
Optimization of quantum circuits for interaction distance in linear nearest neighbor architectures
Shafaei, A., Saeedi, M., & Pedram, M. (2013) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1145/2463209.2488785 · Cited by 123 · see citing works
Qubit placement to minimize communication overhead in 2D quantum architectures
Shafaei, A., Saeedi, M., & Pedram, M. (2014) · Asia and South Pacific Design Automation Conference (ASP-DAC) · doi:10.1109/aspdac.2014.6742940 · Cited by 121 · see citing works
Look-ahead schemes for nearest neighbor optimization of 1D and 2D quantum circuits
Wille, R., Keszöcze, O., Walter, M., Rohrs, P., Chattopadhyay, A., & Drechsler, R. (2016) · Asia and South Pacific Design Automation Conference (ASP-DAC) · doi:10.1109/aspdac.2016.7428026 · Cited by 120 · see citing works
A blueprint for building a quantum computer
Meter, R. V., & Horsman, D. C. (2013) · Communications of the ACM · doi:10.1145/2494568 · Cited by 114 · see citing works
Maslov, D. A., Falconer, S. M., & Mosca, M. (2008) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2008.917562 · Cited by 113 · see citing works
Efficient mapping of quantum circuits to the IBM QX architectures
Zulehner, A., Paler, A., & Wille, R. (2018) · Design, Automation, and Test in Europe · doi:10.23919/date.2018.8342181 · Cited by 108 · see citing works
Determining the minimal number of swap gates for multi-dimensional nearest neighbor quantum circuits
Lye, A., Wille, R., & Drechsler, R. (2015) · Asia and South Pacific Design Automation Conference (ASP-DAC) · doi:10.1109/aspdac.2015.7059001 · Cited by 104 · see citing works
An experimental microarchitecture for a superconducting quantum processor
Fu, X., Rol, M. A., Bultink, C. C., van Someren, J., Khammassi, N., Ashraf, I., Vermeulen, R. F. L., de Sterke, J. C., Vlothuizen, W., Schouten, R. N., et al. (2017) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1145/3123939.3123952 · Cited by 99 · see citing works
Fault-tolerant, high-level quantum circuits: form, compilation and description
Paler, A., Polian, I., Nemoto, K., & Devitt, S. (2015) · Quantum Science and Technology · doi:10.1088/2058-9565/aa66eb · Cited by 97 · see citing works
Optimal SWAP gate insertion for nearest neighbor quantum circuits
Wille, R., Lye, A., & Drechsler, R. (2014) · Asia and South Pacific Design Automation Conference (ASP-DAC) · doi:10.1109/aspdac.2014.6742939 · Cited by 96 · see citing works
A functional architecture for scalable quantum computing
Sete, E. A., Zeng, W. J., & Rigetti, C. T. (2016) · IEEE International Conference on Rebooting Computing (ICRC) · doi:10.1109/icrc.2016.7738703 · Cited by 90 · see citing works
Kole, A., Datta, K., & Sengupta, I. (2016) · IEEE Journal on Emerging and Selected Topics in Circuits and Systems · doi:10.1109/jetcas.2016.2528720 · Cited by 70 · see citing works
A New Heuristic for $N$ -Dimensional Nearest Neighbor Realization of a Quantum Circuit
Kole, A., Datta, K., & Sengupta, I. (2017) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2017.2693284 · Cited by 68 · see citing works
PAQCS: Physical Design-Aware Fault-Tolerant Quantum Circuit Synthesis
Lin, C.-C., Sur‐Kolay, S., & Jha, N. K. (2014) · IEEE Transactions on Very Large Scale Integration (VLSI) Systems · doi:10.1109/tvlsi.2014.2337302 · Cited by 67 · see citing works
Optimized surface code communication in superconducting quantum computers
Javadi-Abhari, A., Gokhale, P., Holmes, A. A., Franklin, D. M., Brown, K. R., Martonosi, M., & Chong, F. T. (2017) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1145/3123939.3123949 · Cited by 61 · see citing works
A Unified Modulo Scheduling and Register Allocation Technique for Clustered Processors
Codina, J., Sánchez, J., & González, A. M. (2001) · doi:10.5555/645988.674300 · Cited by 55 · see citing works
Linear Nearest Neighbor Synthesis of Reversible Circuits by Graph PartitioningPreprint
Chakrabarti, A., Sur‐Kolay, S., & Chaudhury, A. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1112.0564 · Cited by 52 · see citing works
A Case for Variability-Aware Policies for NISQ-Era Quantum ComputersPreprint
Tannu, S., & Qureshi, M. K. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.10224 · Cited by 49 · see citing works
Fast Qubit Placement in 2D Architecture Using Nearest Neighbor Realization
Shrivastwa, R. R., Datta, K., & Sengupta, I. (2015) · IEEE International Symposium on Nanoelectronic and Information Systems (iNIS) · doi:10.1109/inis.2015.59 · Cited by 42 · see citing works
Temporal Planning for Compilation of Quantum Approximate Optimization Circuits
Venturelli, D., Do, M., Rieffel, E. G., & Frank, J. (2017) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2017/620 · Cited by 42 · see citing works
Compiler Management of Communication and Parallelism for Quantum Computation
Heckey, J., Patil, S. R., Javadi-Abhari, A., Holmes, A. A., Kudrow, D., Brown, K. R., Franklin, D. M., Chong, F. T., & Martonosi, M. (2015) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/2694344.2694357 · Cited by 40 · see citing works
Greedy Randomized Search for Scalable Compilation of Quantum Circuits
Oddi, A., & Rasconi, R. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-93031-2_32 · Cited by 36 · see citing works
A Novel Approach for Nearest Neighbor Realization of 2D Quantum Circuits
Bhattacharjee, A., Bandyopadhyay, C., Wille, R., Drechsler, R., & Rahaman, H. (2018) · IEEE Computer Society Annual Symposium on VLSI · doi:10.1109/isvlsi.2018.00063 · Cited by 35 · see citing works
Compiler Management of Communication and Parallelism for Quantum Computation
Heckey, J., Patil, S. R., Javadi-Abhari, A., Holmes, A. A., Kudrow, D., Brown, K. R., Franklin, D. M., Chong, F. T., & Martonosi, M. (2015) · ACM SIGARCH Computer Architecture News · doi:10.1145/2786763.2694357 · Cited by 14 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 1,726 · see citing works
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E. G., Venturelli, D., & Biswas, R. (2019) · Algorithms · doi:10.3390/a12020034 · Cited by 772 · see citing works
Mapping Quantum Circuits to IBM QX Architectures Using the Minimal Number of SWAP and H Operations
Wille, R., Burgholzer, L., & Zulehner, A. (2019) · Proceedings of the 56th Annual Design Automation Conference 2019 · doi:10.1145/3316781.3317859 · Cited by 207 · see citing works
Optimal layout synthesis for quantum computing
Tan, B., & Cong, J. (2020) · Proceedings of the 39th International Conference on Computer-Aided Design · doi:10.1145/3400302.3415620 · Cited by 126 · see citing works
Zhang, C., Hayes, A. B., Qiu, L., Jin, Y., Chen, Y., & Zhang, E. Z. (2021) · Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems · doi:10.1145/3445814.3446706 · Cited by 74 · see citing works
Timing and Resource-Aware Mapping of Quantum Circuits to Superconducting Processors
Lao, L., van Someren, H., Ashraf, I., & Almudever, C. G. (2022) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2021.3057583 · Cited by 72 · see citing works
Demonstration of quantum volume 64 on a superconducting quantum computing system
Jurcevic, P., Javadi-Abhari, A., Bishop, L. S., Lauer, I., Bogorin, D. F., Brink, M., Capelluto, L., Günlük, O., Itoko, T., Kanazawa, N., et al. (2021) · Quantum Science and Technology · doi:10.1088/2058-9565/abe519 · Cited by 85 · see citing works
Qubit Mapping and Routing via MaxSAT
Molavi, A., Xu, A., Diges, M., Pick, L., Tannu, S., & Albarghouthi, A. (2022) · 2022 55th IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1109/micro56248.2022.00077 · Cited by 54 · see citing works
Codar: A Contextual Duration-Aware Qubit Mapping for Various NISQ Devices
Deng, H., Zhang, Y., & Li, Q. (2020) · 2020 57th ACM/IEEE Design Automation Conference (DAC) · doi:10.1109/dac18072.2020.9218561 · Cited by 23 · see citing works
Robust Qubit Mapping Algorithm via Double-Source Optimal Routing on Large Quantum Circuits
Cheng, C.-Y., Yang, C.-Y., Kuo, Y.-H., Wang, R.-C., Cheng, H.-C., & Huang, C.-Y. (. (2024) · ACM Transactions on Quantum Computing · doi:10.1145/3680291 · Cited by 19 · see citing works
Quantum CNOT Circuits Synthesis for NISQ Architectures Using the Syndrome Decoding Problem
de Brugière, T. G., Baboulin, M., Valiron, B., Martiel, S., & Allouche, C. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-52482-1_11 · Cited by 18 · see citing works
- Authors
- Li, G., Ding, Y., & Xie, Y.
- Affiliations
- University of California, Santa Barbara (US)
- Venue
- Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems
- Publisher
- ACM
- Published
- 2019-04-04
- Pages
- 1001-1014
- OpenAlex
- W2889938786
- Semantic Scholar
- 40f3af4560bfb6b2509d5677c40a2ab439bf4f3a
- Cited by
- 594
- References
- 52
- Citations by year
- 2026: 63 · 2025: 139 · 2024: 94 · 2023: 82 · 2022: 86 · 2021: 53 · 2020: 62 · 2019: 15
- FWCI
- 20.66
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- Rare & Special e-Zone (The Hong Kong University of Science and Technology) (submittedVersion)
- arXiv (Cornell University)
- Funders
- National Science Foundation (1730309)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Keywords
- qubit mapping, NISQ devices, quantum circuit compilation
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
