IEICE TRANSACTIONS on Fundamentals
A SAT Approach to the Initial Mapping Problem in SWAP Gate Insertion for Commuting Gates
Summary :
Most quantum circuits require SWAP gate insertion to run on quantum hardware with limited qubit connectivity. A promising SWAP gate insertion method for blocks of commuting two-qubit gates is a predetermined swap strategy which applies layers of SWAP gates simultaneously executable on the coupling map. A good initial mapping for the swap strategy reduces the number of required swap gates. However, even when a circuit consists of commuting gates, e.g., as in the Quantum Approximate Optimization Algorithm (QAOA) or trotterized simulations of Ising Hamiltonians, finding a good initial mapping is a hard problem. We present a SAT-based approach to find good initial mappings for circuits with commuting gates transpiled to the hardware with swap strategies. Our method achieves a 65% reduction in gate count for random three-regular graphs with 500 nodes. In addition, we present a heuristic approach that combines the SAT formulation with a clustering algorithm to reduce large problems to a manageable size. This approach reduces the number of swap layers by 25% compared to both a trivial and random initial mapping for a random three-regular graph with 1000 nodes. Good initial mappings will therefore enable the study of quantum algorithms, such as QAOA and Ising Hamiltonian simulation applied to sparse problems, on noisy quantum hardware with several hundreds of qubits.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.11 pp.1424-1431
- Publication Date
- 2023/11/01
- Publicized
- 2023/05/17
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2022EAP1159
- Type of Manuscript
- PAPER
- Category
- Algorithms and Data Structures
Authors
Atsushi MATSUO
IBM Quantum, IBM Research -- Tokyo,Ritsumeikan University
Shigeru YAMASHITA
Ritsumeikan University
Daniel J. EGGER
IBM Quantum, IBM Research -- Zürich Rüschlikon
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Atsushi MATSUO, Shigeru YAMASHITA, Daniel J. EGGER, "A SAT Approach to the Initial Mapping Problem in SWAP Gate Insertion for Commuting Gates" in IEICE TRANSACTIONS on Fundamentals,
vol. E106-A, no. 11, pp. 1424-1431, November 2023, doi: 10.1587/transfun.2022EAP1159.
Abstract: Most quantum circuits require SWAP gate insertion to run on quantum hardware with limited qubit connectivity. A promising SWAP gate insertion method for blocks of commuting two-qubit gates is a predetermined swap strategy which applies layers of SWAP gates simultaneously executable on the coupling map. A good initial mapping for the swap strategy reduces the number of required swap gates. However, even when a circuit consists of commuting gates, e.g., as in the Quantum Approximate Optimization Algorithm (QAOA) or trotterized simulations of Ising Hamiltonians, finding a good initial mapping is a hard problem. We present a SAT-based approach to find good initial mappings for circuits with commuting gates transpiled to the hardware with swap strategies. Our method achieves a 65% reduction in gate count for random three-regular graphs with 500 nodes. In addition, we present a heuristic approach that combines the SAT formulation with a clustering algorithm to reduce large problems to a manageable size. This approach reduces the number of swap layers by 25% compared to both a trivial and random initial mapping for a random three-regular graph with 1000 nodes. Good initial mappings will therefore enable the study of quantum algorithms, such as QAOA and Ising Hamiltonian simulation applied to sparse problems, on noisy quantum hardware with several hundreds of qubits.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2022EAP1159/_p
Copy
@ARTICLE{e106-a_11_1424,
author={Atsushi MATSUO, Shigeru YAMASHITA, Daniel J. EGGER, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A SAT Approach to the Initial Mapping Problem in SWAP Gate Insertion for Commuting Gates},
year={2023},
volume={E106-A},
number={11},
pages={1424-1431},
abstract={Most quantum circuits require SWAP gate insertion to run on quantum hardware with limited qubit connectivity. A promising SWAP gate insertion method for blocks of commuting two-qubit gates is a predetermined swap strategy which applies layers of SWAP gates simultaneously executable on the coupling map. A good initial mapping for the swap strategy reduces the number of required swap gates. However, even when a circuit consists of commuting gates, e.g., as in the Quantum Approximate Optimization Algorithm (QAOA) or trotterized simulations of Ising Hamiltonians, finding a good initial mapping is a hard problem. We present a SAT-based approach to find good initial mappings for circuits with commuting gates transpiled to the hardware with swap strategies. Our method achieves a 65% reduction in gate count for random three-regular graphs with 500 nodes. In addition, we present a heuristic approach that combines the SAT formulation with a clustering algorithm to reduce large problems to a manageable size. This approach reduces the number of swap layers by 25% compared to both a trivial and random initial mapping for a random three-regular graph with 1000 nodes. Good initial mappings will therefore enable the study of quantum algorithms, such as QAOA and Ising Hamiltonian simulation applied to sparse problems, on noisy quantum hardware with several hundreds of qubits.},
keywords={},
doi={10.1587/transfun.2022EAP1159},
ISSN={1745-1337},
month={November},}
Copy
TY - JOUR
TI - A SAT Approach to the Initial Mapping Problem in SWAP Gate Insertion for Commuting Gates
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1424
EP - 1431
AU - Atsushi MATSUO
AU - Shigeru YAMASHITA
AU - Daniel J. EGGER
PY - 2023
DO - 10.1587/transfun.2022EAP1159
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E106-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2023
AB - Most quantum circuits require SWAP gate insertion to run on quantum hardware with limited qubit connectivity. A promising SWAP gate insertion method for blocks of commuting two-qubit gates is a predetermined swap strategy which applies layers of SWAP gates simultaneously executable on the coupling map. A good initial mapping for the swap strategy reduces the number of required swap gates. However, even when a circuit consists of commuting gates, e.g., as in the Quantum Approximate Optimization Algorithm (QAOA) or trotterized simulations of Ising Hamiltonians, finding a good initial mapping is a hard problem. We present a SAT-based approach to find good initial mappings for circuits with commuting gates transpiled to the hardware with swap strategies. Our method achieves a 65% reduction in gate count for random three-regular graphs with 500 nodes. In addition, we present a heuristic approach that combines the SAT formulation with a clustering algorithm to reduce large problems to a manageable size. This approach reduces the number of swap layers by 25% compared to both a trivial and random initial mapping for a random three-regular graph with 1000 nodes. Good initial mappings will therefore enable the study of quantum algorithms, such as QAOA and Ising Hamiltonian simulation applied to sparse problems, on noisy quantum hardware with several hundreds of qubits.
ER -
English
