SC20 Proceedings

The International Conference for High Performance Computing, Networking, Storage, and Analysis

A QUBO Formulation for Qubit Allocation

Workshop:First International Workshop on Quantum Computing Software

Authors: Bryan Dury (University of British Columbia; TRIUMF, Canada) and Olivia Di Matteo (TRIUMF, Canada)

Abstract: To run an algorithm on a quantum computer, one must choose an assignment from logical qubits in a circuit to physical qubits on quantum hardware. This task of initial qubit placement, or qubit allocation, is especially important on present-day quantum computers which have a limited number of qubits, connectivity constraints, and varying gate fidelities.

In this work, we formulate and implement the qubit placement problem as a quadratic, unconstrained binary optimization (QUBO) problem and solve it using simulated annealing to obtain a spectrum of initial placements. Compared to contemporary allocation methods available in tket and Qiskit, the QUBO method yields allocations with improved circuit depth for >50% of a large set of benchmark circuits, with many also requiring fewer CX gates.

Back to First International Workshop on Quantum Computing Software Archive Listing

Back to Full Workshop Archive Listing