skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Learning Shallow Quantum Circuits
Despite fundamental interests in learning quantum circuits, the existence of a computationally efficient algorithm for learning shallow quantum circuits remains an open question. Because shallow quantum circuits can generate distributions that are classically hard to sample from, existing learning algorithms do not apply. In this work, we present a polynomial-time classical algorithm for learning the description of any unknown 𝑛-qubit shallow quantum circuit π‘ˆ (with arbitrary unknown architecture) within a small diamond distance using single-qubit measurement data on the output states of π‘ˆ. We also provide a polynomial-time classical algorithm for learning the description of any unknown 𝑛-qubit state |πœ“βŸ© = π‘ˆ|0^π‘›βŸ© prepared by a shallow quantum circuit π‘ˆ (on a 2D lattice) within a small trace distance using single-qubit measurements on copies of |πœ“βŸ©. Our approach uses a quantum circuit representation based on local inversions and a technique to combine these inversions. This circuit representation yields an optimization landscape that can be efficiently navigated and enables efficient learning of quantum circuits that are classically hard to simulate.  more » « less
Award ID(s):
2013303 2238836 2311733
PAR ID:
10525478
Author(s) / Creator(s):
; ; ; ; ; ;
Publisher / Repository:
ACM
Date Published:
Page Range / eLocation ID:
1343 to 1351
Subject(s) / Keyword(s):
Quantum computing Shallow quantum circuits Quantum learning theory Quantum algorithms Quantum complexity theory Machine learning theory
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, ACM)
    Bansal, Nikhil (Ed.)
    QAC0 is the family of constant-depth polynomial-size quantum circuits consisting of arbitrary single qubit unitaries and multi-qubit Toffoli gates. It was introduced by Moore as a quantum counterpart of AC0, along with the conjecture that QAC0 circuits cannot compute PARITY. In this work, we make progress on this long-standing conjecture: we show that any depth-𝑑 QAC0 circuit requires 𝑛^{1+3^{βˆ’π‘‘}} ancillae to compute a function with approximate degree Θ(𝑛), which includes PARITY, MAJORITY and MOD_π‘˜. We further establish superlinear lower bounds on quantum state synthesis and quantum channel synthesis. This is the first lower bound on the super-linear sized QAC0. Regarding PARITY, we show that any further improvement on the size of ancillae to 𝑛^{1+exp(βˆ’π‘œ(𝑑))} would imply that PARITY βˆ‰ QAC0. These lower bounds are derived by giving low-degree approximations to QAC0 circuits. We show that a depth-𝑑 QAC0 circuit with π‘Ž ancillae, when applied to low-degree operators, has a degree (𝑛 + π‘Ž)^{1βˆ’3^{βˆ’π‘‘}} polynomial approximation in the spectral norm. This implies that the class QLC0, corresponding to linear size QAC0 circuits, has an approximate degree π‘œ(𝑛). This is a quantum generalization of the result that LC0 circuits have an approximate degree π‘œ(𝑛) by Bun, Kothari, and Thaler. Our result also implies that QLC0 β‰  NC1. 
    more » « less
  2. ; ; ; ; (, Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems)
    Quantum computing (QC) is a new paradigm offering the potential of exponential speedups over classical computing for certain computational problems. Each additional qubit doubles the size of the computational state space available to a QC algorithm. This exponential scaling underlies QC’s power, but today’s Noisy Intermediate-Scale Quantum (NISQ) devices face significant engineering challenges in scalability. The set of quantum circuits that can be reliably run on NISQ devices is limited by their noisy operations and low qubit counts. This paper introduces CutQC, a scalable hybrid computing approach that combines classical computers and quantum computers to enable evaluation of quantum circuits that cannot be run on classical or quantum computers alone. CutQC cuts large quantum circuits into smaller subcircuits, allowing them to be executed on smaller quantum devices. Classical postprocessing can then reconstruct the output of the original circuit. This approach offers significant runtime speedup compared with the only viable current alternative -- purely classical simulations -- and demonstrates evaluation of quantum circuits that are larger than the limit of QC or classical simulation. Furthermore, in real-system runs, CutQC achieves much higher quantum circuit evaluation fidelity using small prototype quantum computers than the state-of-the-art large NISQ devices achieve. Overall, this hybrid approach allows users to leverage classical and quantum computing resources to evaluate quantum programs far beyond the reach of either one alone. 
    more » « less
  3. ; ; ; ; ; ; ; (, Proceedings of the 3rd International Workshop on Post-Moore Era Supercomputing, 2018.)
    We describe how classical supercomputing can aid unreliable quantum processors of intermediate size to solve large problem instances reliably. We advocate using a hybrid quantum-classical architecture where larger quantum circuits are broken into smaller sub-circuits that are evaluated separately, either using a quantum processor or a quantum simulator running on a classical supercomputer. Circuit compilation techniques that determine which qubits are simulated classically will greatly impact the system performance as well as provide a tradeoff between circuit reliability and runtime. We describe how classical supercomputing can aid unreliable quantum processors of intermediate size to solve large problem instances reliably. We advocate using a hybrid quantum-classical architecture where larger quantum circuits are broken into smaller sub-circuits that are evaluated separately, either using a quantum processor or a quantum simulator running on a classical supercomputer. Circuit compilation techniques that determine which qubits are simulated classically will greatly impact the system performance as well as provide a tradeoff between circuit reliability and runtime. 
    more » « less
  4. ; ; ; ; ; ; ; (, https://doi.org/10.48550/arXiv.2411.04283)
    We study the problem of finding a (pure) product state with optimal fidelity to an unknown n-qubit quantum state ρ, given copies of ρ. This is a basic instance of a fundamental question in quantum learning: is it possible to efficiently learn a simple approximation to an arbitrary state? We give an algorithm which finds a product state with fidelity Ξ΅-close to optimal, using N=npoly(1/Ξ΅) copies of ρ and poly(N) classical overhead. We further show that estimating the optimal fidelity is NP-hard for error Ξ΅=1/poly(n), showing that the error dependence cannot be significantly improved. For our algorithm, we build a carefully-defined cover over candidate product states, qubit by qubit, and then demonstrate that extending the cover can be reduced to approximate constrained polynomial optimization. For our proof of hardness, we give a formal reduction from polynomial optimization to finding the closest product state. Together, these results demonstrate a fundamental connection between these two seemingly unrelated questions. Building on our general approach, we also develop more efficient algorithms in three simpler settings: when the optimal fidelity exceeds 5/6; when we restrict ourselves to a discrete class of product states; and when we are allowed to output a matrix product state. 
    more » « less
  5. ; ; ; (, npj Quantum Information)
    Abstract Random quantum circuits have been utilized in the contexts of quantum supremacy demonstrations, variational quantum algorithms for chemistry and machine learning, and blackhole information. The ability of random circuits to approximate any random unitaries has consequences on their complexity, expressibility, and trainability. To study this property of random circuits, we develop numerical protocols for estimating the frame potential, the distance between a given ensemble and the exact randomness. Our tensor-network-based algorithm has polynomial complexity for shallow circuits and is high-performing using CPU and GPU parallelism. We study 1. local and parallel random circuits to verify the linear growth in complexity as stated by the Brown–Susskind conjecture, and; 2. hardware-efficient ansΓ€tze to shed light on its expressibility and the barren plateau problem in the context of variational algorithms. Our work shows that large-scale tensor network simulations could provide important hints toward open problems in quantum information science. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email