Skip to main content

SQUARE: Strategic Quantum Ancilla Reuse for Modular Quantum Programs via Cost-Effective Uncomputation

Author(s): Ding, Yongshan; Wu, Xin-Chuan; Holmes, Adam; Wiseth, Ash; Franklin, Diana; et al

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1qg3h
Full metadata record
DC FieldValueLanguage
dc.contributor.authorDing, Yongshan-
dc.contributor.authorWu, Xin-Chuan-
dc.contributor.authorHolmes, Adam-
dc.contributor.authorWiseth, Ash-
dc.contributor.authorFranklin, Diana-
dc.contributor.authorMartonosi, Margaret-
dc.contributor.authorChong, Frederic T-
dc.date.accessioned2021-10-08T19:51:25Z-
dc.date.available2021-10-08T19:51:25Z-
dc.date.issued2020en_US
dc.identifier.citationDing, Yongshan, Xin-Chuan Wu, Adam Holmes, Ash Wiseth, Diana Franklin, Margaret Martonosi, and Frederic T. Chong. "SQUARE: Strategic Quantum Ancilla Reuse for Modular Quantum Programs via Cost-Effective Uncomputation." In ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA) (2020): pp. 570-583. doi:10.1109/ISCA45697.2020.00054en_US
dc.identifier.urihttps://arxiv.org/pdf/2004.08539.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1qg3h-
dc.description.abstractCompiling high-level quantum programs to machines that are size constrained (i.e. limited number of quantum bits) and time constrained (i.e. limited number of quantum operations) is challenging. In this paper, we present SQUARE (Strategic QUantum Ancilla REuse), a compilation infrastructure that tackles allocation and reclamation of scratch qubits (called ancilla) in modular quantum programs. At its core, SQUARE strategically performs uncomputation to create opportunities for qubit reuse.Current Noisy Intermediate-Scale Quantum (NISQ) computers and forward-looking Fault-Tolerant (FT) quantum computers have fundamentally different constraints such as data locality, instruction parallelism, and communication overhead. Our heuristic-based ancilla-reuse algorithm balances these considerations and fits computations into resource-constrained NISQ or FT quantum machines, throttling parallelism when necessary. To precisely capture the workload of a program, we propose an improved metric, the “active quantum volume,” and use this metric to evaluate the effectiveness of our algorithm. Our results show that SQUARE improves the average success rate of NISQ applications by 1. 47X. Surprisingly, the additional gates for uncomputation create ancilla with better locality, and result in substantially fewer swap gates and less gate noise overall. SQUARE also achieves an average reduction of 1. 5X (and up to 9. 6X) in active quantum volume for FT machines.en_US
dc.format.extent570 - 583en_US
dc.language.isoen_USen_US
dc.relation.ispartofACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA)en_US
dc.rightsAuthor's manuscripten_US
dc.titleSQUARE: Strategic Quantum Ancilla Reuse for Modular Quantum Programs via Cost-Effective Uncomputationen_US
dc.typeConference Articleen_US
dc.identifier.doi10.1109/ISCA45697.2020.00054-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
Square.pdf741.15 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.