Learning Shallow Quantum Circuits

Learning Shallow antum Circuits

Hsin-Yuan Huang

†

California Institute of Technology

Pasadena, USA

Google Quantum AI

Venice, USA

hsinyuan@caltech.edu

Yunchao Liu

†

University of California, Berkeley

Berkeley, USA

yunchaoliu@berkeley.edu

Michael Broughton

Google Quantum AI

Santa Barbara, USA

michael.broughton99@gmail.com

Isaac Kim

University of California, Davis

Davis, USA

isaac.kim.quantum@gmail.com

Anurag Anshu

Harvard University

Cambridge, USA

anuraganshu@fas.harvard.edu

Zeph Landau

University of California, Berkeley

Berkeley, USA

zeph.landau@gmail.com

Jarrod R. McClean

Google Quantum AI

Venice, USA

jarrod.mcc@gmail.com

ABSTRACT

Despite fundamental interests in learning quantum circuits, the

existence of a computationally ecient algorithm for learning shal-

low 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

푈

. We also provide a polynomial-time classical algorithm for

learning the description of any unknown

푛

-qubit state

휓

⟩

푈

푛

⟩

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 eciently navigated and enables ecient learning of quantum

circuits that are classically hard to simulate.

CCS CONCEPTS

•

Theory of computation

→

Quantum complexity theory

;

Quantum information theory

;

Machine learning theory

KEYWORDS

Quantum computing, Shallow quantum circuits, Quantum learning

theory, Quantum algorithms

†

Co-rst author. Both authors contributed equally (listed in alphabetical order).

STOC ’24, June 24–28, 2024, Vancouver, BC, Canada

2024 Copyright held by the owner/author(s).

ACM ISBN 979-8-4007-0383-6/24/06

https://doi.org/10.1145/3618260.3649722

ACM Reference Format:

Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag

Anshu, Zeph Landau, and Jarrod R. McClean. 2024. Learning Shallow Quan-

tum Circuits. In

Proceedings of the 56th Annual ACM Symposium on Theory

of Computing (STOC ’24), June 24–28, 2024, Vancouver, BC, Canada.

ACM,

New York, NY, USA,

pages.

https://doi.org/10.1145/3618260.3649722

1 INTRODUCTION

The question of how to eciently learn expressive classes of quan-

tum states and circuits features prominently in quantum complexity

theory, quantum algorithm design, and the experimental character-

ization of quantum devices. As a rst step, one might consider the

eciency of learning shallow (constant depth) quantum circuits,

where, to date, there has been no resolution despite considerable

interest from a number of angles. From a complexity perspective,

shallow quantum circuits are known to be more powerful than their

classical counterparts [

], and under widely accepted

complexity assumptions, sampling from the output distribution

of shallow quantum circuits is classically hard to simulate [

]. This computational power provides the basis for quan-

tum computational advantage with NISQ (noisy intermediate-scale

quantum) devices and supports the quest for developing quantum

algorithms based on learning parameterized shallow quantum cir-

cuits [

]. Within

an experimental setting focused on coherent errors or gate calibra-

tion, characterizing a NISQ device can be modeled as learning what

shallow quantum circuit the device is performing. Despite substan-

tial interest in the question of learning shallow quantum circuits

from these directions, to date, no polynomial time algorithm for

learning shallow quantum circuits has been found. In this work,

we introduce several ecient algorithms for two related tasks.

Theorem (Summary of main results).

There are polynomial

time algorithms for (1) learning the description of an unknown

푛

-qubit

shallow quantum circuit

푈

(with arbitrary unknown architecture)

within a small diamond distance, given access to

푈

; (2) learning the

description of an unknown

푛

-qubit state

휓

⟩

푈

푛

⟩

prepared by

This work is licensed under a Creative Commons Attribution 4.0 Interna-

tional License.

1343

STOC ’24, June 24–28, 2024, Vancouver, BC, Canada

Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R. McClean

a shallow quantum circuit

푈

(on a 2D lattice) within a small trace

distance, given copies of

휓

⟩

The main challenges in learning shallow quantum circuits are

twofold. While foundational results in computational learning the-

ory have established the ecient learnability of shallow classical

circuits [

], these techniques may not apply to shallow

quantum circuits, as these circuits can generate distributions with

nontrivial correlations over the entire system that are classically

hard to simulate [

]. Furthermore, even when the structure

of a shallow quantum circuit is known up to parameterization, the

