TY - GEN
T1 - Optimal Layout Synthesis for Deep Quantum Circuits on NISQ Processors with 100+ Qubits
AU - Shaik, Irfansha
AU - Van de Pol, Jaco
N1 - Publisher Copyright:
© Irfansha Shaik and Jaco van de Pol.
PY - 2024/8
Y1 - 2024/8
N2 - Layout synthesis is mapping a quantum circuit to a quantum processor. SWAP gate insertions are needed for scheduling 2-qubit gates only on connected physical qubits. With the ever-increasing number of qubits in NISQ processors, scalable layout synthesis is of utmost importance. With large optimality gaps observed in heuristic approaches, scalable exact methods are needed. While recent exact and near-optimal approaches scale to moderate circuits, large deep circuits are still out of scope. In this work, we propose a SAT encoding based on parallel plans that apply 1 SWAP and a group of CNOTs at each time step. Using domain-specific information, we maintain optimality in parallel plans while scaling to large and deep circuits. From our results, we show the scalability of our approach which significantly outperforms leading exact and near-optimal approaches (up to 100x). For the first time, we can optimally map several 8, 14, and 16 qubit circuits onto 54, 80, and 127 qubit platforms with up to 17 SWAPs. While adding optimal SWAPs, we also report near-optimal depth in our mapped circuits.
AB - Layout synthesis is mapping a quantum circuit to a quantum processor. SWAP gate insertions are needed for scheduling 2-qubit gates only on connected physical qubits. With the ever-increasing number of qubits in NISQ processors, scalable layout synthesis is of utmost importance. With large optimality gaps observed in heuristic approaches, scalable exact methods are needed. While recent exact and near-optimal approaches scale to moderate circuits, large deep circuits are still out of scope. In this work, we propose a SAT encoding based on parallel plans that apply 1 SWAP and a group of CNOTs at each time step. Using domain-specific information, we maintain optimality in parallel plans while scaling to large and deep circuits. From our results, we show the scalability of our approach which significantly outperforms leading exact and near-optimal approaches (up to 100x). For the first time, we can optimally map several 8, 14, and 16 qubit circuits onto 54, 80, and 127 qubit platforms with up to 17 SWAPs. While adding optimal SWAPs, we also report near-optimal depth in our mapped circuits.
KW - Layout Synthesis
KW - Parallel Plans
KW - Propositional Satisfiability
KW - Quantum Circuits
KW - Qubit Mapping and Routing
KW - Transpiling
UR - https://www.scopus.com/pages/publications/85202360644
U2 - 10.4230/LIPIcs.SAT.2024.26
DO - 10.4230/LIPIcs.SAT.2024.26
M3 - Article in proceedings
AN - SCOPUS:85202360644
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 27th International Conference on Theory and Applications of Satisfiability Testing, SAT 2024
A2 - Chakraborty, Supratik
A2 - Jiang, Jie-Hong Roland
PB - Dagstuhl Publishing
T2 - 27th International Conference on Theory and Applications of Satisfiability Testing, SAT 2024
Y2 - 21 August 2024 through 24 August 2024
ER -