Challenges and Opportunities in Quantum Optimization
Abstract
Quantum Computing (QC) is a new computational paradigm that promises significant speedup over classical computing in various domains. However, near-term QC faces numerous challenges, including limited qubit connectivity and noisy quantum operations. To address the qubit connectivity constraint, circuit mapping is required for executing quantum circuits on quantum computers. This process involves performing initial qubit placement and using the quantum SWAP operations to relocate non-adjacent qubits for nearest-neighbor interaction. Reducing the SWAP count in circuit mapping is essential for improving the success rate of quantum circuit execution as SWAPs are costly and error-prone. In this work, we introduce a novel circuit mapping method by combining incremental and parallel solving for Boolean Satisfiability (SAT). We present an innovative SAT encoding for circuit mapping problems, which significantly improves solver-based mapping methods and provides a smooth trade-off between compilation quality and compilation time. Through comprehensive benchmarking of 78 instances covering 3 quantum algorithms on 2 distinct quantum computer topologies, we demonstrate that our method is 26× faster than state-of-the-art solver-based methods, reducing the compilation time from hours to minutes for important quantum applications. Our method also surpasses the existing heuristics algorithm by 26% in SWAP count.
Authors 46
-
Affiliation as printed
QuSoft and University of Amsterdam
-
Affiliation as printed
University of Latvia
-
Massachusetts Institute of Technology
Affiliation as printed
Massachusetts Institute of Technology
-
Affiliation as printed
QuSoft and University of Amsterdam
-
Los Alamos National Laboratory
Affiliation as printed
Los Alamos National Laboratory
-
Affiliation as printed
E.ON Digital Technology GmbH
-
Vedran Dunjko Aachen
Affiliation as printed
Leiden University
-
Affiliation as printed
IBM Quantum , IBM Research Europe -Zurich
-
IBM Research - Thomas J. Watson Research Center
Affiliation as printed
IBM Research , IBM T.J. Watson Research Center
-
Fraunhofer Institute for Cognitive Systems
Affiliation as printed
Fraunhofer IKS 10 Erste Group Bank 11
-
Affiliation as printed
IBM Quantum , IBM T.J. Watson Research Center
-
Affiliation as printed
IBM Quantum , IBM T.J. Watson Research Center
-
IBM Research - Zurich · École Polytechnique Fédérale de Lausanne
Affiliation as printed
IBM Quantum , IBM Research Europe -Zurich
École Polytechnique Fédérale de Lausanne 13 Wells Fargo 14
-
Affiliation as printed
IBM Quantum , IBM T.J. Watson Research Center
-
Affiliation as printed
IBM Quantum , IBM T.J. Watson Research Center
-
Massachusetts Institute of Technology
Affiliation as printed
Massachusetts Institute of Technology
-
Universities Space Research Association · Research Institute for Advanced Computer Science · Quantum Intelligence (United States)
Affiliation as printed
Quantum Artificial Intelligence Lab , NASA Ames Research Center
USRA Research Institute for Advanced Computer Science
-
Fraunhofer Institute for Industrial Mathematics
Affiliation as printed
Fraunhofer ITWM 18 Quantagonia
-
Affiliation as printed
IBM Quantum , IBM T.J. Watson Research Center
-
Affiliation as printed
IBM Quantum , IBM T.J. Watson Research Center
-
Zuse Institute Berlin · Technische Universität Berlin
Affiliation as printed
Technische Universität Berlin
Zuse Institute Berlin
-
HSBC Holdings · Czech Technical University in Prague
Affiliation as printed
Czech Technical University in Prague
HSBC Lab , Innovation and Ventures , HSBC , London
-
Fraunhofer Institute of Optronics, System Technologies and Image Exploitation
Affiliation as printed
Fraunhofer IOSB-AST 24 University of Zurich
-
Czech Technical University in Prague
Affiliation as printed
Czech Technical University in Prague
-
Affiliation as printed
IBM Quantum , IBM T.J. Watson Research Center
-
Affiliation as printed
IBM Quantum , IBM T.J. Watson Research Center
-
Science and Technology Facilities Council
Affiliation as printed
The Hartree Centre , STFC
-
Affiliation as printed
E.ON Digital Technology GmbH
-
University of Southern California
Affiliation as printed
University of Southern California
-
Affiliation as printed
E.ON Digital Technology GmbH
-
Affiliation as printed
IBM Quantum , IBM Research Europe -Zurich
-
Zuse Institute Berlin · Technische Universität Berlin
Affiliation as printed
Technische Universität Berlin
Zuse Institute Berlin
-
Affiliation as printed
IBM Quantum , IBM Research Europe -Zurich
-
Centre for Quantum Technologies · National University of Singapore
Affiliation as printed
Centre for Quantum Technologies , National University of Singapore
-
Science and Technology Facilities Council
Affiliation as printed
The Hartree Centre , STFC
-
Science and Technology Facilities Council
Affiliation as printed
The Hartree Centre , STFC
-
Universität der Bundeswehr München
Affiliation as printed
University of the Bundeswehr Munich
-
Affiliation as printed
IBM Quantum , IBM Research Europe -Dublin
-
Affiliation as printed
IBM Quantum , IBM Research Europe -Zurich
-
Affiliation as printed
IBM Quantum , IBM Research Europe -Zurich
-
University of Waterloo · Perimeter Institute
Affiliation as printed
Institute for Quantum Computing , Perimeter Institute for Theoretical Physics , University of Waterloo
-
Affiliation as printed
Volkswagen AG
-
IBM (United States) · Tilburg University
Affiliation as printed
IBM Quantum , IBM T.J. Watson Research Center
Tilburg University
-
Affiliation as printed
IBM Quantum , IBM Research Europe -Dublin
-
Affiliation as printed
IBM Quantum , IBM Research Europe -Zurich
Cited by 8 stored of 8
8 results
No patents citing this paper on Lens.org (checked 2026-10-11).