optimization landscape for learning shallow quantum circuits is

swamped with exponentially many suboptimal local minima [

The bad optimization landscape causes standard optimization meth-

ods, such as gradient descent algorithms and Newton methods, to

fail in learning shallow quantum circuits.

To address these challenges, we consider a quantum circuit rep-

resentation based on

local inversions

, which yields an optimization

landscape that can be eciently navigated. The local inversions dis-

entangle qubits in each local region in a way that does not perturb

the remaining system. We then show how these local inversions

may be combined to build up the entire circuit without having to

solve a computationally hard problem. Together, this new tech-

nique enables us to learn a natural class of quantum circuits that

are classically hard to simulate.

1.1 Background

Learning shallow classical circuits.

Although the shallow quan-

tum case has many conceptual challenges resulting from non-

locality, the learnability of shallow classical circuits is a funda-

mental question in computational learning theory that has been

well-studied and resolved in many cases. Learning constant-depth

classical circuits with bounded fan-in gates (

) is equivalent to

learning juntas and can be performed in polynomial time from uni-

form samples [

]. In addition, quasi-polynomial time algorithms

are known for learning constant-depth classical circuits with un-

bounded fan-in AND/OR gates (

) [

], as well as

mod

푝

gates

(

[

푝

]

) [

] in the PAC model. The problem of learning shal-

low quantum circuits

(

QNC

)

and their output states are natural

quantum analogs of learning Boolean circuits. As

QNC

can be

exponentially more powerful than

for some computational

problems [

], it is natural to ask if shallow quantum circuits can

be learned eciently from random data samples.

Quantum machine learning.

When one parameterizes the gates

in a quantum circuit, the parameterized quantum circuit forms an

ML model, known as a

quantum neural network

, that can learn from

data and make predictions on new inputs [

Since deep parameterized quantum circuits suer from having

bar-

ren plateaus

in the optimization landscape [

] and are chal-

lenging to implement on noisy quantum devices [

], shallow

quantum circuits have been subject to extensive study in recent

years [

]. Various applications of learn-

ing shallow quantum circuits have been explored, ranging from

compressing quantum circuits for implementing a unitary [

], speeding up quantum dynamics [

], to

learning generative models for sampling from predicted distribu-

tions [

]. While the optimization landscape for

learning shallow quantum circuits is free from barren plateau [

the landscape is swamped with exponentially many suboptimal

local minima; see [

] for a study of this phenomenon. The presence

of a large number of suboptimal local minima causes standard lo-

cal optimization methods, such as gradient descent or Newton’s

method, to fail in learning parameterized shallow quantum circuits.

Ecient quantum tomography.

While quantum state and process

tomography generally require exponential resources, performing

tomography over some restricted families of states or processes

can be made computationally ecient. Examples of such families

include matrix product states [

], high-temperature Gibbs

states [

], stabilizer states [

], quantum phase

states [

], noninteracting Fermionic states [

], Cliord circuits

with a small number of T gates [

], Pauli channels under

structural assumptions [

], and interacting Hamiltonian

dynamics [

] (see [

] for a recent

survey). Most of these examples correspond to quantum circuit

families that are classically easy to simulate [

]. In

contrast, sampling from the output distribution of constant-depth

quantum circuits is classically hard even when restricted to a 2D

lattice [

]. The experimental eort to characterize NISQ devices

motivates the question of how to perform tomography for states

and processes generated by shallow quantum circuits. While these

states can be learned sample-eciently using shadow tomography

[

], no computationally ecient algorithms are known.

1.2 Our Results

We rst focus on cases where one is given black-box access to the

unknown unitary in (1) learning general shallow quantum circuits

and (2) learning geometrically-local shallow quantum circuits. We

then consider the more restricted model where one is only provided

access to copies of an unknown state and focus on (3) learning

quantum states prepared by geometrically-local shallow quantum

circuits on 2-dimensional lattices.

1.2.1 Learning General Shallow antum Circuits.

Let

푈

be an

unknown

푛

-qubit unitary generated by a shallow quantum circuit.

The learning algorithm uses a randomized measurement dataset

consisting of

푁

samples about

푈

[

]. This

dataset has been proposed as the classical shadow of

푈

[

Each classical data sample species a random

푛

-qubit product in-

put state

휓

ℓ

⟩

푛

푖

휓

ℓ,푖

⟩

and a randomized Pauli measurement

outcome

휙

ℓ

⟩

푛

푖

휙

ℓ,푖

⟩

on the output states

푈

휓

ℓ

⟩

, where

휓

ℓ,푖

⟩

휙

ℓ,푖

⟩ ∈ {|

⟩

|+⟩

|−⟩

+⟩

−⟩}

are single-qubit stabi-

lizer states. Each data sample can be generated by a single query

푈

. Our goal is to learn

푈

within a small diamond distance. The

following results have the form of learning a circuit

푉

acting on

푛

qubits, such that

∥

푉

−

푈

⊗

푈

†

∥

⋄

≤

휀

. Hence,

푉

can be used to

implement

푈

by tracing out the

푛

-qubit ancilla system.

Our rst main result shows that one can learn

푈

with a poly-

nomial sample and computational complexity, with only the as-

sumption that

푈

is constant-depth (i.e.,

푈

has arbitrary unknown

connectivity). Furthermore, the result applies even when the circuit

generating

푈

can have any number

푚

of ancilla qubits used as

working space and can have arbitrary two-qubit gates in

(

)

be-

tween any pair of the

푛

푚

qubits so long as the resulting operation

1344

Learning Shallow antum Circuits

STOC ’24, June 24–28, 2024, Vancouver, BC, Canada

on the

푛

system qubits is unitary. The learning algorithm is fully

classical given the randomized measurement dataset.

Theorem 1 (Learning shallow qantum circuits).

Given an

unknown

푛

-qubit unitary

푈

generated by a constant-depth circuit

over any two-qubit gates between any pair of qubits. One can learn a

constant-depth circuit approximating

푈

to diamond distance

휀

with

high probability from

푁

푛

log

(

푛

)

휀

)

samples about

푈

and

poly

(

푛

휀

classical running time.

When the circuit is over a nite gate set,

푈

can be learned to zero

error with high probability from

푁

log

푛

)

samples and

poly

(

푛

)

time.

1.2.2 Learning Geometrically-Local Shallow antum Circuits.

The

algorithm for learning general shallow quantum circuits runs in

polynomial time but with a large exponent. Furthermore, the depth

of the learned circuit

푉

, while constant, could be substantially

greater than the depth of

푈

. Motivated by the fact that most realistic

quantum systems are geometrically local on a nite-dimensional

lattice, it is natural to wonder if these aspects can be improved when

learning geometrically-local quantum circuits on lattices. Next, we

show that this is indeed the case.

Theorem 2 (Learning geometrically-local shallow cir-

cuits).

Given an unknown

푛

-qubit geometrically-local depth-

푑

quan-

tum circuit

푈

over a

푘

-dimensional lattice with

푑,푘

)

. One can

learn a geometrically-local shallow circuit that approximates

푈

diamond distance

휀

with high probability from

푁

푛

log

(

푛

)

휀

)

classical data samples and either

• O(

푛

log

(

푛

)

휀

)

classical running time with a learned circuit

depth of

(

푘

)

(

푘푑

)

푘

• (

푛

휀

)

O ( (

푘푑

)

푘

)

classical running time with a learned circuit

depth of

(

푘

)(

푑

) +

When the circuit is over a nite gate set,

푈

can be learned to zero error

with high probability from

푁

log

푛

)

