(Quantum Accelerator) Coreset Quantum Computing: Addressing Large Data Sets with Small Quantum Computers
Abstract
Quantum computers offer a powerful new approach to tackling computational challenges that are otherwise intractable. However, the current state of hardware has severe constraints on the quality and quantity of quantum bits (qubits). In this near-term regime, where quantum computers have just tens of noisy qubits, how can we aim to address optimization problems involving thousands or millions of variables? This fundamental research question aligns with the Innovate Quantum U Tech Challenge's call for "strategies for performing large computations on limited qubit machines, including gate and problem decompositions". Our research responds to this call by exploring the connection between quantum computers and coresets. A coreset is a compact summary of a large classical data set, such that solving a problem on the coreset is equivalent to solving a problem on the full data set, up to an error guarantee. Recently, Harrow proposed in [Har20] to use coresets so that a quantum computer with a small number of qubits, N, can address a classical data set of size M > > N. However, the algorithms studied in [Har20] are untenable on noisy quantum computers.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 24, 2022
- Accession Number
- AD1230823
Entities
People
- Frederic Chong
Organizations
- University of Chicago