samples and

푛

log

(

푛

)

time with a learned circuit depth of

(

푘

)(

푑

) +

This shows that in the geometrically local setting, the learned

circuit depth can achieve a linear blow-up. Furthermore, the learn-

ing algorithm works for

푑

polylog

(

푛

)

depth circuits at the cost

of quasipolynomial running time.

We remark that the more formal statement of the above theorem

can be straightforwardly generalized to a larger class of unitaries

called

quantum cellular automata

(QCA), which play an important

role in understanding quantum phases of matter [

These are unitaries that map any geometrically local operator to

a geometrically local operator in the Heisenberg picture. For any

such unitary, our proof technique applies without any modication,

yielding an ecient algorithm for learning any QCAs. Interestingly,

while shallow quantum circuits are QCAs by denition, the con-

verse statement is not necessarily true. For instance, shifting a set

of qubits on a one-dimensional lattice trivially maps local opera-

tors to local operators. However, it is impossible to decompose this

unitary into a geometrically local shallow quantum circuit [

]; see

Ref. [

] for other nontrivial examples of QCA. Therefore, our

algorithm is applicable beyond shallow quantum circuits.

So far, we have been focusing on learning a shallow quantum

circuit from a classical randomized measurement dataset. A nat-

ural question asks if further improvement is possible when we

allow more general quantum query access to

푈

. In the follow-

ing, we show that by using quantum queries to

푈

, an exponen-

tial improvement in query complexity is possible and this result

asymptotically-optimal

in both time and query complexity for

learning geometrically-local shallow circuits over nite gate sets.

Surprisingly, quantum access also allows these circuits to be

with

certainty

, dropping the familiar qualier of high probability. The

matching lower bounds stem from the need to query at least

(

)

times to obtain any information about

푈

and to write down the

learned

푛

-qubit circuit, which requires

(

푛

)

time.

Theorem 3 (Learning shallow circuits with qantum

qeries).

An unknown

푛

-qubit geometrically-local shallow quan-

tum circuit

푈

over a nite gate set can be learned to zero error with

zero failure probability using

(

)

queries to

푈

and

(

푛

)

quantum

computational time.

1.2.3 Learning Output States of Geometrically-Local Shallow an-

tum Circuits.

Besides learning the

푛

-qubit unitary

푈

using input-

output queries, it is natural to study the problem of learning a

pure quantum state

휓

⟩

prepared by a shallow quantum circuit

푈

i.e.,

휓

⟩

푈

푛

⟩

. Here, instead of given access to

푈

, we are only

given copies of the pure state

휓

⟩

as in quantum state tomogra-

phy [

]. As discussed in Section

1.1

, most families of ecient

learnable quantum states, such as matrix product states [

]

and stabilizer states [

], correspond to quantum circuit

families that are classically easy to simulate [

]. In contrast,

constant-depth quantum circuits are classically hard to simulate

even when restricted to a 2D lattice [

Learning

푈

푛

⟩

from copies of

푈

푛

⟩

has an incomparable di-

culty to the earlier results because it has a less stringent requirement

(learning an output state of

푈

) but a more restricted access model

(accessing copies of

푈

푛

⟩

instead of

푈

). While

휓

⟩

푈

푛

⟩

can

be learned from polynomially many copies [

], the restricted

access model makes the problem computationally more challeng-

ing, and the question of whether there exists a polynomial time

algorithm remains open. We give an ecient algorithm when

푈

restricted to a 2D lattice.

Theorem 4 (Learning qantum states prepared by 2D shal-

low circuits).

Given copies of an unknown pure state

휓

⟩

, with

the promise that

휓

⟩

푈

푛

⟩

for an unknown geometrically-local

circuit

푈

with depth

푑

over a 2-dimensional lattice. One can learn a

geometrically-local shallow circuit with depth

푑

that prepares

휓

⟩

to trace distance

휀

with high probability, using

O (

푑

)

· (

푛

휀

)

O (

)

copies of

휓

⟩

, in time

(

푛푑

휀

)

O (

푑

)

. When the circuit

푈

is over a nite

gate set,

휓

⟩

can be learned to zero error with high probability from

log

(

푛

)

copies and

푛

log

푛

)

time.

Similarly, this result applies to

푑

polylog

(

푛

)

depth at the

cost of quasipolynomial running time. The ecient learnability of

quantum states prepared by a shallow quantum circuit acting on

3D lattices (or on more general geometries) remains a challenging

and interesting open problem.

1.3 Discussion

Higher circuit depth.

In the general setting without geometric

locality, we show that log-depth circuits require exponentially many

1345

STOC ’24, June 24–28, 2024, Vancouver, BC, Canada

Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R. McClean

quantum queries to learn within a small diamond distance, which is

proven by showing that log-depth circuits can implement Grover’s

oracle over

푛

elements and applying the Grover lower bound [

Therefore, our result for eciently learning general constant-depth

quantum circuits cannot be extended to much higher depth.

In the geometrically-local setting, one of our theorems implies

polynomial-time learnability for quantum circuits on a

푘

-dimensional

lattice up to

log

(

푛

)

푘

depth, and quasi-polynomial time for up to

polylog

(

푛

)

depth. What structural assumptions allow us to e-

ciently learn quantum circuits beyond polylog-depth remains an

important open question.

Worst-case vs average-case distance.

Motivated by the above dis-

cussion, it is natural to consider learning quantum circuits under

weaker notions of distance, analogous to the classical notion of

PAC learning. The standard notion of average-case distance in the

literature [

] is dened as the distance between output states

when averaging over input states generated by Haar random uni-

taries. While learning polynomial-size quantum circuits to small

average-case distance can be achieved with polynomial sample

complexity [

], the computational complexity of achieving a

small average-case distance remains an open question.

In addition, Ref. [

] considered a weaker notion of an average-

case error where the goal is to learn observables of the output

state for random input states and showed that under this notion,

any quantum circuit (even those with exponential depth) could be

learned in quasi-polynomial time.

Verifying the learned shallow quantum circuit.

Our learning algo-

rithm provably works under the promise that the unknown

푛

-qubit

channel

corresponds to a unitary

휌

)

푈 휌푈

†

and the unitary

푈

is generated by a shallow quantum circuit. This promise does

not necessarily hold:

푈

could be a deep quantum circuit that may

or may not have a shallow quantum circuit implementation, and

may not be close to a unitary due to the noise in the quantum

device. Even if there is no promise of

, one can still bluntly apply

our learning algorithm to learn an

푛

-qubit channel

generated by

a shallow quantum circuit. However, the learned circuit

is no

longer guaranteed to be close to the true unknown channel

. This

raises the question of whether we can verify the learned circuit

or the promise on

In the full paper [

], we give an ecient verication algorithm

that outputs

pass

is close to

in the average-case distance and

is close to unitary. The verication algorithm outputs

fail

is not close to

. Because

is generated by a shallow quantum

circuit, the verication algorithm only needs to use the classical

dataset consisting of random input product states and randomized

Pauli measurement outcomes on the outputs of

Being able to verify the learned shallow quantum circuits is

central to applications such as compressing quantum circuits for

a known unitary. In this case, we have a known

푛

-qubit unitary

푈

that we know how to implement using a high-depth circuit.

The goal is to learn a low-depth circuit that approximates

푈

. If

푈

does have a shallow circuit implementation, then our algorithm

will learn a shallow circuit implementation for

푈

. However,

푈

may not have a shallow circuit implementation. In this case, the

verication algorithm can tell us that our learning algorithm has

failed. So far, we are using a simple verication algorithm based on

a (weak) approximate local identity test, which only guarantees a

small average-case distance. Whether more advanced verication

schemes can be used to achieve stronger guarantees eciently is

an interesting question that requires further exploration.

2 TECHNICAL OVERVIEW

In this section we give an overview of the key technical ideas; see

the full paper [

] for detailed proofs.

Let

푈

be an unknown

푛

-qubit circuit of depth

푑

)

. We

consider the following two tasks: (1) Learn a constant-depth circuit

푈

from random data samples from

푈

or query access to

푈

, such that

푈

and

푈

are close in diamond distance. (2) Learn a constant-depth

circuit

푈

from measuring copies of the

푛

-qubit state

휓

⟩

푈

푛

⟩

such that

푈

푛

⟩

and

푈

푛

⟩

are close in trace distance.

A basic idea to learn

푈

is to produce a guess

푈

and check if

푈

close to

푈

(i.e.,

푈

†

푈

is close to identity). While the search space

over

푈

is exponentially large, the

locality

of shallow circuits allows

us to search more eciently. For example, in the following gure,

we can nd a small

local inversion

circuit

푉

, that disentangles qubit

1 (the rightmost qubit), i.e.,

푈푉

≈

푈

′

⊗

퐼

. Here, the input wires

are at the bottom, and the output wires are at the top;

푉

is applied

before applying

푈

푉

≈

푈

′

(1)

This follows from a two-step argument. First, the existence of such a

local inversion circuit is guaranteed by the locality of

푈

, as undoing

the gates in the backward lightcone (shaded blue region) of qubit 1

forms such a local inversion. Second, given a guess

푉

, we develop

an ecient procedure to check

approximate local identity

, i.e.

푈푉

≈

푈

′

⊗

퐼

for some

푛

−

qubit unitary

푈

′

. This allows us to nd local

inversions via brute force enumerate-and-test since the search space

is small (as

푉

has depth

푑

and is supported within a constant size

region). Note that after this exhaustive process, we may nd a

list of valid local inversions. The “ground truth” local inversion

compatible with the unique global inverse of the unitary is among

them, but we do not know which one. Similarly, given copies of a

state

휓

⟩

푈

푛

⟩

we can nd small local inversion circuits

푉

disentangle qubit 1,

푉

휓

⟩ ≈ |

휓

′

⟩ ⊗ |

⟩

for some

푛

−

qubit state

휓

′

⟩

The above argument shows a procedure to eciently learn local

inversions for each qubit for both of our learning problems. The

central question is whether this suces to reconstruct the circuit

and, if so, whether the reconstruction can be done eciently. The

main obstacle is that local inversions for each qubit are not unique,

and two local inversions on neighboring qubits may not be consis-

tent in the overlapping regions. Finding a consistent set of local

inversions may require solving a constraint satisfaction problem

that is computationally hard. Next, we show how to overcome this

obstacle for learning

푈

and

휓

⟩

푈

푛

⟩

1346

Learning Shallow antum Circuits

STOC ’24, June 24–28, 2024, Vancouver, BC, Canada

2.1 Learning

푈

to a Small Diamond Distance

2.1.1 Sewing Local Inversions.

Suppose we have learned a set of

local inversions

푖

for an unknown shallow quantum circuit

푈

for

each qubit

푖

. Here, we show how to reconstruct the circuit using the

learned local information. Surprisingly, the algorithm only requires

arbitrary

element

푉

푖

∈ C

푖

for each qubit

푖

, without the need to

search for the element compatible with the global inverse, which

could require solving a complicated constraint satisfaction problem.

For simplicity, here we rst assume all the local inversions are

found exactly without any approximation. Take any

푉

∈ C

, ap-

plying it to the unknown circuit

푈

gives

푈푉

푈

′

⊗

퐼

, see Eq.

(

)

where we imagine qubit 1 to be the rightmost qubit and use a simple

1D geometry for illustration. This represents some progress: ap-

plying

푉

reduces the unknown

푛

-qubit unitary

푈

to an unknown

(

푛

−

)

-qubit unitary

푈

′

(note that

푈

′

may not be a shallow circuit).

A natural thought is whether we can keep making this progress

by applying local inversion on other qubits. The main issue here is

that now the unitary has changed. For example, consider qubit 2

which is right next to qubit 1. Due to the fact that they have overlap-

ping lightcones, some local inversion

푉

∈ C

may no longer work

for the new circuit

푈푉

. Separately, we can attempt to nd local

inversion for qubit 2 with respect to this new circuit

푈푉

; however,

doing so might disturb the progress we have made on qubit 1 and

therefore requires coordinated eort across dierent qubits. This is

exactly the type of constraint satisfaction problem that we want to

avoid.

Here we introduce a general approach to keep making progress:

the idea is to introduce a fresh ancilla qubit, swap it with qubit 1,

and then

undo

the local inversion

푉

. We show this in two steps:

rst, introduce a fresh ancilla qubit (red) and swap it with qubit 1,

푈

푉

푈

′

(2)

and then apply

푉

†

푈

푉

†

푈

′

푉

†

푈

(3)

To explain the second equality of Eq.

(

)

, note that without the

swap operation, the above procedure is not doing anything (since

we just perform some operation and undo it). In the second picture

of Eq.

(

)

, after experiencing

푉

†

, the red wire corresponds to the

rst output wire of

푈

, but then it gets swapped out to the ancilla.

Therefore, the overall eect is equivalent to performing a swap at

the end after applying

푈

The key reason that the above procedure is useful is because

repairs

the circuit. This allows us to continue doing the same

operation on qubit 2 because even though a lot of operations were

applied before

푈

(see the rst picture in Eq.

(

)

), it is equivalent to

as if nothing were applied before

푈

(see the last picture in Eq.

(

)

);

therefore we can similarly apply

푉

†

, swap with a new fresh qubit,

and

푉

before

푈

, achieving the eect of swapping qubit 2 at the

end. Repeating the above procedure for all qubits, we have learned

a circuit

푈

acting on

푛

qubits that satises

푈

learned circuit

푈

(4)

which implies that

푈

푆

·(

푈

⊗

푈

†

)

, where

푆

denotes the global swap

operation between the system and ancilla qubits. To implement

푈

using the learned circuit, on input

휌

we initialize an ancilla register

with some arbitrary state (say

푛

⟩

), apply

푆

푈

and trace out the

ancilla register, and the output state equals

푈 휌푈

†

. We can use a

similar procedure to implement

푈

†

. Thus, the above procedure

simultaneously learns to implement

푈

and

푈

†

, using access only

푈

Finally, we remark that the learned circuit

푆

푈

is shallow. To see

this, note that

푆

SWAP

⊗

푛

is depth-1.

푈

consists of unitaries of the

form

푊

푖

푉

푖

SWAP

푉

†

푖

that are

local

: each of them supports on

the lightcone of qubit

푖

, as well as an extra ancilla qubit. Therefore

we can implement non-overlapping

푊

푖

s simultaneously, and all of

the

푊

푖

s can be stacked into a constant number of layers since, at

most, a constant number of qubits share overlapping lightcones.

To achieve the optimal query and time complexity of

(

)

(

푛

)

for learning geometrically-local shallow quantum circuits over -

nite gate sets in Theorem

, we present a quantum learning al-

gorithm that nds the exact local inversions for all

푛

qubits with

zero failure probability by querying

푈

for only

)

times. This

surprising scaling is achieved by combining a few ideas: (a) coloring

the geometry described by a bounded-degree graph, (b) decoupling

the

푛

-qubit unitary

푈

into

푛

)

few-qubit channels based on the

coloring, and (c) designing a tournament to perfectly distinguish be-

tween two classes of few-qubit quantum channels: those that form

an exact local identity versus those that do not. The tournament

uses the perfect distinguishability of certain pairs of CPTP maps

shown in [

], where we design the few-qubit channels to ensure

perfect distinguishability. Then, the learning algorithm nds a good

order to sew the local inversions to produce a constant-depth circuit

implementation for the unknown constant-depth

푛

-qubit circuit

푈

2.1.2 Sewing Heisenberg-Evolved Pauli Operators.

Next, we de-

scribe a simpler technique based on directly sewing the Heisenberg-

evolved Pauli operators

푈

†

푃

푖

푈

(

푃

푖

is a single-qubit Pauli acting on

qubit

푖

) and discuss how it is closely related to local inversion.

We rst describe how to learn the Heisenberg-evolved Pauli oper-

ators. Because

푈

is a shallow quantum circuit, each operator

푈

†

푃

푖

푈

1347

STOC ’24, June 24–28, 2024, Vancouver, BC, Canada

Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R. McClean

acts on a constant number of qubits. The few-qubit observable

푈

†

푃

푖

푈

can be reconstructed from the randomized measurement

dataset. Let the random input product state be

휓

⟩

휓

⟩⊗· · ·⊗|

휓

푛

⟩

where

휓

푖

⟩

is a random one-qubit stabilizer state. Because each qubit

in the output state is measured in a random

푋,푌,푍

basis with equal

probability, we will measure

푃

푖

on the output state

푈

휓

⟩⟨

휓

푈

†

with

probability

. This allows us to estimate

⟨

휓

푈

†

푃

푖

푈

휓

⟩

. Then, we

show that we can eciently reconstruct

푈

†

푃

푖

푈

from a small num-

ber of dierent random input states.

After learning the

푛

Heisenberg-evolved Pauli operators

푈

†

푃

푖

푈

we present a direct approach for sewing them into a circuit. This

approach uses the identity

SWAP

푃

∈ {

퐼,푋,푌,푍

}

푃

⊗

푃

. Let

푆

푖

the

SWAP

gate acting on the

푖

-th system qubit and the

푖

-th ancilla

qubit, let

푆

⊗

푛

푖

푆

푖

be the global swap between system and ancilla,

and let

푊

푖

푈

†

푆

푖

푈

푃

∈ {

퐼,푋,푌,푍

}

푈

†

푃

푖

푈

⊗

푃,

∀

푖

, . . . ,푛

From the previous technique for sewing local inversion, we have

proven the identity

푈

⊗

푈

†

푆

푛

푖

(

푉

푖

푆

푖

푉

†

푖

)

(5)

where

푉

푖

satises

푈푉

푖

푈

′(

푖

)

⊗

퐼

푖

is an arbitrary exact local inver-

sion on qubit

푖

. We can see that

푉

푖

푆

푖

푉

†

푖

푈

†

푈푉

푖

푆

푖

푉

†

푖

푈

†

푈

†

푆

푖

푈

푊

푖

⇒

푈

⊗

푈

†

푆

푛

푖

푊

푖

푆

푛

푖

(

푈

†

푆

푖

푈

)

(6)

The new equation can also be seen by itself: simply cancel

푈

with

푈

†

in the product so that the right-hand side becomes

푆푈

†

푆푈

, and

observe that

푈

†

푈

†

푈

(7)

As we can see, the Heisenberg-evolved Pauli operators can be di-

rectly sewn into

푈

⊗

푈

†

This outlines the following procedure to learn

푈

: rst learn the

Heisenberg-evolved Pauli operators

{

푈

†

푃

푖

푈

}

푛

푖

, combine them to

form

{

푊

푖

}

푛

푖

according to

푊

푖

푃

∈ {

퐼,푋,푌,푍

}

푈

†

푃

푖

푈

⊗

푃

푖

, and

reconstruct the circuit using

{

푊

푖

}

푛

푖

. Note that each

푊

푖

acts on a

constant number

푘

of qubits and can be directly compiled into a

circuit of depth

푂

(

푘

)

. To further optimize the depth of the learned

circuit, notice that each

푊

푖

has the form

푊

푖

푈

†

푆

푖

푈

푉

푖

푆

푖

푉

†

푖

, i.e.,

it can be represented by a depth-

(

푑

)

circuit. We can nd such a

representation for

푊

푖

by brute-force enumerating all depth-

(

푑

)

circuits acting on

푘

qubits, and the learned circuit has the same

form as in Section

2.1.1

. This thus provides a simpler framework for

learning an unknown shallow quantum circuit

푈

using a classical

dataset containing random samples about

푈

To prove Theorem

and

on learning general and geometrically-

local shallow quantum circuits, we combine this framework with

some additional ideas on (a) coloring the

푘

-dimensional lattices to

ensure all qubits with the same color has nonoverlapping lightcone,

(b) truncating small Fourier coecients to ensure the learned ob-

servables acts only on qubits in the support of the true observables,

nite gate set, and (d) nding a good order to sew the Heisenberg-

evolved Pauli operators into a short-depth circuit.

2.2 Learning

푈

푛

⟩

to a Small Trace Distance

Next, we discuss how to learn a quantum state

휓

⟩

푈

푛

⟩

pre-

pared by a shallow circuit

푈

, given copies of

휓

⟩

. While this problem

appears to be simpler (we need to learn

푈

푛

⟩

instead of the entire

푈

), the weaker access model (we only have access to the output

푈

for the all-zero input state

푛

⟩

) poses new fundamental chal-

lenges. In particular, we can learn local inversions

푉

푖

that give

푉

푖

푈

푛

⟩

휓

′

⟩ ⊗ |

⟩

푖

instead of the much stronger

푈푉

푖

푈

′

⊗

퐼

푖

and the previous approach of “keep making progress by swapping

ancilla qubits” does not seem to work.

Here, we address these challenges by developing new techniques

tailored to a 2D lattice. The main idea is to

disentangle

the state into

many 1D-like states that are easy to learn by leveraging the fact

that 1D constraint satisfaction problems can be eciently solved.

2.2.1 Disentangling a 2D antum State.

Our starting point is the

simpler problem of learning a state

휓

⟩

푈

푛

⟩

, with the promise

that

푈

is a shallow circuit (white box) acting on a 1D lattice:

푈

퐴

퐵

퐶

(8)

Let

퐴

퐵

, and

퐶

be contiguous regions of constant size. We can nd a

set of local inversions

퐴

for

퐴

by enumerating over circuits acting

on the lightcone of

퐴

(blue shape). The question is how to combine

dierent local inversions into a circuit. The key observation is that

two neighboring local inversions can be merged together if they

are “consistent”, i.e., sharing the same gates where they overlap. For

example, some

푉

퐴

∈ C

퐴

(blue) and

푉

퐵

∈ C

퐵

(red) can be merged into

a larger circuit of the same depth

푉

퐴퐵

if they share the same gates

in the overlapping region (intersecting triangle); the merged circuit

푉

퐴퐵

satises

푉

퐴퐵

휓

⟩

휓

′

⟩ ⊗ |

⟩

퐴퐵

. This denes a constraint

satisfaction problem: we need to nd a local inversion for each

region such that neighboring local inversions are consistent. Such a

solution must exist (since the “ground truth” local inversions satisfy

these constraints), and we can eciently nd such a solution by

simple dynamic programming in time

푛

|C|

)

where

|C|

denotes

the maximum number of local inversions for a small region. This

gives a circuit

푉

that satises

푉

휓

⟩

푛

⟩

, so the state

휓

⟩

can be

prepared by

휓

⟩

푉

†

푛

⟩

From this perspective, generalizing this approach to 2D may

be a dicult task since constraint satisfaction problems on 2D

lattices are

-hard in general. We address this challenge using

an additional insight: instead of solving the constraint satisfaction

problem directly in 2D, we rst use the 1D argument to disentangle

the 2D state.

1348