Representational separation between unitary and channel quantum generative models via shared classical randomness at shallow depth

Representational separation between unitary and channel quantum generative models via shared classical randomness at shallow depth Arunava Majumder,∗ Marius Krumm, Hendrik Poulsen Nautrup, and Hans J. Briegel

arXiv:2608.05110v1 [quant-ph] 5 Aug 2026

University of Innsbruck, Department of Theoretical Physics, Technikerstraße 21a, A-6020 Innsbruck, Austria. Near-term quantum hardware limits circuit depth and often imposes geometrically local connectivity for quantum generative models, restricting the output distributions accessible to shallow unitary Born models. Introducing stochasticity into a unitary quantum Born model can improve the empirical generative performance of the resulting channel model and, for a restricted small-scale architecture, has been proven to represent a strictly larger family of distributions than its unitary counterpart. However, whether such randomness provides a provable separation at fixed shallow depth for arbitrarily large systems has remained open. Here, we show that shared classical randomness, a comparatively weak resource from entanglement theory, is sufficient to establish such a strict scalable representational separation over the corresponding shallow unitary Born model. More specifically, we augment bounded-connectivity shallow unitary circuits, followed by computational-basis measurements, with spatially separated local Pauli operations, whose joint application is controlled by a single classically sampled random bit. The resulting shallow-depth channel model generates longrange correlations in the classical output distribution that no purely unitary shallow-depth model with bounded connectivity can reproduce. For one-dimensional nearest-neighbour architectures, reproducing such distributions with a purely unitary model can require depth Ω(N ) in the worst case. We further show that measurement-based quantum computation (MBQC) provides a natural implementation of the required shared classical randomness through suitable adaptation of the random measurement outcomes. Numerical experiments on MBQC-based generative models support the analytical results.

I.

INTRODUCTION

Quantum computers are expected to provide advantages for certain computational tasks, with canonical examples including factorization [1], unstructured search [2], and sampling problems [3]. In the near-term setting, these prospects motivate variational quantum models [4], whose performance is constrained by realistic architectural resources such as connectivity, circuit depth, and measurement access [5]. Among the variational quantum models, quantum generative models use a parameterized quantum circuit followed by a measurement to obtain a probability distribution over bit strings through Born’s rule [6, 7]. They are particularly promising because sampling from such distributions is known to be classically hard in general [8, 9]. However, the expressivity or representational power of these Born models, in terms of the family of distributions they can generate, is tied not only to the Hilbert-space dimension, but also to the aforementioned architectural restrictions of the underlying circuit, including depth, connectivity, and available measurement operations. Combining limited circuit depth with local connectivity restricts the propagation of information to a finite spatial range, preventing shallow circuits from establishing correlations between sufficiently distant qubits. Dynamic quantum circuits can overcome this limitation by using mid-circuit measurements and classically controlled

∗ arunava.majumder@uibk.ac.at

feedforward operations to establish long-range correlations [10–13]. Although powerful, these operations introduce additional experimental overhead: mid-circuit measurements are susceptible to measurement errors, while classical processing and communication can increase execution latency. Several other approaches have explored stochastic or channel-based extensions of variational quantum models [14–17]. In particular, Refs. [14, 15] introduce classical randomness into the unitary model by classically processing the intrinsically random measurement outcomes of measurement-based quantum computation (MBQC). Separately, Ref. [14] proved that, for a restricted smallscale architecture, introducing this classical randomness yields a channel model that generates a strictly larger family of output distributions than the corresponding unitary model. However, whether such randomness establishes a strict scalable representational or expressivity advantage over a pure unitary Born model at shallow depth remains open. This motivates the central question of this work: Can the family of output distributions generated by shallow local quantum circuits be strictly enlarged without introducing additional quantum resources in the form of circuit depth, long-range entangling gates, or adaptive mid-circuit measurements and feedforward? In this work, we show that shared classical randomness, a standard resource in entanglement theory [18, 19], is sufficient to establish a strict representational separation at shallow depth on any bounded-degree local architecture. We further allow the shared randomness to be tunable, making the resulting model suitable for gen-

2 erative learning tasks. As illustrated in Fig. 1, a deep local circuit [Fig. 1(a)] can build correlations between distant qubits, whereas a shallow local circuit [Fig. 1(b)] cannot do so under the same connectivity constraints. Our construction [Fig. 1(c)] keeps the circuit shallow, but augments it at an intermediate layer with tunable shared randomness in the form of a stochastic Pauli string whose support includes spatially separated qubits. The additional resource is therefore not a long-range quantum gate, but a shared classical random variable that determines in advance whether local Pauli gates will be applied simultaneously in distant regions of the circuit. Averaging over the random choices defines a stochastic channel model that can generate long-range correlations in its classical output distribution that the corresponding unitary model cannot reproduce at shallow depth, thereby establishing a strict separation between the two model families. In a one-dimensional nearest-neighbour architecture, reproducing these correlations with a purely unitary model requires a depth that grows linearly with the distance between the relevant regions. More generally, on any bounded degree local architecture, the required unitary depth is governed by the graph distance between these regions. In measurement-based quantum computation (MBQC), the measurement outcomes are inherently random, and suitable adaptation or retention of selected outcomes can naturally realize channel models with shared randomness without requiring extra resources.

Our results should not be interpreted as establishing a quantum computational advantage over classical methods. Rather, they establish a representational separation between two classes of quantum generative models subject to the same shallow, local quantum-resource constraints. One of these classes is given by standard shallow unitary Born machines with restricted connectivity. The only additional resource of the other class is shared classical randomness, used to coordinate Pauli operations on separated qubits. Thus, shared classical randomness alone can strictly enlarge the family of output distributions accessible to shallow, local quantum generative models without requiring additional quantum depth.

This manuscript is organized as follows. In Sec. II A 1, we introduce quantum generative modeling within the QCBM framework. In Secs. II A 2 and II A 3, we define the local unitary model and its shared-randomness channel extension, respectively. Section II C presents an MBQC realization of the shared-randomness channel, and Sec. II B introduces the corresponding MBQC-based graph generative model. In Sec. III A, we present our analytical and numerical results. Section VII discusses related work. Finally, in the Supplementary Material, Appendices A-E, we provide detailed proofs and supporting calculations for the results established in Sec. III A.

II. A.

METHODS

Quantum generative modeling with shared randomness 1.

Generative modelling

Generative learning is an unsupervised learning task that aims to model the probability distribution underlying a given data set. Generative models are commonly classified as explicit, when they provide a tractable expression for the model distribution PU (θ) , or implicit, when they specify only a stochastic procedure for generating samples, x ∼ PU (θ) [20]. We focus on implicit generative models. The training data consist of M independent and identically distributed samples D = {x1 , . . . , xM }, where each xk ∈ {0, 1}N is a bit string drawn from an unknown target distribution Y (x). The goal is to optimize the model parameters θ such that the resulting distribution PU (θ⋆ ) (x) approximates Y (x) to a desired accuracy, as illustrated in Fig. 2. Classical generative models typically use neural networks with trainable weights to approximate a target distribution. In a quantum circuit Born machine (QCBM), a class of quantum generative models, the neural network is replaced by a parametrized quantum circuit composed of trainable single- and multi-qubit gates. Starting from a fixed input state |ψ⟩, the circuit prepares the parametrized state U (θ)|ψ⟩, which is measured in the computational basis to generate samples according to the 2 Born rule, PU (θ) (x) = |⟨x|U (θ)|ψ⟩| . Each circuit execution produces one bit-string sample x, and repeated executions provide the samples required to estimate a suitable loss function and optimize the model parameters. A key feature of QCBMs is that they generate samples directly from the model distribution without requiring its explicit evaluation. The models studied in this paper follow the same sampling and optimization procedure shown in Fig. 2.

2.

Generic brickwall unitary circuit

We consider a shallow one-dimensional local quantum circuit on N qubits, composed of D layers U (θ) = UD (θD ) · · · U1 (θ1 ),

(1)

θ = {θk }D k=1

(2)

where

and θk denotes the set of trainable parameters in layer k. For our purposes, we restrict to one-dimensional nearestneighbor brickwall circuits in which each gate acts on at most two adjacent qubits. Such a circuit consists of alternating sub-layers of parametrized two-qubit gates acting on disjoint even and odd nearest-neighbor bonds (see

3 (b) Shallow circuit

(a) Deep circuit 𝑈(𝜃! ) 𝑈(𝜃$ )

|𝜓⟩

⟨𝑍&! ⟩

𝑈(𝜃& )

𝑈(𝜃# )

𝑃!+

⟨𝑍&! ⟩

𝑈(𝜃! ) 𝑈(𝜃$ )

𝑈(𝜃# )

|𝜓⟩

|𝜓⟩

𝑈(𝜃# )

𝑈(𝜃% )

𝑈(𝜃!* ) 𝑈(𝜃' )

𝑈(𝜃" )

𝑠 ∼ 𝐵𝑒𝑟𝑛𝑜𝑢𝑙𝑙𝑖(𝑝)

𝑈(𝜃$ )

𝑈(𝜃( ) 𝑈(𝜃% )

⟨𝑍&! ⟩

𝑈(𝜃! )

𝑈(𝜃) )

(c) Shallow circuit with shared randomness

𝑈(𝜃" )

⟨𝑍&" ⟩

𝑈(𝜃% )

⟨𝑍&" ⟩ 𝑃&+

Covariance: Cov 𝑍%! , 𝑍%" = 𝑍%! 𝑍%" − 𝑍%! 𝑍%" ≠ 0

Covariance: Cov 𝑍%! , 𝑍%" =0

𝑈(𝜃" )

Implements:

0 𝑃!" = 𝑃#" ⊗ 𝑃$" ; 𝑃 ∈ {𝑋, 𝑍}

⟨𝑍&" ⟩ Covariance: Cov 𝑍%! , 𝑍%" ≠ 0

FIG. 1. Long-range correlations from shared classical randomness: For illustration, the figure shows a brickwall-type circuit on N = 6 qubits acting on an input state |ψ⟩, although the mechanism applies to any system size N ≥ 6. The shaded regions denote the backward light cones of the measured observables Ẑ1 and Ẑ6 . (a) In a sufficiently deep (linear depth) local circuit, the two light cones overlap, allowing the circuit to generate a nonzero correlation, Cov(Ẑ1 , Ẑ6 ) = ⟨Ẑ1 Ẑ6 ⟩−⟨Ẑ1 ⟩⟨Ẑ6 ⟩ ̸= 0. (b) For a shallow local circuit, the light cones remain disjoint. For a product input state, the corresponding expectation values factorize, and hence Cov(Ẑ1 , Ẑ6 ) = 0 for all model parameters. (c) The same shallow circuit is augmented by one shared classical random bit s ∈ {0, 1} sampled from a Bernoulli distribution, which controls local Pauli operations on the two distant s = P1s ⊗ P6s , with Pq ∈ {X, Z}, Pq0 = I, and q ∈ {1, 6}. The input state |ψ⟩ qubits and implements the stochastic string PM is chosen such that PM |ψ⟩ is not proportional to |ψ⟩, ensuring that the Pauli string cannot be absorbed into the input state. Although no long-range quantum gate is introduced in (c), the shared random variable correlates the local responses and can produce Cov(Ẑ1 , Ẑ6 ) ̸= 0 for suitable model parameters. Thus, shared classical randomness enables correlations that a purely unitary local circuit cannot generate at the same shallow depth.

Fig. 1). For example, one brickwall layer may be written as (k)

(k)

(k) (k) Uk (θk ) = Uodd (θodd )Ueven (θeven ),

(3)

output state in the computational basis therefore produces the distribution   PU (θ) (x) = Tr |x⟩⟨x|U (θ)ρin U (θ)† , x ∈ {0, 1}N (6)

where (k) Ueven =

N −1 Y

(k)

(k)

(k)

Gi,i+1 (θi,i+1 ), Uodd =

i=2 i even (k) and Gi,i+1

N −1 Y

3. (k)

Generic brickwall channel circuit

(k)

Gi,i+1 (θi,i+1 ).

i=1 i odd

(4) are parametrized two-qubit gates acting on

We now augment the unitary brickwall circuit with correlated stochastic Pauli operations. Let PM be a Pauli string with

(k)

qubits (i, i + 1) with θi,i+1 ∈ R. Within each sub-layer, the gates act on disjoint pairs and can be applied in parallel. Between the even and odd sub-layers, the gates generally do not commute, so their ordering is part of the circuit definition. Single-qubit rotations can also be included in the generic parametrized two-qubit gates. Throughout this paper, for the generic brickwall circuit we consider a fixed product input state ρin =

N O

ρj ,

(5)

PM =

N O

Qj ,

(7)

j=1

where M ⊆ [1, N ] := {1, . . . , N } denotes the support of the Pauli string, Qj ∈ {X, Z} for j ∈ M, and Qj = I for j∈ / M. A single classical Bernoulli variable s ∈ {0, 1} determines whether the entire Pauli string is applied, such that 0 PM = I,

1 PM = PM .

(8)

j=1

where each ρj is an arbitrary single-qubit state. For a unitary model U (θ) as in Eq. (1), measurement of the

Thus, all local Pauli operators supported on M are controlled by the same random variable s, producing a spatially correlated stochastic Pauli operation.

4 Quantum Circuit Born Machine (QCBM)

The construction extends directly to multiple stochastic Pauli strings inserted at different positions within the circuit. Let {PMi }L i=1 be a set of L Pauli strings, where Mi ⊆ [1, N ]. Each Pauli string PMi is controlled by a Bernoulli variable si ∈ {0, 1} with

𝑌(𝑥)

(a)

𝑥 ∼ 𝑌(𝑥)

Pr(si = 1) = pi ,

Target distribution Learning model (b)

|𝜓⟩ /

!

𝑈(𝜃)

ters

𝜃#$% arame

dp ate Upd

minimize

i

MMD( 𝑌, 𝑃!(#) )

𝑥 ∼ 𝑃! 𝜽 𝑥 → Sampling from Born distribution: 𝑃! " 𝑥 = 𝑥 𝑈 𝜃 𝜓 #

FIG. 2. Quantum circuit Born machines for quantum generative modeling: (a) Target distribution Y (x) (usually unknown), from which samples are given, x ∼ Y . (b) The learning model applies a parametrized quantum circuit U (θ) to a fixed input state |ψ⟩ and measures the resulting state in the computational basis. Each circuit execution produces a bit string sampled from the Born distribution x ∼ PU (θ) . Samples from the target and model distributions are used to evaluate the maximum mean discrepancy (MMD) loss between Y and PU (θ) . Gradients are estimated using the parameter-shift rule, after which a classical optimizer updates θ 7→ θnew . The updated parameters are returned to the quantum circuit, and the procedure is repeated until the loss converges.

Pr(si = 0) = 1 − pi ,

(13)

We assume that the variables {si }L i=1

where p ∈ [0, 1]. are mutually independent and denote the corresponding application probabilities by the set p = {pi }L i=1 . Although the variables controlling different strings are insi dependent, each individual string PM represents a cori related operation because the same variable si controls all Pauli operators supported on Mi . Each Pauli string PMi , with i ∈ {1, . . . , L}, is assigned to an intermediate layer denoted by an insertion slot li ∈ {1, . . . , D − 1}. The assignment {li }L i=1 is fixed as part of the circuit architecture. Different Pauli strings may be assigned to different slots, multiple Pauli strings may share the same slot, and some slots may contain no Pauli strings. Having several Pauli strings for the same slot allows to more directly accommodate correlations in which non-overlapping subsets of qubits are correlated within the same subset, but not across the subsets. For a branch s = (s1 , . . . , sL ) ∈ {0, 1}L and fixed assignments {li }L i=1 , define Y si Bl (s) := PM , l ∈ {1, . . . , D − 1}. (14) i 1≤i≤L, li =l

Consider an insertion slot l ∈ {1, . . . , D − 1} between the circuit layers Ul (θl ) and Ul+1 (θl+1 ). The unitary associated with branch s is defined as s U (s) (θ) := UD (θD ) · · · Ul+1 (θl+1 )PM Ul (θl ) · · · U1 (θ1 ). (9) The Pauli string is applied with probability Pr(s = 1) = p, where p ∈ [0, 1], and is omitted with probability Pr(s = 0) = 1 − p. Equivalently,

Pr(s) = ps (1 − p)1−s .

(10)

We refer to p as the application probability. The values p = 0 and p = 1 correspond to deterministic unitaries which we refer to as branches depending on s ∈ {0, 1}, whereas p ∈ (0, 1) defines a nontrivial stochastic channel. The resulting channel model Eθ,p (ρin ), acting on the input state ρin becomes X Eθ,p (ρin ) = Pr(s) U (s) (θ)ρin U (s) (θ)† , (11)

When iterating over 1 ≤ i ≤ L, the condition li = l selects precisely those Pauli strings whose assigned insertion slot is l in the circuit definition, that is, those inserted between Ul and Ul+1 . Thus, Bl (s) is the product of all Pauli strings assigned to the insertion slot between Ul and Ul+1 . The product is taken in a fixed order, and Bl (s) = I if no Pauli string is assigned to slot l. The branch s dependent unitary is U (s) (θ) = UD (θD )BD−1 (s)UD−1 (θD−1 ) · · · B1 (s)U1 (θ1 ). (15) and the probability of branch s being realized is L Y

i si

i 1−si

L Y

πpi (si ).

(16)

The induced channel model can be written as X Eθ,p (ρin ) = πp (s) U (s) (θ)ρin U (s) (θ)† .

(17)

πp (s) =

(p ) (1 − p )

i=1

=

i=1

s∈{0,1}L

s∈{0,1}

where U (0) (θ) denotes the branch without any correlated Pauli gates. Measuring the channel output in the computational basis gives the distribution h i X PEθ,p (x) = Pr(s) Tr |x⟩⟨x|U (s) (θ)ρin U (s) (θ)† ] s∈{0,1}

(12)

and the corresponding Born distribution is h i X PEθ,p (x) = πp (s) Tr |x⟩⟨x| U (s) (θ)ρin U (s) (θ)† . s∈{0,1}L

(18) where θ = {θl }D with θ containing the set of paramel l=1 ters for layer l, and p = {pi }L i=1 contains the probabilities with which the correlated Paulis are applied.

5 Here, Rx and Rz are single-qubit Pauli-rotations, while Rzz is a two-qubit entangling Pauli-rotation acting on nearest-neighbor qubits, and the k th layer parameters are   k,z N k,zz N −1 θk = {θik,x }N . (22) i=1 , {θi }i=1 , {θi,i+1 }i=1

Learning model

𝑅! (𝜃"%,! )

𝑅( (𝜃"%,( )

𝑅! (𝜃$%,! )

𝑅( (𝜃$%,( )

𝑅! (𝜃'%,! )

𝑅( (𝜃'%,( )

For an insertion slot after layer l ∈ [1, D − 1], write …… Repeats

𝑅! (𝜃)%,! )

U (θ) = U>l (θ)U≤l (θ).

(23)

where U≤l (θ) contains all circuit layers up to layer l, while U>l (θ) contains the subsequent layers. A shared bit sl ∈ {0, 1} is sampled according to Pr(sl = 1) = pl , and the stochastic Pauli string O l sl ZM := Zjs , M ⊆ [1, N ], (24)

!

" 𝑍!

……

%, !! 𝑅!! (𝜃)+",) )

Input state

%, !! 𝑅!! (𝜃$,' )

𝛼

⊗"

%, !! 𝑅!! (𝜃',* )

……

%, !! 𝑅!! (𝜃",$ )

𝑠 % ∼ 𝐵𝑒𝑟𝑛𝑜𝑢𝑙𝑙𝑖(𝑝% )

𝑅( (𝜃)%,( )

j∈M

𝑈#

𝑈#$%

is inserted at this slot, between layer l and l +1, as shown in Fig. 3. The branch unitary becomes

FIG. 3. Learning model with shared randomness: A depth-D one-dimensional nearest-neighbor circuit acts on the product input state |α⟩⊗N . Each parametrized layer Ul (θl ) consists of nearest-neighbor Rzz rotations followed by local Rz and Rx rotations. Between layers Ul and Ul+1 , a shared classical bit sl ∼ Bernoulli(pl ) allows the stochastic Pauli string sl to act on a subset M ⊆ [1, N ] of qubits, such that the loZM cal Z operations are either applied jointly or all omitted. Repeating the layer structure generates the full depth-D learning model while the Pauli string shown here is inserted only at the designated slot l.

l

l

s U (s ) (θ) = U>l (θ)ZM U≤l (θ).

(25)

The resulting channel is Eθ,pl (ρin ) = (1 − pl ) U (0) (θ)ρin U (0) (θ)† + pl U (1) (θ)ρin U (1) (θ)† ,

(26)

and computational-basis measurements give, as output probability,   (27) PEθ,pl (x) = Tr |x⟩⟨x| Eθ,pl (ρin ) . We also use a fixed product input state

Definition 1 (Minimal correlated channel model). The minimal correlated channel model is obtained by inserting s at an intermediate a single stochastic Pauli string PM layer l of the local quantum circuit defined in Eq. (9), where the support M contains two distinct sites a, b ∈ M, s = Pas ⊗ Pbs with Pq ∈ {X, Z}, Pq0 = I, and i.e., PM q ∈ {a, b}. The resulting channel, for an input state ρin is Eθ,p (ρin ) =(1 − p)U (0) (θ)ρin U (0) (θ)† + pU (1) (θ)ρin U (1) (θ)†

(19)

where U (s) (θ) with s ∈ {0, 1} follows from Eq. (9). B.

Learning model

As an explicit learning model, we consider a depthD one-dimensional nearest-neighbor circuit on N qubits with open boundary conditions as in Eq. (1), where each layer k ∈ [1, D] in the circuit can be written as Uk (θk ) =

N O

Rx (θik,x )

i=1

N O i=1

Rz (θik,z )

N −1 Y

k,zz Rzz (θi,i+1 )

i=1

(20) as shown in Fig. 3 with Rx (θ) = e−iθX/2 , Rz (θ) = e−iθZ/2 , Rzz (θ) = e−iθZ⊗Z/2 . (21)

ρin =

N O

Rx (α)|0⟩⟨0|Rx (α)† ,

(28)

j=1

with a fixed angle α ∈ / π2 Z. For our numerical simulations, we explicitly set α = π4 . Propagating the inserted Pauli string through U>l (θ) leaves commuting Pauli rotations unchanged while flipping the signs of the angles of anti-commuting rotations, as illustrated in Sec. D (also see Fig. 9) in the appendix. The choice of a correlated Pauli-Z string ensures that the shared randomness is encoded entirely in correlated sign flips of the non-Clifford angles of Rx gates. These branch-dependent angle flips modify the circuit dynamics and hence the output distribution non-trivially, while the remaining propagated Z-string is diagonal in the computational basis and does not alter the final measured bit string. More generally, correlated Pauli-X or mixed Pauli strings may also be considered, although their direct action on computational-basis outcomes must then be taken into account. Later, we show in Sec. II C 4 that any resulting non-Z Pauli string at the circuit output can be corrected, leaving the branch-dependent intermediate angle flips as the effective action of the stochastic Pauli string. The learning model defined in Eq. (26) is used in the numerical analysis in Sec. III C. We note, however, that the analytical results presented in Sec. III A do not depend on this specific architecture and can be extended to more general finite-range local architectures.

6 C.

Native correlated channel models in variational measurement-based quantum computation

we take Tc = H ⊗N

1.

Introduction to variational measurement-based quantum computation

Here we describe how shared classical randomness, represented by a stochastic Pauli string, or correlated stochastic Pauli operations, can be realized natively within the MBQC framework. In MBQC, universal quantum computation is performed through adaptive singlequbit measurements on an entangled resource state [21, 22]. To illustrate this mechanism, we use the standard cluster state, prepared by initializing qubits in the state |+⟩ on a rectangular lattice and applying nearestneighbor controlled-Z gates. The construction is not restricted to cluster states: other graph states supporting MBQC can likewise realize unitary circuits augmented with shared randomness. In the left panels of Fig. 4 (a,b), we consider a cluster state of size N × (D + 1) = 4 × 3 with open boundary conditions, so that boundary qubits are not connected along the spatial direction. The first D columns are measured in the XY plane, while the final column forms the output layer and is measured in the computational Z basis. We label the measured qubits by (l, j), where l ∈ [1, D] is the layer index and j ∈ [1, N ] is the spatial index. The measurement on qubit j in layer l is performed in the basis  l 1  |±θjl ⟩ = √ |0⟩ ± e−iθj |1⟩ , 2

(29)

N −1 Y

CZj,j+1 .

(30)

Rz (θjl ) := exp −iθjl Zj /2 ,

(31)

j=1

and using the convention

the circuit branch corresponding to measurement outcomes s = {slj }j,l can be written as   N Y Y l
s Tc U (s) (θ) = Zj j exp −iθjl Zj /2  , (32) j=1

l=D,...,1

where slj = 0 corresponds to the +1 measurement outcome and slj = 1 to the −1 outcome. This binary variable sl

slj ∈ {0, 1} decides whether a byproduct Zj j should appear at position (l, j) in the circuit picture (Fig. 4). The Eq. (32) gives rise to a variational model of MBQC, called variational MBQC (VMBQC) [14]. While standard MBQC always corrects byproducts, Refs. [14, 15] allow for probabilistic correction of these byproducts to elevate the unitary VMBQC to a channel model. Let clj ∈ {0, 1} denote the correction decision, with clj = 1 meaning that the byproduct is corrected and clj = 0 meaning that it is retained or not corrected. Assuming that clj is sampled independently of the measurement outcome slj , with Pr(clj = 1) = plj ,

(33)

then the retained byproduct bit is where θjl

determines the corresponding gate in the induced circuit model [23]. An individual measurement in this basis gives either outcome +1 or −1, each with probability 1/2. The +1 outcome implements the intended operation, while the −1 outcome introduces an additional Pauli-Z byproduct, since |−θ ⟩⟨−θ | = Z|+θ ⟩⟨+θ |Z. In standard MBQC, these measurement-induced byproducts are compensated by adapting subsequent measurement angles according to earlier measurement outcomes. A classical controller records the outcomes, determines the resulting byproduct operators, and updates later measurement bases through feedforward. This procedure is applied throughout the resource state, and the final readout is interpreted accordingly, so that the implemented logical transformation is independent of the stochastic measurement outcomes [14]. For the cluster state considered here, MBQC with XY plane measurements admits an equivalent circuit representation (see Fig. 4) consisting of trainable Z-axis rotations, stochastic Pauli-Z byproducts, and a fixed Clifford layer Tc defining a Clifford quantum cellular automaton (CQCA) [14, 15, 24]. With open boundary conditions,

selj = (1 − clj )slj .

(34)

Since measurement outcomes are random and satisfy Pr(slj = 1) = 1/2, the retained byproduct probability is Pr(e slj = 1) =

1 1 (1 − plj ) ≤ . 2 2

This gives rise to a family of quantum channels X E(θ,p) [ρ] = p(e s) U (es) (θ) ρ U (es) (θ)† ,

(35)

(36)

e∈{0,1}N ×D s

where ρ = (|+⟩⟨+|)⊗N is the input state. As the byproducts are independent of each other, the branch probabil  s̃l Q Q 1+(−1) j plj l ity factorizes as p(s̃) = l,j p(s̃j ) = l,j , 2 with s̃ being an N × D binary matrix with entries s̃ji ∈ {0, 1}, and pji is the trainable correction probability for the qubit at (i, j)-location. In VMBQC, this channel character arises natively from random measurementinduced byproducts, whose retention or correction is governed entirely by classical processing and feedforward of the measurement outcomes [14].

7 While it was shown in Refs. [14] that the trainable correction probability can give rise to models that are more expressive than the unitary model (even in a very restricted setting [15]), it has a rather strong shortcoming: this correction-only mechanism can suppress naturally occurring byproducts but cannot make any retained byproduct occur with probability greater than 1/2. In the present work, we allow more general classical control. In addition to deciding whether to retain a measurement-induced byproduct when slj = 1, the controller may deliberately introduce the same effective byproduct when slj = 0 through an appropriate modification of the subsequent feedforward rules. This allows the effective byproduct probability Pr(slj = 1) to vary over the full interval [0, 1]. Moreover, a single classical controller can use the same sampled variable to apply a correlated Pauli byproduct string simultaneously to several spatially separated qubits. We illustrate these constructions using Fig. 4. The next Sec. II C 2 introduces how one can deliberately add byproducts independently to individual qubits. Then, in Sec. II C 3, we show the construction of shared randomness in the form of correlated byproducts on a subset of qubits similar to Eq. (17) but implemented in VMBQC natively.

2.

Independent randomness from effective classical control

We first describe the independent-randomness version of the construction within the MBQC framework. For each measured qubit (l, j), introduce an effective classical control variable clj ∈ {−1, +1}. Note that the range of this variable here is different from the variable clj ∈ {0, 1} introduced in Sec. II C 1. After obtaining the raw measurement outcome on qubit (l, j), the choice clj = +1 corrects the effective measurement-induced byproduct, whereas clj = −1 produces the corresponding Pauli Zbyproduct. The latter may equivalently be interpreted as an anti-correction, implemented by modifying the subsequent measurement angles if there is no measurementinduced byproduct. Thus, anti-correction can be viewed as the same operation as correction that treats s = 0 as the “incorrect” measurement outcome. Now, we define the effective byproduct bit slj :=

1 − clj . 2

(37)

(a)

s!! ∼ 𝐵𝑒𝑟𝑛𝑜𝑢𝑙𝑙𝑖(𝑝!! )

|+⟩

H

"!

𝑍!!

|+⟩

H

|+⟩

H

T! "!

|+⟩

𝑍#"

H

s"! ∼ 𝐵𝑒𝑟𝑛𝑜𝑢𝑙𝑙𝑖(𝑝"! )

/

|+!" ⟩⟨+!" | !

!

(b)

"#$

"#$

𝑅" (𝜃#$ ) - gate

|−$$ ⟩⟨−$$ | = 𝑍% |+$$ ⟩⟨+$$ |𝑍% #

#

#

#

𝑠! ∼ 𝐵𝑒𝑟𝑛𝑜𝑢𝑙𝑙𝑖(𝑝! )

|+⟩

𝑍!"

H

|+⟩

H

|+⟩

H

T!

|+⟩

𝑍#"

!

H

$

|−$$ ⟩⟨−$$ | = 𝑍%" |+$$ ⟩⟨+$$ |𝑍%"

|+!" ⟩⟨+!" | !

!

#

!

#

#

#

$

𝑅" (𝜃#$ ) - gate

FIG. 4. Independent and shared randomness within MBQC: For illustration, we consider a 4 × 3 cluster state, where the first two columns are measured in the XY plane, and the final column forms the readout layer. The corresponding circuit representation contains parametrized Rz (θjl ) rotations, nearest-neighbor CZ gates, and Hadamard gates. The colored boundary qubits indicate measurement-induced Z byproducts that are either corrected by feedforward or deliberately added through anti-correction, all other qubits are corrected with unit probability. (a) The two boundary qubits are corrected or anti-corrected independently. The corresponding circuit therefore contains independent byprods1

s1

ucts Z1 1 and Z4 4 , controlled by independent Bernoulli variables s11 ∼ Bernoulli(p11 ) and s14 ∼ Bernoulli(p14 ), respectively, where slj = 0 denotes correction, slj = 1 denotes anticorrection of measurement-induced byproduct on qubit j at layer l, and Pr(slj = 1) = plj ∈ [0, 1] as in Eq. (39). (b) The feedforward rule is chosen in a way so that the two boundary qubits (blue) are corrected or anti-corrected jointly. Their retained byproducts are therefore controlled by a single shared binary variable s1 ∼ Bernoulli(p1 ) (Eq. (45)), yielding the 1 1 stochastic Pauli string Z1s ⊗ Z4s in the equivalent circuit on the right.

Thus slj = 0 for clj = +1 and slj = 1 for clj = −1. Choosing Pr(clj = −1) = plj ,

Pr(clj = +1) = 1 − plj ,

Operationally, the induced circuit applies the Pauli (38)

is equivalent, in the induced circuit model of Fig. 4 (a) (right), to treating slj as a Bernoulli variable with tunable probability slj ∼ Bernoulli(plj ), Pr(slj = 1) = plj , Pr(slj = 0) = 1−plj . (39)

sl

byproduct Zj j with probability plj . Unlike the correctiononly mechanism described above in Eq. (36), this effective control scheme allows Pr(slj = 1) to range over the full interval [0, 1]. For the example in Fig. 4 (a), we use two independent s1

classical variables controlling the two byproducts Z1 1 and

8 s1

Z4 4 in the circuit, with s11 ∼ Bernoulli(p11 ),

s14 ∼ Bernoulli(p14 ).

(40)

These two effective byproduct bits are sampled independently. The corresponding branch circuit is   4 Y
U (s) (θ) = Tc exp −iθj2 Zj /2  . (41) j=1

 Tc



s1 s1 Z1 1 ⊗ Z 4 4

4 Y

 exp −iθj1 Zj /2  ,

(42)

j=1

where s = (s11 , s14 ). Making the probabilities p11 and p14 trainable gives the channel family X Pr(s11 ) Pr(s14 ) U (s) (θ) ρ U (s) (θ)† . E(θ,p) [ρ] = s11 ,s14 ∈{0,1}

(43) l

l

where Pr(slj ) = (plj )sj (1 − plj )1−sj with slj ∈ {0, 1} as shown in Eq. (39). This effective classical control can be incorporated directly into the standard MBQC feedforward procedure. For the unbiased measurement outcomes considered here, a measurement-induced byproduct occurs with probability 1/2, and deterministic MBQC corrects it through feedforward. The anticorrection scheme instead modifies the same classical control rule to retain (when slj = 1) or deliberately introduce (when slj = 0) the corresponding byproduct, allowing the effective byproduct probability to span the full interval [0, 1]. Since this uses the existing measurement record and feedforward mechanism, it does not increase the average classical-processing overhead relative to deterministic MBQC.

3.

Shared randomness

The previous section described how independent randomness can be generated in MBQC through independently controlled byproducts. We now show how the same feedforward mechanism can realize shared randomness across spatially separated qubits in the cluster-state computation and, equivalently, in the induced circuit model. Consider the cluster-state computation with D computational layers, as described in Eq. (32). After the qubits in layer l are measured, their outcomes are recorded, and these raw measurement outcomes are independent. Classical feedforward can process them so that several qubits share the same effective byproduct bit sl ∈ {0, 1}. This shared bit controls the collective Pauli byproduct N l sl ZM := j∈M Zjs which acts simultaneously on a subset M ⊆ [1, N ] of qubits. Thus, when sl = 1, a Zbyproduct is retained on every qubit in M, whereas

all other measurement-induced byproducts are corrected. As in Sec. II C 2, we define the effective control variable cl with Pr(cl = −1) = pl ,

Pr(cl = +1) = 1 − pl ,

(44)

such that the shared bit sl is sampled according to sl ∼ Bernoulli(pl ), Pr(sl = 1) = pl , Pr(sl = 0) = 1 − pl . (45) As in Sec. II C 2, the probability pl can be treated as a tunable parameter in the interval [0, 1]. As an example, consider the cluster-state construction shown in the left panel of Fig. 4 (b). We choose Ml = {1, 4} and use the same control variable c1 for the boundary qubits (1, 1) and (1, 4). The resulting effec1 1 tive byproducts are therefore Z1s and Z4s , which always appear or disappear together depending on s1 ∈ {0, 1}. For the corresponding induced circuit shown in the right panel of Fig. 4 (b), the branch unitary is   4 Y
1 U (s ) (θ) = Tc exp −iθj2 Zj /2  . (46) j=1

 

1

1

Tc Z1s ⊗ Z4s

4 Y


exp −iθj1 Zj /2  . (47)

j=1

and the associated correlated channel is X 1 1 E(θ,p1 ) [ρ] = Pr(s1 ) U (s ) (θ) ρ U (s ) (θ)† ,

(48)

s1 ∈{0,1}

where 1

1

Pr(s1 ) = (p1 )s (1 − p1 )1−s .

(49)

The key difference here, from Eq. (43), is that the two endpoint byproducts are not controlled by independently sampled bits. Instead, the same bit s1 controls both byproducts, thereby producing shared randomness in the form of classically correlated byproducts across the two distant qubits. Thus, the example in Fig. 4 (b) realizes the model in Def. 1. Moreover, this MBQC construction gives a concrete realization of the general stochastic correlated model in Eq. (17). More generally, for L correlated byproduct l strings {PMl }L l=1 , the shared binary variable s controls the insertion of the string Y l sl PM = Zjs , Ml ⊆ [1, N ], (50) l j∈Ml

at a specified layer l in the induced circuit. Assigning each PMl to an intermediate insertion slot l ∈ {1, · · · , D − 1} gives a generic branch unitary as in Eq. (15). If different shared binary variables are sampled independently, with s = (s1 , . . . , sL ) ∈ {0, 1}L , then the branch probability is πp (s) =

L Y l l (pl )s (1 − pl )1−s . l=1

(51)

9 Substituting these branch unitaries from MBQC along with the branch probabilities into Eq. (17) gives the correlated quantum channel, and Eq. (18) gives its induced Born distribution. Although the variables {s1 , . . . , sL } controlling different Pauli strings are independent, the Pauli operators within each string are correlated because they are controlled by the same bit sl . Note that the stochastic Pauli string is not an additional coherent quantum gate. In MBQC, it arises natively from classical processing of random measurement outcomes. This channel character of the model is therefore generated entirely classically.

can therefore modify the output distribution nontrivially. Following Refs. [14, 15], we remove the final propagated Pauli byproduct and retain only the stochastic angle-flip effect in the learning model. The quantum circuit shown in Eq. (20) along with the channel model with stochastic Pauli string in Eq. (26) can be implemented using MBQC, which is illustrated in Appendix D. This model is also used for the numerical experiments in Sec. III C. The analytical results, however, do not depend on this specific architecture and extend to other finite-range local circuit architectures. D.

4.

End point Pauli-correction

Here, we first recall the final Pauli-correction step used in the variational measurement-based quantum computation (VMBQC) channel model Ẽc (θ, p) introduced in Ref. [14]. In MBQC, measurement-induced Pauli byproducts, s1 s1 such as Z1 1 and Z4 4 in Fig. 4, can be propagated through the remaining cluster state using stabilizer relations. In the equivalent circuit representation, conjugation by Clifford layers maps Pauli operators to Pauli operators. For example, under open boundary conditions, Tc Xi Tc† = Xi−1 Zi Xi+1 , if i ∈ [2, N − 1]. By contrast, propagating a Pauli operator through a nonClifford Pauli rotation can change the sign of the rotation angle, for instance, X s Rz (θ) = Rz ((−1)s θ)X s . We refer the readers to Ref. [24] for the detailed propagation rules. After propagation through all subsequent layers, the byproducts accumulate into a final Pauli string. For example, for the independent-byproduct construction in Fig. 4 (a), the final accumulated byproduct is s1

s1

s1

s1

P̂ (s) = Z1 1 ⊗ X2 1 ⊗ X3 4 ⊗ Z4 4 . This final Pauli string can be removed by appending an outcome-dependent correction layer P̂D+1 (s̃) = P̂ (s)† that cancels P̂ (s) before the final measurement. For computational-basis measurements, this is equivalent to classical post-processing of the output bit string. This removes the propagated Pauli byproduct while retaining the branch-dependent intermediate angle flips generated during its propagation. A similar endpoint-correction procedure applies to the parametrized circuits presented in Eq. (26) and shown in Fig. 3, which consists of parametrized single- and twoqubit Pauli rotations, and more generally to circuits containing parametrized multi-qubit Pauli rotations, as detailed in Sec. D (see Fig. 9) of the Appendix. This distinction is essential for the learning models below. In computational-basis measurements, the effective Pauli operator at the end of the circuit transforms the circuit output trivially: the final X and Y components of the Pauli string merely relabel the output bit string, while the final Z components leave the output probabilities unchanged. By contrast, the intermediate angle flips alter the non-Clifford rotations within the circuit and

Loss and gradients

For training, we employ the squared maximum mean discrepancy (MMD) [25] as an implicit loss function, defined below: L(θ, p) =

[K(x, y)] − 2

E

E

x∼PE(θ,p) y∼Y

x∼PE(θ,p) y∼PE(θ,p)

[K(x, y)] (52)

+ E [K(x, y)] x∼Y y∼Y

where all samples appearing in the same expectation are drawn independently. Here, PE(θ,p) is the output distribution of the channel model defined in Eq. (18), and Y (x) is the target distribution generated from the family in Def. 6. The K(x, y) in Eq. (52) is referred to as the kernel function that quantifies the similarity between samples x and y. In practice, the expectations in Eq. (52) are estimated using finite samples from the model and target distributions. When p = 0, no stochastic Pauli string is applied and the channel model reduces to the corresponding unitary model, as stated in Observation 2. During training, the circuit parameters θ and the shared application probabilities p are updated iteratively using the gradients ∂L , ∂θ

and

∂L , ∂p

(53)

for each θ ∈ θ and p ∈ p. In the single Pauli-string model, this includes the derivatives with respect to the k,zz circuit parameters θik,x , θik,z , and θi,i+1 , together with the l shared probability p . These gradients can be evaluated analytically using parameter-shift and stochastic-channel differentiation rules [6, 14]. Further details are provided in Appendix E 1. III. A.

RESULTS

Analytical results

Shallow-depth local unitary circuits have limited ability to correlate distant outputs because separated regions

10 depend only on disjoint past light cones. By contrast, the channel model with shared randomness can use a single classical random variable to apply a spatially extended Pauli string that can generate long-range output correlations without increasing the circuit depth or introducing long-range quantum gates. Observation 2 (weak inclusion of model families). Consider a fixed depth-D parameterized circuit U (θ) as in Eq. (1), with an input state ρin and computational-basis measurements. Let

that are separated by distance dist(a, b) (see Def. 3), at an intermediate layer in the circuit. Also consider Punit (D) and Pch (D) defined in Eq. (54), and (55), respectively, as the family of distributions corresponding to the unitary and channel model. Then, there exist a shallow channel model E ∗ ≡ E(θ∗ ,p∗ ) with output distribution Q⋆ := PE(θ⋆ ,p⋆ ) in the computational basis such that for all depths 1 < D0 < dist(a,b) , 4 Q∗ ∈ / Punit (D0 )

(58)

⋆

Punit (D) := {PU (θ) }θ

(54)

denote the family of output distributions generated by the unitary model, and let Pch (D) := {PEθ,p }θ,p

(55)

denote the family of distributions generated by the corresponding correlated channel model Eθ,p (ρin ) acting on input state ρin as defined in Eq. (17). If the parameter domain includes p = 0, then Punit (D) ⊆ Pch (D).

(56)

The previous observation establishes only a weak expressivity statement, i.e., adding the stochastic byproduct cannot reduce the reachable family of distributions. The central question is whether the inclusion is strict at a fixed shallow depth D, namely whether Punit (D) ⊊ Pch (D),

(57)

Theorem 4 answers this affirmatively for one-dimensional nearest-neighbor brickwall architectures. Definition 3 (Interaction-hypergraph distance). Let G = (V, E) denote the interaction hypergraph of the circuit architecture under consideration (e.g., the local circuit in Eq. (1)), where each vertex in V represents a qubit and each hyperedge e ∈ E is the support of an allowed local gate. Two qubits are adjacent if they belong to a common hyperedge. For a, b ∈ V , the distance distG (a, b) is the minimum number of hyperedges in a sequence connecting a to b.

Moreover, for a constant δ > 0 in the number of qubits N , and all such depths D0 , one can show
inf TV Q⋆ , PU (θ) ≥ δ ⋆ (59) θ

where TV(·) is the total variation distance. In particular, for dist(a, b) = Θ(N ), the corresponding unitary model requires depth D0 = Ω(N ) to represent Q∗ . Therefore, the total variation distance between Q⋆ and any distribution PU (θ) generated by the nearest-neighbor unitary circuit is lower bounded by some finite non-zero number δ ⋆ for every unitary circuit depth D0 < dist(a,b) . 4 In particular, with a = 1 and b = N , this gives a lineardepth requirement D = N 4−1 for nearest-neighbor circuit. The formal statement and proof are given in Appendix B along with the specific expression for δ ∗ . This shallow-depth separation does not rely on Pauli operators acting directly on the final measurement outcomes which can be viewed as trivial classical postprocessing. Instead, in the learning models considered here, the final byproducts are corrected or absorbed into the readout (see Sec. II C 4), while the shared randomness remains encoded in correlated intermediate nonClifford angle-flips that alter the output distribution nontrivially. The separation in Theorem 4 is not specific to the onedimensional nearest-neighbor brickwall ansatz. Corollary 5 (Separation for finite-range circuits). For any finite-range local circuit architecture, correlated stochastic Pauli operations can generate shallow-depth distributions that are not accessible to the corresponding purely unitary setup at shallow depth.

For a one-dimensional nearest-neighbor architecture with open boundary conditions, the interaction graph is the path graph on N qubits, with edges connecting qubits (j) and (j + 1). The interaction-graph distance is therefore distG (a, b) = |a − b|. In particular, the two boundary qubits 1 and N are separated by distG (1, N ) = N − 1. For brevity we write dist(a, b) := distG (a, b).

Thus the advantage persists in architectures where long-range entangling gates are not directly available which is formally stated in Corollary 16. Furthermore, the channel model with sharedrandomness used in Theorem 4 can be realized natively in MBQC as shown in Sec. II C 3. Hence, similar separation holds for the associated MBQC-based generative model.

Theorem 4 (Informal : shallow-depth channel–unitary separation). Consider a one-dimensional nearestneighbor brickwall circuit architecture on N ≥ 6 qubits, together with the minimal correlated channel model of s Def. 1. In this model a single stochastic Pauli string PM , s ∈ {0, 1}, acts on two distant qubits a, b ∈ M ⊆ [1, N ]

Remark 1 (MBQC realization of the separation). As a concrete instantiation, Appendix B 1 gives an explicit MBQC on a cluster-state construction, including the implemented gates, the byproduct propagation, and the verification of the shared randomness conditions used in Theorem 4.

11 B.

where

Class of distributions

The separation theorem in the previous section shows that shared randomness can generate branch-dependent output structure in the channel model that is inaccessible to the corresponding shallow unitary model. In this section, we define and analyze a family of distributions that is particularly suitable for these learning models. We therefore consider finite mixtures of peaked distributions, where each component in the mixture is concentrated around a distinct dominant bit string. This structure is naturally matched to the channel model, since different stochastic branches in the channel model can concentrate output probabilities around different dominant bit strings. When the dominant strings differ coherently across distant qubits, the corresponding distribution may contain long-range correlations that the corresponding shallow local unitary model cannot reproduce. Definition 6 (Branch-peaked mixture distributions). A distribution P on {0, 1}N is called a branch-peaked mixture distribution if X P (x) = π(s) [δs 1[x = x⋆s ] + (1 − δs )Rs (x)] , (60) s∈S

where S ⊆ {0, 1}L is a finite set satisfying |S| ≤ Smax , where Smax = O(1) is independent of N , π(s) ≥ 0 and P π(s) = 1. For each branch s, the point x⋆s ∈ s∈S {0, 1}N refers to the peak or dominant bit string of the corresponding branch distribution, δs ∈ (0, 1], and Rs is a normalized residual distribution satisfying Rs (x⋆s ) = 0 and δs ≥ (1 − δs ) max⋆ Rs (x). x̸=xs

(61)

Here, 1[·] denotes the indicator function. Branch-peaked mixtures allow different branches to have branch-dependent peaks and branch-dependent residual distributions. Further details are provided in Appendix C. In Sec. III C, we further show numerically that suitably designed correlated channel models learn representative distributions from this class more accurately than their unitary competitor.

C.

Numerical results

The learning models considered in this work include a purely unitary model (Eq. (1)) and a correlated channel model defined in Eq. (17). We numerically compare the learning performances of these two models keeping the same width N = 6 and depth D = 2. For the numerical experiment, we consider N = 6 and construct a two-branch target distribution, Y (x) = 0.4 Y0 (x) + 0.6 Y1 (x),

(62)

|x|

6−|x|

(1 − ϵ1 )|x| , (63) with ϵ0 = 0.15 and ϵ1 = 0.25. Here, |x| denotes the Hamming weight of x. The first branch is peaked at x⋆0 = 000000, while the second is peaked at x⋆1 = 111111. In the notation of Definition 6, the corresponding peak weights are δ0 = (1 − ϵ0 )6 and δ1 = (1 − ϵ1 )6 , and Y0 (x) = (1 − ϵ0 )6−|x| ϵ0 ,

Y1 (x) = ϵ1

  Ys (x) , x ̸= x⋆ , s Rs (x) = 1 − δs  ⋆ 0, x = xs .

(64)

Thus, Ys (x) = δs 1[x = x⋆s ] + (1 − δs )Rs (x). So the target distribution Y (x) belongs exactly to the branch-peaked mixture class in Eq. (60) with L = 1 and S = {0, 1}. Since ϵ0 , ϵ1 < 1/2, the first branch has a unique peak at x⋆0 = 000000, while the second has a unique peak at x⋆1 = 111111. We first train the unitary model U (θ) defined in Eqs. (1) and (20). Figure 5 (a) shows the distribution of the minimum MMD loss attained over 300 training epochs across 20 independent random initializations. Each value entering the box plot is therefore the best loss obtained in one training run. We then train the correlated channel model Eθ,p defined in Eq. (26) and shown in Fig. 3. The unitary circuit is now augmented, in the first layer, by the stochastic N6 s1 Pauli string i acting on all qubits immediately i=1 ZN N6 1,z s1 after the sublayer comi Rz (θi ). Since i=1 Zi mutes with the preceding Rz and Rzz sub-layers, this N6 1 placement is equivalent to applying i=1 Zis before the entire first layer. Any circuit layers preceding this insertion slot are set to the identity in the numerical implementation. This Pauli string is controlled by a shared binary variable s1 ∼ Bernoulli(p1 ), with Pr(s1 = 1) = p1 . For comparison, this corresponds to the circuit shown on 1 s1 the right of Fig. 8, with the endpoint string Z1s ⊗ ZN N6 1 s replaced by the global string i=1 Zi . The trainable parameters are the circuit angles θ, in Eq. (22), together with the branch probability p = {p1 }. The box plot in Fig. 5 (b) reports the minimum MMD loss attained in each of the 20 independent random initializations. The correlated channel consistently achieves substantially lower losses than the unitary model and exhibits less variation across random initializations. For every run, the circuit parameters θ are initialized independently and uniformly from [0, 1], while p1 is initialized uniformly from [0.5, 0.7]. We use 6000 samples and a fixed learning rate of 0.5 for the variational angles θ and 0.01 for p1 within the Adagrad optimizer. Further details on the box-plot statistics are provided in Appendix E 2. These finite-size experiments show that, for the selected target and training protocol, the model containing the matching shared branch structure reaches lower final

12

(a)

(b)

FIG. 5. Learning performance of MBQC-based model: Here we examine how well the unitary model U (θ) and the correlated channel model Eθ,p can learn a distribution belonging to the family of distributions defined in Def. 6. The x-axis labels the two learning models, while the y-axis reports the distribution of minimum MMD losses achieved by 20 independently initialized unitary and channel learning models over 300 epochs. Both learning models have N = 6 qubits and depth D = 2. (a) Distribution of minimum MMD losses achieved by the unitary model. (b) Distribution of minimum MMD losses achieved by the correlated channel model where N6 s1 string on all qubits, in the we apply a correlated i=1 Zi 1 first layer, with s ∈ {0, 1} being a binary variable, and probability Pr(s1 = 1) = p1 ∈ [0, 1]. For more details regarding the box plot, see Appendix E 2.

error than the unitary baselines. The analytical separation, rather than the numerical experiment, establishes the representational result.

IV.

CONCLUSION

In this work, we demonstrated both analytically and numerically that shared classical randomness can strictly enlarge the set of output distributions accessible to shallow local quantum generative models. The separation does not arise from increasing the quantum depth, adding ancillas, or using long-range entangling gates. Instead, a single stochastic Pauli string, supported on spatially separated qubits and inserted at an intermediate circuit layer, is sufficient to create a channel model whose output distribution cannot be reproduced by the corresponding shallow local unitary Born model. The obstruction is architectural, as in shallow bounded-connectivity circuits, separated output regions can remain outside each other’s backward light cones, while the shared random Pauli string can correlate their classical outputs without increasing the quantum circuit depth. For one-dimensional nearest-neighbour architectures, reproducing such distributions, obtained from the channel model, with a purely unitary model requires depth growing linearly with the distance between the correlated regions and can therefore

require depth Ω(N ) in the worst case. Note that unitary circuits with linear depth typically suffer from expressivity-induced barren plateaus, whereas shallow circuits do not [26–28]. Consistent with this, we observed no significant optimization difficulties in our numerical experiments in Sec. III C. Moreover, extending the shallow unitary model with shared randomness requires only a few additional trainable parameters. In most of our constructions, a single probability parameter controls the stochastic application of a fixed Pauli string. More generally, the same insights will likely apply to any bounded-degree hardware graph, with the required unitary depth controlled by the graph distance between the correlated regions. Thus the result is not specific to a particular gate set or to a strictly one-dimensional geometry. Instead, it is a statement about finite-speed information propagation in local quantum architectures. The implication for hardware is that classically coordinated stochastic Pauli operations can be a cheap and useful resource for generative modeling on devices where quantum connectivity is limited. On nearest-neighbor superconducting layouts or neutral-atom arrays with local gates, shared randomness can create distributional correlations that would otherwise require deeper routing or longer quantum evolution. In measurement-based implementations, the resource is even more natural as measurement outcomes are already random, and suitable adaptation or retention of selected outcomes realizes the correlated Pauli operations directly. On hardware with native long-range gates, including architectures with high connectivity, the separation based on shared randomness becomes weaker because the relevant graph distances are shorter. Nevertheless, for generative modeling, shared classical randomness can still reduce circuit depth by replacing some coherent long-range operations in the output distribution. Furthermore, on hardware that natively supports the required parametrized Pauli rotations [29– 31], the correlated stochastic Pauli gates can be absorbed into coordinated shifts of existing rotation parameters across the selected qubits, requiring only shared classical control and no additional quantum-gate depth. These results should not be interpreted as a quantum advantage claim over classical computation. Instead, it is a separation between two quantum model classes under the same shallow local quantum resources. The additional resource is classically cheap: a shared random variable controlling local Pauli operations simultaneously. This shows that stochasticity is not merely a way to include unitary models as special cases, but rather, when structured as shared randomness, it can provide a genuine representational advantage at shallow depth. Several directions remain open. One is to characterize more completely which target distributions benefit from shared-randomness beyond the branch-peaked mixture distribution used here. In particular, a classification and optimization of different choices of shared randomness for quantum generative modeling is desirable. Another is to optimize the placement and support of the stochas-

13 tic Pauli strings for realistic hardware graphs. A third is to study trainability: shared randomness enlarges expressivity, but its practical value depends on whether the tunable probabilities corresponding to shared randomness and circuit parameters can be trained efficiently for a particular learning task. Finally, the MBQC realization suggests a broader connection between measurementinduced randomness, adaptive feedforward, and stochastic quantum generative modeling, which may lead to new shallow learning architectures based on classical coordination rather than deeper quantum circuits.

V.

ACKNOWLEDGMENTS

to any author accepted manuscript version arising from this submission. This work was also supported by the European Union (ERC Advanced Grant, QuantAI, No. 101055129). The views and opinions expressed in this article are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council - neither the European Union nor the granting authority can be held responsible for them. GPT-5.6 Sol was used to help establish the consistency of the mathematical statements and proofs during the preparation of the manuscript. All scientific ideas, analyses, and conclusions are those of the authors, and all AIimproved text was carefully reviewed, manually checked, and validated prior to inclusion.

We thank Sofiene Jerbi, Vedran Dunjko, and Damian Markham for useful discussions. This research was funded in part by the Austrian Science Fund (FWF) [SFB BeyondC F7102, DOI: 10.55776/F71; WIT9503323, DOI: 10.55776/WIT9503323]. For open access purposes, the author has applied a CC BY public copy-right license

The code and numerical data supporting the findings of this study are available at [32].

[1] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM review 41, 303 (1999). [2] L. K. Grover, A fast quantum mechanical algorithm for database search, in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (1996) pp. 212–219. [3] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al., Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019). [4] M. Benedetti, E. Lloyd, S. Sack, and M. Fiorentini, Parameterized quantum circuits as machine learning models, Quantum science and technology 4, 043001 (2019). [5] J. Preskill, Quantum computing in the nisq era and beyond, Quantum 2, 79 (2018). [6] J.-G. Liu and L. Wang, Differentiable learning of quantum circuit born machines, Physical Review A 98, 062324 (2018). [7] M. Benedetti, D. Garcia-Pintos, O. Perdomo, V. LeytonOrtega, Y. Nam, and A. Perdomo-Ortiz, A generative modeling approach for benchmarking and training shallow quantum circuits, npj Quantum information 5, 45 (2019). [8] A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, On the complexity and verification of quantum random circuit sampling, Nature Physics 15, 159 (2019). [9] M. J. Bremner, A. Montanaro, and D. J. Shepherd, Average-case complexity versus approximate simulation of commuting quantum computations, Physical Review Letters 117, 080501 (2016). [10] K. Hwang, H.-T. Lim, Y.-S. Kim, D. K. Park, and Y. Kim, Distributed quantum machine learning via classical communication, Quantum Science and Technology 10, 015059 (2025).

[11] E. Bäumer, V. Tripathi, D. S. Wang, P. Rall, E. H. Chen, S. Majumder, A. Seif, and Z. K. Minev, Efficient longrange entanglement using dynamic circuits, PRX Quantum 5, 030339 (2024). [12] L. Piroli, G. Styliaris, and J. I. Cirac, Approximating many-body quantum states with quantum circuits and measurements, Physical Review Letters 133, 230401 (2024). [13] C. Cao and J. Eisert, Measurement-driven quantum advantages in shallow circuits, Phys. Rev. Lett. 136, 080601 (2026). [14] A. Majumder, M. Krumm, T. Radkohl, L. J. Fiderer, H. P. Nautrup, S. Jerbi, and H. J. Briegel, Variational measurement-based quantum computation for generative modeling, Physical Review A 110, 062616 (2024). [15] A. Majumder, H. P. Nautrup, and H. J. Briegel, Minimizing classical resources in variational measurement-based quantum computation for generative modeling, arXiv preprint arXiv:2604.11578 https://doi.org/10.48550/arXiv.2604.11578 (2026). [16] J. Heredge, M. West, L. Hollenberg, and M. Sevior, Nonunitary quantum machine learning, Physical Review Applied 23, 044046 (2025). [17] J. Wen, L. Qian, S. Wei, and G. Long, Trainable quantum channels as computational primitives for quantum learning, arXiv preprint arXiv:2606.15808 https://doi.org/10.48550/arXiv.2606.15808 (2026). [18] F. Buscemi, All entangled quantum states are nonlocal, Phys. Rev. Lett. 108, 200401 (2012). [19] D. Schmid, D. Rosset, and F. Buscemi, The typeindependent resource theory of local operations and shared randomness, Quantum 4, 262 (2020). [20] S. Mohamed and B. Lakshminarayanan, Learning in implicit generative models, arXiv preprint arXiv:1610.03483 https://doi.org/10.48550/arXiv.1610.03483 (2016).

VI.

DATA AVAILABILITY

14 [21] R. Raussendorf and H. J. Briegel, A one-way quantum computer, Physical review letters 86, 5188 (2001). [22] H. J. Briegel and R. Raussendorf, Persistent entanglement in arrays of interacting particles, Physical Review Letters 86, 910 (2001). [23] D. Browne and H. Briegel, One-way quantum computation–a tutorial introduction, arXiv preprint quant-ph/0603226 https://doi.org/10.48550/arXiv.quant-ph/0603226 (2006). [24] H. Poulsen Nautrup and H. J. Briegel, Measurementbased quantum computation from clifford quantum cellular automata, Physical Review A 110, 062617 (2024). [25] A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. Smola, A kernel two-sample test, The journal of machine learning research 13, 723 (2012). [26] M. Larocca, S. Thanasilp, S. Wang, K. Sharma, J. Biamonte, P. J. Coles, L. Cincio, J. R. McClean, Z. Holmes, and M. Cerezo, Barren plateaus in variational quantum computing, Nature Reviews Physics 7, 174 (2025). [27] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nature communications 9, 4812 (2018). [28] M. Ragone, B. N. Bakalov, F. Sauvage, A. F. Kemper, C. Ortiz Marrero, M. Larocca, and M. Cerezo, A lie algebraic theory of barren plateaus for deep parameterized quantum circuits, Nature Communications 15, 7172 (2024). [29] S. Debnath, N. M. Linke, C. Figgatt, K. A. Landsman, K. Wright, and C. Monroe, Demonstration of a small programmable quantum computer with atomic qubits, Nature 536, 63 (2016). [30] D. C. McKay, C. J. Wood, S. Sheldon, J. M. Chow, and J. M. Gambetta, Efficient z gates for quantum computing, Phys. Rev. A 96, 022330 (2017). [31] A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta, Hardwareefficient variational quantum eigensolver for small molecules and quantum magnets, Nature 549, 242 (2017). [32] A. Majumder, Shared randomness for quantum generative models (2026). [33] Y. Wu, J. Yao, P. Zhang, and X. Li, Randomnessenhanced expressivity of quantum neural networks, Physical Review Letters 132, 010602 (2024). [34] B. Coyle, S. Raj, N. Mathur, E. A. Cherrat, N. Jain, S. Kazdaghli, and I. Kerenidis, Training-efficient density quantum machine learning, npj Quantum Information 11, 172 (2025). [35] L. Domingo, G. Carlo, and F. Borondo, Taking advantage of noise in quantum reservoir computing, Scientific Reports 13, 8790 (2023). [36] D. Fry, A. Deshmukh, S. Y.-C. Chen, V. Rastunkov, and V. Markov, Optimizing quantum noise-induced reservoir computing for nonlinear and chaotic time series prediction, Scientific Reports 13, 19326 (2023). [37] A. Sannia, R. Martı́nez-Peña, M. C. Soriano, G. L. Giorgi, and R. Zambrini, Dissipation as a resource for quantum reservoir computing, Quantum 8, 1291 (2024). [38] T. Kubota, Y. Suzuki, S. Kobayashi, Q. H. Tran, N. Yamamoto, and K. Nakajima, Temporal information processing induced by quantum noise, Physical Review Research 5, 023057 (2023).

[39] F. Scala, A. Ceschini, M. Panella, and D. Gerace, A general approach to dropout in quantum neural networks, Advanced Quantum Technologies 8, 2300220 (2025). [40] V. Kuzmin, W. Somogyi, E. Pankovets, and A. Melnikov, Method for noise-induced regularization in quantum neural networks, Advanced Quantum Technologies 8, e00603 (2025). [41] J.-C. Huang, Y.-L. Tsai, C.-H. H. Yang, C.-F. Su, C.M. Yu, P.-Y. Chen, and S.-Y. Kuo, Certified robustness of quantum classifiers against adversarial examples through quantum noise, in ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (IEEE, 2023) pp. 1–5. [42] D. Winderl, N. Franco, and J. M. Lorenz, Constructing optimal noise channels for enhanced robustness in quantum machine learning, in 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), Vol. 1 (IEEE, 2025) pp. 1566–1577. [43] J. Liu, F. Wilde, A. A. Mele, X. Jin, L. Jiang, and J. Eisert, Stochastic noise can be helpful for variational quantum algorithms, Physical Review A 111, 052441 (2025). [44] X. Gao, E. R. Anschuetz, S.-T. Wang, J. I. Cirac, and M. D. Lukin, Enhancing generative models via quantum correlations, Physical Review X 12, 021037 (2022). [45] Z. Qin, X. Li, Y. Zhou, S. Zhang, R. Li, C. Du, and Z. Xiao, Applicability of measurement-based quantum computation towards physically-driven variational quantum eigensolver, New Journal of Physics 26, 073040 (2024). [46] I. D. Smith, H. P. Nautrup, and H. J. Briegel, Parity quantum computing as yz-plane measurement-based quantum computing, Phys. Rev. Lett. 132, 220602 (2024).

15 VII.

RELATED WORK

Generically, previous works adding classical randomness into parameterized quantum circuits mostly rely on the observation that quantum channels are more general than unitaries. However, we are not aware of other works systematically investigating the crucial benefits of shared classical randomness for generative modeling with shallow quantum circuits. Furthermore, we focus on keeping the number of additional trainable parameters small. Inspired by MBQC, we often have just few additional trainable probabilities deciding whether a few fixed Pauli strings get placed or not at an intermediate layer in the circuit. This requires no long-range entangling gates, no mid-circuit measurements, and no controlled arbitrary unitaries. Despite this minimal modification, the resulting channel model can generate long-range output correlations that shallow local unitary models cannot represent, because the relevant backward light cones of the latter remain disjoint. Thus, our contribution is not the generic claim that “randomness helps”, nor an empirical optimization effect, but strict complexity-theoretical shallow-depth separations for quantum generative models enabled by shared randomness. Prior works have demonstrated that stochasticity, mixtures, and non-unitary extensions of variational quantum circuits can improve expressivity or trainability compared with purely unitary architectures. Wu et al. [33] introduced randomness-enhanced quantum neural networks, where a parameterized unitary circuit is enhanced by a random unitary layer sampled from an ensemble. These randomly sampled unitaries consist of trainable single qubit rotations. Instead of such trainable random unitaries, we chose to sample only fixed Pauli strings to keep the parameter count smaller. Using majorization theory of observables, they analytically and also numerically show that stochasticity can increase the expressive power of quantum models for supervised learning tasks. Different from our work, the analytical results take advantage of restrictions given by unitarity itself (unitary channels cannot change eigenvalues of observables), rather than restrictions introduced by shallow ansätze of local connectivity. Similarly, Coyle et al. [34] proposed density quantum neural networks, in which the model outputs an average over a weighted ensemble of trainable unitary branches. Equivalently, each circuit execution samples one branch from the ensemble, runs the corresponding parameterized sub-unitary, and estimates observables by averaging over branches. This results in a density matrix similar to Local-Combination-of-Unitaries (LCU), but with smaller resource overhead. However, also here, each branch may still be a nontrivial trainable circuit with its own parameters, depth, and entangling structure. The formal results analyze the training cost and in particular the number of samples, and compare the resource costs to the standard LCU scheme. The interplay of shallowness and shared randomness is not explicitly explored. The LCU scheme itself has been analyzed in Heredge et al. [16] for adapting classical machine learning principles such as residual connections and pooling layers. Such constructions can increase expressivity, but they typically require coherent control over multiple unitary components, which can substantially increase circuit depth and implementation overhead. Furthermore, the non-unitary is not achieved by the injection of randomness, but by post-selection. Wen et al. [17] formulate trainable quantum channels as computational primitives, emphasizing that generically, channels and their parameterized Kraus operators strictly generalize unitary models. Also here, the argument that unitaries cannot change eigenvalues of observables is used. They also argue that the loss landscape is not constrained to a unitary manifold anymore. As channel ansätze, they investigate unitary circuits supplemented with tunable amplitude- and phase-damping channels, which they interpret as tunable dissipation. Noise and dissipation have also been used productively in quantum learning. In quantum reservoir computing, Domingo et al. [35], Fry et al. [36], Sannia et al. [37], and Kubota et al. [38] show that noise or dissipation can improve temporal information processing or reservoir performance. These works mostly consider single qubit noise, although the last reference also considers noise affecting two nearby qubits. These works acknowledge the usefulness of noise or dissipation for reducing quantum resources, but they do not investigate the benefits of shared randomness over distant qubits. Their noise is also fixed, while we consider trainable shared randomness. Other works use stochastic noise for regularization, robustness, or optimization: Scala et al. [39] study quantum dropout, Kuzmin et al. [40] study noise-induced regularization, Huang et al. [41] and Winderl et al. [42] use noise for adversarial robustness, and Liu et al. [43] show that stochastic noise can help variational algorithms escape strict saddles. These results show that noise need not be detrimental, but none identify shared classical randomness as a resource for overcoming locality constraints in shallow generative Born models. Variational measurement-based quantum computation (VMBQC) was introduced as a framework in which measurement-induced Pauli byproducts are retained with trainable probabilities and exploited for quantum generative modeling [14]. More recently, it was shown that even a restricted VMBQC channel with a single additional trainable probability can represent distributions inaccessible to the corresponding unitary model [15]. The present work extends these architecture-specific observations by identifying shared classical randomness as the relevant resource and establishing a strict shallow-depth separation for general local quantum circuits. Several other works have shown that one can generate long-range correlations by preparing pure states with longrange entanglement. Dynamic circuits and LOCC-assisted protocols use ancilla qubits, measurements and classical

16 communication to generate long-range entanglement or reduce state-preparation depth [11, 12]. Those works show that non-unitary operations and classical communication can overcome geometric limitations of local unitary circuits. Our setting uses the same broad physical principle, but for a different task: learning classical output distributions. However, our scheme needs no ancilla qubits to prepare superposition of states with long-range entanglement, and no classical communication or feed-forward operations between qubits. Instead, our scheme can be interpreted as using shared classical randomness. Distributed QML schemes connect quantum processors using classical channels or real-time communication [10]. This motivates classical communication as a scalable architectural primitive. Our model is lower-level and more specific: the classical channel samples a shared random variable that coordinates Pauli operations across qubits, thereby modifying the generated probability distribution. Our scheme relies on shared classical randomness rather than measurement-conditioned classical communication. More generally, quantum generative models aim to exploit structured correlations that are difficult to capture with restricted classical models. For example, Gao et al. [44] showed that quantum correlations can enhance generative modeling by comparing classical Bayesian-network models with basis-enhanced Bayesian quantum circuits. Their separations use quantum non-locality and contextuality to show advantages over classical k-gram and hidden-Markov models.

17 SUPPLEMENTARY MATERIALS Appendix A: Background and definitions

a. Brickwall circuit architecture. Throughout the separation proofs, the local unitary model is a one-dimensional nearest-neighbor brickwall circuit on N qubits with open boundary conditions. It is written as U (θ) = UD (θD ) · · · U1 (θ1 ),

(A1)

where D denotes the number of brickwall layers. Each layer consists of two sub-layers of nearest-neighbor two-qubit gates, (k)

(k) Uk (θk ) = Uodd Ueven ,

(A2)

with (k) Ueven =

N −1 Y

(k)

(k)

Gi,i+1 ,

Uodd =

i=2, i even

N −1 Y

(k)

Gi,i+1 .

(A3)

i=1, i odd

(k)

Here, (Gi,i+1 ) is an arbitrary two-qubit gate acting on the neighboring sites (i, i + 1). The gates within each sublayer have disjoint supports and therefore can be applied in parallel, whereas the ordering of the even- and odd-bond sublayers is part of the circuit definition. Arbitrary single-qubit gates may be inserted before, after, or between these sublayers without changing the spatial locality of the architecture. Open boundary conditions restrict the two-qubit gates to the edges (i, i + 1), with (i = 1, . . . , N − 1). This architecture defines the local unitary baseline used in the separation results. b. Input state. We consider a fixed product input state ρin =

N O

ρj ,

(A4)

j=1

where each ρj is an arbitrary single-qubit density operator. The state may therefore be pure or mixed and need not be identical across the qubits. The product-state assumption ensures that the input contains no correlations between spatially separated regions. c. Stochastic Pauli string. Let M ⊆ {1, . . . , N } denote a subset of qubits containing at least two distinct sites. A Pauli string supported on M is defined as PM :=

Y

Qj ,

Qj ∈ {Xj , Zj },

(A5)

j∈M

with the identity acting on all qubits outside M . A single Bernoulli random variable s ∈ {0, 1}, with Pr(s = 0) = 1 − p,

Pr(s = 1) = p,

(A6)

controls the application of the entire string, ( s PM =

I, s = 0, PM , s = 1.

(A7)

The same random bit therefore determines the Pauli operations on each site in M simultaneously. Averaging over s gives the stochastic Pauli channel † Ep (ρ) = (1 − p)ρ + pPM ρPM .

(A8)

s for some input state ρ. The stochastic Pauli string PM may be inserted between any two consecutive layers of the brickwall circuit in Eq. (A1).

18 d. Unitary and channel output distributions For a fixed depth D, input state ρin , and local circuit architecture, let U (θ) denote the parametrized unitary circuit. After computational-basis measurement, its output distribution, as shown in Eq. (6), is   PU (θ) (x) = Tr |x⟩⟨x|U (θ)ρin U (θ)† , x ∈ {0, 1}N . (A9) The corresponding family of unitary output distributions is  Punit (D) := PU (θ) : θ ∈ ΘD .

(A10)

where ΘD denotes the parameter domain of the depth-D circuit. The corresponding correlated channel model, as defined in Eq. (17), is X πp (s) U (s) (θ)ρin U (s) (θ)† Eθ,p (ρin ) =

(A11)

s∈{0,1}L

where U (s) (θ) denotes the branch unitary corresponding to a fixed realization s = (s1 , . . . , sL ) ∈ {0, 1}L of the stochastic control variables. For a single stochastic Pauli string, this reduces to s ∈ {0, 1} and the corresponding branch unitary U (s) (θ). The computational-basis output distribution is PEθ,p (x) = Tr [|x⟩⟨x|Eθ,p (ρin )] . The family of channel output distributions is therefore  Pch (D) := PEθ,p : θ ∈ ΘD , p ∈ [0, 1]L .

(A12)

(A13)

where L is the number of stochastic Pauli strings in the circuit. Here, |x⟩ = |x1 ⟩⊗· · ·⊗|xN ⟩ denotes the computationalbasis state associated with x = (x1 , . . . , xN ) ∈ {0, 1}N . e. Total variation distance. Total variation distance is a metric for comparing two output probability distributions. For distributions P and Q on the same finite sample space Ω, it is defined as 1X |P (x) − Q(x)|. (A14) TV(P, Q) := 2 x∈Ω

Thus, a lower bound on total variation distance gives a strong distributional separation: if TV(P, Q) ≥ δ, then the two models cannot approximate each other closer than error δ at the level of output distributions. Definition 7 (Z-covariance). Let ρ be an N -qubit state and let ρab denote its reduced state on qubits a and b. The Z-covariance between these qubits is defined as the connected two-point correlator Covρab (Ẑa , Ẑb ) := ⟨Ẑa ⊗ Ẑb ⟩ρab − ⟨Ẑa ⟩ρab ⟨Ẑb ⟩ρab ,

(A15)

where ⟨Ẑa ⟩ρab := Tr[ρab (Ẑa ⊗ I)],

⟨Ẑb ⟩ρab := Tr[ρab (I ⊗ Ẑb )],

⟨Ẑa ⊗ Ẑb ⟩ρab := Tr[ρab (Ẑa ⊗ Ẑb )].

(A16)

Lemma 8 (Backward light cones in a nearest neighbor brickwall circuit). Consider an open-chain nearest-neighbour brickwall circuit on N qubits as in Eq. (A1), where each layer in the circuit can have arbitrary single-qubit gates and nearest-neighbour two-qubit gates. For any qubit a ∈ {1, . . . , N }, let LD (a) denote the support of the backward light cone of its final computational-basis measurement after D layers of the circuit. Then LD (a) ⊆ {max{1, a − 2D}, . . . , min{N, a + 2D}} .

(A17)

Consequently, for any two distinct qubits a, b ∈ {1, . . . , N }, dist(a, b) , 4 implies that their backward light cones are disjoint: D<

dist(a, b) := |a − b|,

LD (a) ∩ LD (b) = ∅.

(A18)

(A19)

In particular, for the boundary qubits a = 1 and b = N , LD (1) ⊆ {1, . . . , 2D + 1},

LD (N ) ⊆ {N − 2D, . . . , N },

(A20)

and these supports are disjoint whenever D<

N −1 . 4

(A21)

19 Similar bounds hold for more general local circuit architectures, where the depth D is determined by the interaction range and geometry of the underlying connectivity graph. Proof. Consider two qubits a, b ∈ {1, . . . , N }, and assume without loss of generality that a < b. The backward light cone of the final computational-basis measurement on qubit a is obtained by propagating the observable Ẑa backwards through the circuit. Similarly, the backward light cone of the measurement on qubit b is obtained by propagating Ẑb backwards. Single-qubit gates do not enlarge the support of an operator. A nearest-neighbor two-qubit gate acting on qubits (i, i + 1) can enlarge the support only across the edge (i, i + 1). In particular, if the operator is supported on one endpoint of the gate, conjugation may extend its support to the other endpoint, whereas a gate whose support is disjoint from that of the operator leaves the operator support unchanged. Each circuit layer contains at most two nearest-neighbor two-qubit sublayers (see Eq. (A2)). Hence, during one full layer, the support of a backward-propagated operator can expand by at most two sites in each direction. Starting from the single-site support a, after D layers the backward light cone therefore satisfies LD (a) ⊆ {max{1, a − 2D}, . . . , min{N, a + 2D}} .

(A22)

LD (b) ⊆ {max{1, b − 2D}, . . . , min{N, b + 2D}} .

(A23)

The same argument gives

Since a < b, these two intervals are disjoint whenever a + 2D < b − 2D. Equivalently, 4D < b − a = dist(a, b) or Therefore, D < dist(a,b) 4 LD (a) ∩ LD (b) = ∅

(A24)

under the stated depth condition. Lemma 9 (Two-qubit computational-basis marginal). Let ρ be an arbitrary N -qubit state, and let ρab denote its reduced state on qubits a and b. Measuring these two qubits in the computational basis produces the joint distribution P (xa , xb ), where xa , xb ∈ {0, 1}. Then  1 P (xa , xb ) = 1 + (−1)xa ⟨Ẑa ⟩ + (−1)xb ⟨Ẑb ⟩ + (−1)xa +xb ⟨Ẑa ⊗ Ẑb ⟩ , (A25) 4 where ⟨Ẑa ⟩ := Tr[ρab (Ẑa ⊗ I)],

⟨Ẑb ⟩ := Tr[ρab (I ⊗ Ẑb )],

⟨Ẑa ⊗ Ẑb ⟩ := Tr[ρab (Ẑa ⊗ Ẑb )].

(A26)

Proof. The joint probability of outcomes xa , xb ∈ {0, 1} is P (xa , xb ) = Tr[ρab (Πxa ⊗ Πxb )],

(A27)

 1 I + (−1)xi Ẑi , 2

(A28)

where Πxi = |xi ⟩⟨xi | =

i ∈ {a, b}.

Therefore, Πxa ⊗ Πxb =

 1 I ⊗ I + (−1)xa Ẑa ⊗ I + (−1)xb I ⊗ Ẑb + (−1)xa +xb Ẑa ⊗ Ẑb . 4

(A29)

Substituting this expression into Eq. (A27) gives exactly Eq. (A25), since Tr[ρab ] = 1. Lemma 10 (Disjoint light cones imply factorized two-site marginal). Consider an open chain depth-D onedimensional nearest-neighbor brickwall unitary circuit U (θ) (Eq. (A1)) acting on an N -qubit product input state NN ρin = i=1 ρi . Let a and b be two output sites separated by distance dist(a, b), and let   ρab := Tr[1,N ]\{a,b} U (θ)ρin U (θ)† (A30) be the reduced output state on sites a and b. Then Covρab (Ẑa , Ẑb ) = 0 for all depth D < dist(a,b) . Consequently, the 4 computational-basis two-site joint marginal factorizes as PU (θ) (xa , xb ) = PU (θ) (xa )PU (θ) (xb ),

xa , xb ∈ {0, 1}.

(A31)

20 Proof. Define the Heisenberg-evolved observables Ôa := U (θ)† (Ẑa ⊗ I[1,N ]\{a} )U (θ),

Ôb := U (θ)† (Ẑb ⊗ I[1,N ]\{b} )U (θ).

(A32)

the backward light cones of a and b are disjoint. Hence Ôa and Ôb are From Lemma 8, for all depth D < dist(a,b) 4 supported on disjoint sets of input qubits. Therefore, using the product structure of ρin , Tr[ρab (Ẑa ⊗ Ẑb )] = Tr[ρin Ôa Ôb ]

(A33)

= Tr[ρin Ôa ] Tr[ρin Ôb ]

(A34)

= Tr[ρab (Ẑa ⊗ I)] Tr[ρab (I ⊗ Ẑb )].

(A35)

Thus Covρab (Ẑa , Ẑb ) = Tr[ρab (Ẑa ⊗ Ẑb )] − Tr[ρab (Ẑa ⊗ I)] Tr[ρab (I ⊗ Ẑb )] = 0.

(A36)

Now apply Lemma 9. Write α := Tr[ρab (Ẑa ⊗ I)],

β := Tr[ρab (I ⊗ Ẑb )],

γ := Tr[ρab (Ẑa ⊗ Ẑb )].

(A37)

The zero-covariance condition gives γ = αβ. Therefore,
1 1 + (−1)xa α + (−1)xb β + (−1)xa +xb γ 4
1 1 + (−1)xa α + (−1)xb β + (−1)xa +xb αβ = 4 1 1 = (1 + (−1)xa α) (1 + (−1)xb β) 2 2 = PU (θ) (xa )PU (θ) (xb ).

PU (θ) (xa , xb ) =

(A38) (A39) (A40) (A41)

This proves the factorization of the two-site computational-basis marginal. Lemma 11 (Marginal obstruction implies full-distribution obstruction). Let P be a target probability distribution on {0, 1}N , and let Q := {Qθ : θ ∈ Θ}

(A42)

be a model class of probability distributions on {0, 1}N . For any subset M ⊆ [1, N ], denote the marginal of P on M by PM , and the corresponding marginal of Qθ by Qθ,M . If there exists a subset M ⊆ [1, N ] such that PM ∈ / {Qθ,M : θ ∈ Θ},

then

P ∈ / Q.

(A43)

Equivalently, if no model distribution has the correct marginal on M , then no model distribution can equal the full target distribution. Proof. If P = Qθ , then marginalizing both sides gives PM = Qθ,M , contradicting the assumption. Lemma 12 (Quantitative marginal obstruction). Let d be any statistical distance or divergence that is contractive under marginalization, namely d(PM , QM ) ≤ d(P, Q)

(A44)

N

for all probability distributions P, Q on {0, 1} and all subsets M ⊆ [1, N ]. Then, for every target distribution P and every model class Q := {Qθ : θ ∈ Θ}, one has inf d(P, Qθ ) ≥ inf d(PM , Qθ,M )

θ∈Θ

θ∈Θ

(A45)

for every M ⊆ [1, N ]. In particular, if for some M ⊆ [1, N ], inf d(PM , Qθ,M ) ≥ ε > 0,

θ∈Θ

then

inf d(P, Qθ ) ≥ ε.

θ∈Θ

Thus, a nonzero obstruction at the marginal level implies a nonzero obstruction at the full-distribution level.

(A46)

21 Proof. The claim follows by contractivity under marginalization: d(P, Qθ ) ≥ d(PM , Qθ,M )

(A47)

for every θ, and then taking the infimum over θ. For all analytical bounds in this paper, we mostly use the total variation (TV) distance as the divergence metric. Lemma 13 (Diagonal observable gap implies total-variation gap). Let ρ and σ be two N -qubit states, and let Pρ and Pσ be their Born distributions obtained by measuring all qubits in the computational basis. Let X A= ax Πx , Πx := |x⟩⟨x| (A48) x∈{0,1}N

be a diagonal observable satisfying ∥A∥∞ ≤ 1. Then |Tr[Aρ] − Tr[Aσ]| ≤ 2 TV(Pρ , Pσ ).

(A49)

1 |Tr[Aρ] − Tr[Aσ]| . 2

(A50)

Equivalently, TV(Pρ , Pσ ) ≥ Proof. Since A is diagonal in the measurement basis,

|Tr[Aρ] − Tr[Aσ]| =

X

(A51)

|ax | |Pρ (x) − Pσ (x)|

(A52)

|Pρ (x) − Pσ (x)|

(A53)

ax Pρ (x) − Pσ (x)

x

≤

X x

≤

X x

= 2 TV(Pρ , Pσ ).

(A54)

Lemma 14 (Covariance gap implies total-variation gap). Let ρ and σ be two arbitrary N -qubit states, and let ρab and σab denote their respective reduced states on qubits a and b. Let Pρab and Pσab be the corresponding joint distributions obtained by measuring qubits a and b in the computational basis. Define Covρ (Ẑa , Ẑb ) = Covρab (Ẑa , Ẑb ) := Tr[ρab (Ẑa ⊗ Ẑb )] − Tr[ρab (Ẑa ⊗ I)] Tr[ρab (I ⊗ Ẑb )],

(A55)

and similarly for σab . Then TV(Pρab , Pσab ) ≥

1 Covρab (Ẑa , Ẑb ) − Covσab (Ẑa , Ẑb ) . 6

(A56)

Proof. Set αρ := Tr[ρab (Ẑa ⊗ I)],

βρ := Tr[ρab (I ⊗ Ẑb )],

γρ := Tr[ρab (Ẑa ⊗ Ẑb )],

(A57)

and define ασ , βσ , γσ analogously. By Lemma 13, applied to Ẑa ⊗ I, I ⊗ Ẑb , and Ẑa ⊗ Ẑb , we have |αρ − ασ | ≤ 2 TV(Pρab , Pσab ),

|βρ − βσ | ≤ 2 TV(Pρab , Pσab ),

|γρ − γσ | ≤ 2 TV(Pρab , Pσab ).

(A58)

Since |αρ |, |βσ | ≤ 1, we get

Rearranging proves the claim.

Covρab (Ẑa , Ẑb ) − Covσab (Ẑa , Ẑb )

(A59)

= |γρ − αρ βρ − γσ + ασ βσ | ≤ |γρ − γσ | + |αρ βρ − ασ βσ | ≤ |γρ − γσ | + |αρ | |βρ − βσ | + |βσ | |αρ − ασ | ≤ 6 TV(Pρab , Pσab ).

(A60) (A61) (A62) (A63)

22 Appendix B: Proof of Theorem 4

Theorem 15 (Formal : shallow-depth channel–unitary separation). Consider a one-dimensional nearest-neighbor brickwall circuit architecture on N ≥ 6 qubits, together with the minimal correlated channel model of Def. 1, in which s a single stochastic Pauli string PM = Pas ⊗ Pbs , s ∈ {0, 1}, acts on two distant qubits a, b ∈ M that are separated by . Let Punit (D) and Pch (D) denote the distance dist(a, b) (see Def. 3). Also consider circuit depths 1 < D < dist(a,b) 4 family of output distributions defined in Eqs. (A10) and (A13), respectively. Let Ẑa and Ẑb denote the final local Pauli observables at output sites a and b. Suppose that there exists a parameter choice (θ ⋆ , p⋆ ) of the channel model with p⋆ ∈ (0, 1) such that the two branches, ρ(0) and ρ(1) (Eq. (19)), induce different local quantum responses at both output sites: ∆a := ma (1) − ma (0) ̸= 0,

∆b := mb (1) − mb (0) ̸= 0,

where ma (s) := Tr[Ẑa ρ(s) ], mb (s) := Tr[Ẑb ρ(s) ]. (B1)

Let E ⋆ := E(θ⋆ ,p⋆ ) , and Q⋆ := PE(θ⋆ ,p⋆ ) be the Born distribution obtained by measuring E ⋆ in the computational basis. Then for any depth 1 < D < dist(a,b) 4 Q⋆ ∈ / Punit (D)

(B2)

Moreover, there is a constant δ ⋆ = 16 p⋆ (1 − p⋆ )|∆a ∆b | > 0, such that the infimum of the total variation distance between Q∗ and the unitary distribution PU (θ) is lower bounded by
inf TV Q⋆ , PU (θ) ≥ δ ⋆ (B3) θ

for every such depth D. In particular, if dist(a, b) = Θ(N ), then any purely unitary nearest-neighbor model that represents Q⋆ requires linear depth, D = Ω(N ). In Corollary 18, we will give explicit shallow-depth MBQC constructions of Q∗ satisfying Eq. (B2) on a cluster state. There, we will show that already depth-2 in the channel model is sufficient to obtain such distributions Q∗ . Proof. We prove the statement by exhibiting a two-qubit marginal that is generated by the correlated channel at some fixed shallow depth but cannot be generated by any unitary circuit whose backward light cones around the two relevant sites are disjoint. s s is the · · · U1 (θ1 ). Here, PM Write the branches of the channel model E ∗ as U (s) (θ) = UD (θD ) · · · Ul+1 (θl+1 )PM ∗ stochastic Pauli string, acting on qubits a and b, inserted with probability p at an intermediate layer (compare Def. 1), and D denotes the depth of E ∗ . Let s ∈ {0, 1}, with Pr(s = 1) = p⋆ ,

Pr(s = 0) = 1 − p⋆ .

(B4)

such that the channel model can be written as Eθ∗ ,p∗ (ρin ) = E ∗ = Pr(s = 0)U (0) (θ)ρin U (0) (θ)† + Pr(s = 1)U (1) (θ)ρin U (1) (θ)† = (1 − p∗ )ρ(0) + p∗ ρ(1)

(B5) (B6)

Because the branch variable s is classical, expectation values in the averaged channel are obtained by averaging the branch-conditioned expectation values. For the one-site observable Ẑa Tr[Ẑa E ∗ ] = ⟨Ẑa ⟩E ∗ = (1 − p∗ ) Tr[Ẑa ρ(0) ] + p∗ Tr[Ẑa ρ(1) ]

(B7)

Tr[Ẑb E ∗ ] = ⟨Ẑb ⟩E ∗ = (1 − p∗ ) Tr[Ẑb ρ(0) ] + p∗ Tr[Ẑb ρ(1) ]

(B8)

and similarly

Define the branch-dependent local biases for both sites as ma (s) := Tr[Ẑa ρ(s) ] = ⟨Ẑa ⟩s ,

mb (s) := Tr[Ẑb ρ(s) ] = ⟨Ẑb ⟩s .

(B9)

⟨Ẑb ⟩E ∗ = (1 − p∗ )mb (0) + p∗ mb (1)

(B10)

Then ⟨Ẑa ⟩E ∗ =(1 − p∗ )ma (0) + p∗ ma (1),

23 Regarding ⟨Ẑa Ẑb ⟩E ∗ , within each fixed branch, the two relevant light-cone regions are disjoint at the insertion layer. Since the state on these regions factorizes, the conditional two-point expectation factorizes: ⟨Ẑa Ẑb ⟩s = ⟨Ẑa ⟩s ⟨Ẑb ⟩s = ma (s)mb (s).

(B11)

⟨Ẑa Ẑb ⟩E ∗ = (1 − p∗ )ma (0)mb (0) + p∗ ma (1)mb (1)

(B12)

Therefore

The covariance of the two-site marginal of Q⋆ is hence CovE ∗ (Ẑa , Ẑb ) = ⟨Ẑa Ẑb ⟩E ∗ − ⟨Ẑa ⟩E ∗ ⟨Ẑb ⟩E ∗ = (1 − p⋆ )ma (0)mb (0) + p⋆ ma (1)mb (1)    − (1 − p⋆ )ma (0) + p⋆ ma (1) (1 − p⋆ )mb (0) + p⋆ mb (1)    = p⋆ (1 − p⋆ ) ma (1) − ma (0) mb (1) − mb (0) . Thus the averaged channel has nonzero two-site covariance whenever    ma (1) − ma (0) mb (1) − mb (0) ̸= 0

(B13) (B14) (B15) (B16)

(B17)

and p⋆ ∈ (0, 1). We assume that the correlated branch changes both local responses, namely ∆a := ma (1) − ma (0) ̸= 0,

∆b := mb (1) − mb (0) ̸= 0.

(B18)

Now consider any purely unitary depth-D circuit from the corresponding local nearest neighbor architecture with D<

dist(a, b) . 4

(B19)

By the light-cone bound, the backward light cones of the two measured sites a and b are disjoint (Lemma 8). Since the input state is a product state, according to Lemma 10 CovU (θ) (Ẑa , Ẑb ) = 0

(B20)

for every parameter choice θ and every such depth D. Thus the joint marginal distribution on (a, b) for the unitary model is a product distribution (see Lemma 10) PU (θ) (xa , xb ) = Pab = PU (θ) (xa )PU (θ) (xb ),

xi ∈ {0, 1}

(B21)

whereas under the condition ∆a , ∆b ̸= 0, the marginal over (a, b) for the channel distribution Q∗ can not be written as a product distribution for any q(xa ) and q(xb ) as below Q∗ (xa , xb ) = Q∗ab ̸= q(xa )q(xb ),

xi ∈ {0, 1}

(B22)

Therefore no such unitary distribution can have the same two-site marginal as Q⋆ . By the marginal-obstruction Lemma 11, no unitary distribution can equal the full distribution Q⋆ . Consequently, Q⋆ ∈ / Punit (D)

(B23)

dist(a, b) . 4

(B24)

for every D<

It remains to justify the quantitative total-variation gap. Let Q⋆ab be the two-site marginal of Q⋆ , and let Pab be any factorized two-site marginal generated by a unitary circuit below light-cone overlap, i.e., D < dist(a,b) . From 4 Lemma 14 one can write CovE ∗ (Ẑa , Ẑb ) − CovU (θ) (Ẑa , Ẑb ) ≤ 6 TV(Q⋆ab , Pab ).

(B25)

24 Since CovU (θ) (Ẑa , Ẑb ) = 0, we obtain 1 ⋆ p (1 − p⋆ )|∆a ∆b |. 6

TV(Q⋆ab , Pab ) ≥

(B26)

Total variation is contractive under marginalization, so for the full distributions (see Lemma 12) TV(Q⋆ , PU (θ) ) ≥ TV(Q⋆ab , PU (θ),ab ).

(B27)

inf TV(Q⋆ , PU (θ) ) ≥ δ ⋆ ,

(B28)

Thus θ

where one may take δ ⋆ :=

1 ⋆ p (1 − p⋆ )|∆a ∆b | > 0. 6

(B29)

The positivity follows from p∗ ∈ (0, 1) and ∆a ∆b ̸= 0. The gap is maximized at p⋆ = 1/2, giving ⋆ δmax =

1 |∆a ∆b |. 24

(B30)

Since |∆a |, |∆b | ≤ 2 for Pauli observables, the universal upper bound is ⋆ δmax ≤

1 . 6

(B31)

Finally, if dist(a, b) = Θ(N ), then the condition for light-cone overlap implies that any corresponding purely unitary nearest-neighbor realization of Q∗ requires depth D = Ω(N ). Corollary 16 (Separation for finite-range circuits). The separation in Theorem 15 is not specific to the particular nearest-neighbor brickwall ansatz considered above. Consider any local circuit architecture in which the past light cone of any measured qubit expands by at most vD sites after depth D, for some constant velocity v = O(1) independent of N . Then there exist output distributions generated by the correlated channel model at a fixed shallow depth D, independent of N , that cannot be generated by the corresponding purely unitary model at any depth D<

dist(a, b) , 2v

(B32)

where a and b are the two sites linked by the stochastic Pauli string, and dist(a, b) denotes their distance in the circuit layout (see Def. 3). In particular, the growth of dist(a, b) with system size induces lower bounds on the depths of the unitary competitors that can reproduce the shallow channel model distributions. Corollary 16 also recovers the linear lower bound for one-dimensional nearest-neighbor brickwall circuits where v = 2. Corollary 17 (No covariance separation with independent random Paulis). Consider the setting of Theorem 15. Instead of the stochastic Pauli string Pas ⊗Pbs controlled by a shared variable s ∈ {0, 1}, consider independent stochastic Pauli operations Pasa and Pbsb on two distant sites a and b, where sa , sb ∈ {0, 1} are independent binary variables with Pr(sa = 1) = pa , and Pr(sb = 1) = pb . Assume that, within each fixed branch (sa , sb ) ∈ {0, 1}2 , the two relevant light-cone regions factorize, as in Theorem 15. Then the averaged output state of the channel model satisfies CovE ⋆ (Ẑa , Ẑb ) = 0.

(B33)

Consequently, the two-site computational-basis marginal factorizes as Q⋆ab (xa , xb ) = Q⋆a (xa )Q⋆b (xb ), xa , xb ∈ {0, 1}. Proof. For fixed branch values (sa , sb ), define U sa ,sb (θ) = UD (θD ) · · · Uk (θk ) (Pasa ⊗ Pbsb ) · · · U1 (θ1 ),

(B34)

ρ(sa ,sb ) = U sa ,sb (θ)ρin U sa ,sb (θ)† .

(B35)

and for some input state ρin

25 The averaged output state is then X

E⋆ =

Pr(sa ) Pr(sb )ρ(sa ,sb )

(B36)

sa ,sb ∈{0,1}

Define the branch-dependent local responses ma (sa ) := Tr[Ẑa ρ(sa ,sb ) ],

mb (sb ) := Tr[Ẑb ρ(sa ,sb ) ].

(B37)

Here ma depends only on sa and mb depends only on sb , because the two branches are independent and act on disjoint relevant regions. By the branch-dependent factorization assumption, Tr[Ẑa Ẑb ρ(sa ,sb ) ] = Tr[Ẑa ρ(sa ,sb ) ] Tr[Ẑb ρ(sa ,sb ) ] = ma (sa )mb (sb ).

(B38)

Therefore, ⟨Ẑa ⟩E ⋆ =

X

X

Pr(sa ) Pr(sb )ma (sa ) =

sa ,sb

=

X

Pr(sa )ma (sa )

sa

X

Pr(sb )

(B39)

sb

Pr(sa )ma (sa ),

(B40)

sa

since ma has no sb dependence and similarly ⟨Ẑb ⟩E ⋆ = ⟨Ẑa Ẑb ⟩E ⋆ =

X

P

sb Pr(sb )mb (sb ). For the two-site expectation,

Pr(sa ) Pr(sb )ma (sa )mb (sb )

(B41)

sa ,sb

! X

=

Pr(sa )ma (sa )

sa

! X

Pr(sb )mb (sb )

(B42)

sb

= ⟨Ẑa ⟩E ⋆ ⟨Ẑb ⟩E ⋆ .

(B43)

Hence CovE ⋆ (Ẑa , Ẑb ) = ⟨Ẑa Ẑb ⟩E ⋆ − ⟨Ẑa ⟩E ⋆ ⟨Ẑb ⟩E ⋆ = 0.

(B44)

By Lemma 10, the two-site computational-basis marginal therefore factorizes: Q⋆ab (xa , xb ) = Q⋆a (xa )Q⋆b (xb ).

(B45)

Thus independent random Pauli byproducts do not generate the non-zero two-site covariance used in Theorem 15. Hence the covariance-based marginal obstruction does not yield a strict separation for this independent-byproduct model. Nevertheless, the weak inclusion Punit (D) ⊆ Pch (D)

(B46)

still holds whenever the channel model contains the unitary model as the special case with trivial byproduct probabilities. 1.

MBQC on a cluster state

As an illustrative realization of a one-dimensional nearest-neighbor architecture used in Theorem 15, we consider measurement-based quantum computation on an N × (D + 1) cluster state, where the final column is the readout layer. We focus on an open chain of N ≥ 6 qubits with two computational layers, corresponding to depth D = 2 (see Fig. 7 (a)). The input is the product state of the form ρin = Rx (α)|0⟩⟨0|Rx (α)†

⊗N

,

sin α cos α ̸= 0,

α∈ /

π Z 2

(B47)

26 A

B

Layer indices

C

B

C

Measure auxiliary layer (A) in |±! ⟩⟨±! |-basis ⨁

Byproduct correction

….

….

Prepared in |+⟩ state

Prepared in 𝑅" 𝛼 |0⟩ state

FIG. 6. MBQC preparation of product input state. An auxiliary column A, initialized in |+⟩⊗N , is attached to the first computational column. Measuring each auxiliary qubit in the {|±α ⟩} basis and applying the corresponding byproduct correction prepares Rx (α)|0⟩ on every qubit of the first computational column, yielding |ψin ⟩ = (Rx (α)|0⟩)⊗N .

where Rx (α) = exp (−iαX/2). Because this state is separable, in the equivalent circuit picture, it can be prepared using local single-qubit rotations before the depth-2 entangling circuit. Its preparation therefore does not contribute to the circuit depth considered in the separation proof. The same input state can be prepared directly within the cluster-state construction. Consider an N ×(D +1) cluster state augmented by an auxiliary input column, denoted by column A in Fig. 6 (left panel). All qubits are initialized in |+⟩, and each auxiliary qubit is coupled by a CZ gate to the corresponding qubit in the first computational column
√ B in Fig. 6. The auxiliary qubits are then measured in the basis |±α ⟩ = |0⟩ ± e−iα |1⟩ / 2. For the measurement outcome sj ∈ {0, 1} on the auxiliary qubit associated with site j, the state teleported to the site j in the first computational column B is, up to an irrelevant global phase, HZ sj Rz (α)|+⟩ = X sj HRz (α)|+⟩ = X sj Rx (α)|0⟩.

(B48)

Applying the standard byproduct correction therefore prepares Rx (α)|0⟩ at site j in the computational layer B. Repeating this procedure independently for all j = 1, . . . , N prepares ⊗N

|ψin ⟩ = (Rx (α)|0⟩)

(B49)

on the first computational column. This construction is included solely to establish compatibility with the MBQC architecture and is not part of the depth-separation argument. Performing XY -plane measurements on the qubits in the computational layers implements, as shown in Sec. II C, the depth-2 unitary U (θ) =

2 Y

Ul (θl )

(B50)

l=1

where

Ul (θl ) = H ⊗N CZopen Rz (θl ),

CZopen :=

N −1 Y j=1

CZj,j+1 ,

Rz (θl ) :=

N Y

Rz (θjl ) = exp −iθjl Zj /2.

j=1

As discussed in Sec. II C 3, shared classical randomness can be generated in MBQC by choosing the feedforward rules such that the same effective measurement-outcome bit controls byproducts on spatially separated qubits. For instance, the same stochastic bit acts on the boundary qubits (1, 6) for a total N = 6 qubits in Fig. 7. We next show how these correlated byproducts produce an output distribution that belongs to the correlated-channel family but cannot be generated by the corresponding shallow unitary model. Corollary 18 (Shallow-depth separation using MBQC on a cluster state). Consider the VMBQC channel model Ẽc introduced in Sec. II C 4 in which the propagated Pauli byproducts are corrected before the final measurements. We implement this model on the N × 3 cluster state shown in Fig. 7 (a), with N ≥ 6, computational depth D = 2, and open boundary conditions. Suppose that the effective measurement-induced byproducts associated with the two 1 s1 boundary qubits, Z1s and ZN , in the first computational layer are controlled by the same binary variable s1 ∈ {0, 1}, 1 sampled according to Pr(s = 1) = p, with p ∈ (0, 1) (see Sec. II C 3).

27

(a)

𝑍!"

!

𝑋!"

!

(b) Final output state and covariance

⟨𝑍$! ⟩

1 1 𝜌$%&'( = 𝜌)*+, + 𝜌-*+, 2 2

&

𝜃!. → −1 / 𝜃!.

Non-vanishing Covariance

Stochastic angle-flips

Cov 𝑍"! , 𝑍"" #

&

𝜃". → −1 / 𝜃".

! 𝑍#"

! 𝑋#"

⟨𝑍$# ⟩

Prepared in 𝑅! 𝛼 |0⟩ state

!"#$%

Prepared in |+⟩ state

≠0

Prepared in |+⟩ state ⨁ angle-flip

FIG. 7. MBQC realization of the shallow-depth endpoint separation. (a) For illustration, we consider a 6 × 3 cluster state whose final column forms the readout layer. Classical feedforward is chosen so that the measurement-induced byproducts on the two boundary qubits of the first computational layer share the same binary variable s1 ∈ {0, 1}, yielding correlated 1 1 Z1s and Z6s . Propagating these byproducts through the subsequent layer induces correlated sign flips of the corresponding 1 1 out rotation angles, θ12 7→ (−1)s θ12 and θ62 7→ (−1)s θ62 . (b) Averaging over the two stochastic branches ρout + and ρ− corresponding 1 out + ρ , whose endpoint observables exhibit a to s1 = 0 and s1 = 1, respectively, gives the final output state ρfinal = 12 ρout + 2 − nonvanishing covariance, Cov(Ẑ1 , Ẑ6 )ρfinal ̸= 0. The white qubits are initialized in |+⟩, while the orange qubits are prepared in Rx (α)|0⟩. The blue qubits indicate the locations at which the shared byproduct induces the stochastic angle flips. This construction realizes the separation established in Corollary 18.

Let ρ(s1 ) denote the branch-conditioned output state corresponding to s1 ∈ {0, 1}. Then the averaged output state is E ⋆ := (1 − p)ρ(0) + pρ(1)

(B51)

Let Q⋆ be the computational-basis Born distribution of E ⋆ . For compactness, define cl,j := cos(θjl ) and sl,j := sin(θjl ). If the parameters of the model are chosen such that β := 4p(1 − p)s2,1 s2,N s1,1 c1,2 c1,N −1 s1,N sin4 (α) cos2 (α) ̸= 0,

(B52)

then the two boundary sites have nonzero covariance when measured in Ẑ basis, CovE ∗ (Ẑ1 , ẐN ) = β.

(B53)

Consequently, the infimum of the total variation distance between Q⋆ and the output distribution generated by the corresponding shallow unitary model satisfies
|β| inf TV Q⋆ , PU (θ) ≥ . θ 6

(B54)

In particular, the total variation bound above holds against every purely unitary model of depth 1 < D < N 2−1 under the cluster-state layer convention used above. Hence, when the boundary separation scales as Θ(N ), the required unitary depth scales as D = Ω(N ). Proof. Here, we consider the VMBQC Ẽc (θ, p) model as described in Sec. II C 4, in which all Pauli byproducts propagated to the end of the computation are corrected before the final measurement. Now consider the cluster state shown in Fig. 7 with N ≥ 6, and suppose that the boundary qubits in the first computational layer acquire 1 s1 the correlated measurement-induced byproducts Z1s and ZN , as described in Sec. II C 3. Using the commutation 1 1 relations given in Eq. (1) of Ref. [24], one can show that the Z1s byproduct becomes X1s in the second layer, and 1 1 1 therefore changes the corresponding measurement angle of the Rz (θ12 ) gate as X1s Rz (θ12 ) 7→ Rz ((−1)s θ12 )X1s . In the 1 1 1 next propagation step, X1s becomes Z1s X2s at the readout layer. Since these final Pauli byproducts are corrected 1 1 as shown in Sec. II C 4, the only remaining effect of Z1s is the intermediate sign change of θ12 7→ (−1)s θ12 . The same 1 1 s 2 2 argument applies to the other boundary byproduct ZN , whose only remaining effect is θN 7→ (−1)s θN .

28 2 Thus, for any N ≥ 6, the shared variable s1 changes only the two boundary angles θ12 and θN in the second 2 computational layer, and the rest of the {θj }j∈[2,N −1] remain unaffected as shown in Fig. 7 (with cluster state width N = 6). For the input state Rx (α)|0⟩, with Rx (α) = exp (−iαX/2), on each qubit, the relevant Bloch components are

⟨X⟩ = 0,

⟨Y ⟩ = − sin α,

⟨Z⟩ = cos α.

(B55)

Let’s consider the output state after the first layer in the unitary model ρ1 := U1 (θ1 )ρin U1 (θ1 )† .

(B56)

Now, we compute the branch-dependent endpoint responses. The Ẑ1 endpoint observable propagated backward (s1 ) through the second layer U2 (θ2 ) that depends on the branch s1 ∈ {0, 1} as (s1 )

U2

(s1 )

(θ2 )† Ẑ1 U2

(s1 ) †

(θ2 ) = Rz (θ2

(s1 )

) CZ†open X̂1 CZopen Rz (θ2

  1 ) = c2,1 X̂1 − (−1)s s2,1 Ŷ1 Ẑ2 .

(s1 )

1

(B57) 1

2 2 where θ2 denotes the set of measurement angles in the second layer with (θ12 , θN ) 7→ ((−1)s θ12 , (−1)s θN ), while 1 the rest of the angles remains unaffected by s . Hence, the branch-dependent final expectation value for Ẑ1 is 1

m1 (s1 ) := Tr[Ẑ1 ρ(s1 ) ] = c2,1 A1 − (−1)s s2,1 B1 ,

(B58)

A1 := Tr[(X̂1 Ẑ2 )ρ1 ],

(B59)

where B1 := Tr[(Ŷ1 Ẑ2 )ρ1 ].

Similarly, 1

mN (s1 ) := Tr[ẐN ρ(s1 ) ] = c2,N AN − (−1)s s2,N BN ,

(B60)

AN := Tr[(ẐN −1 X̂N )ρ1 ],

(B61)

where BN := Tr[(ẐN −1 ŶN )ρ1 ].

Direct Pauli propagation through the first cluster layer gives A1 = s1,2 sin α cos α,

B1 = −s1,1 c1,2 sin2 α cos α,

(B62)

BN = −c1,N −1 s1,N sin2 α cos α.

(B63)

and AN = s1,N −1 sin α cos α,

For each fixed branch ρ(s1 ) with fixed s1 , the endpoint backward light cones are disjoint for N ≥ 6, at depth D = 2. Since the input state is a product state, the branch-conditioned endpoint moment factorizes: Tr[Ẑ1 ẐN ρ(s1 ) ] = m1 (s1 )mN (s1 ). Therefore the averaged one-site responses are X Tr[Ẑ1 E ∗ ] = Pr(s1 )m1 (s1 ), s1 ∈{0,1}

Tr[ẐN E ∗ ] =

(B64)

X

Pr(s1 )mN (s1 ),

(B65)

s1 ∈{0,1}

and the averaged two-site response is Tr[Ẑ1 ẐN E ∗ ] =

X s1 ∈{0,1}

with this, we obtain

Pr(s1 )m1 (s1 )mN (s1 ).

(B66)

29

CovE ∗ (Ẑ1 , ẐN ) = Tr[Ẑ1 ẐN E ∗ ] − Tr[Ẑ1 E ∗ ] Tr[ẐN E ∗ ] = 4p(1 − p)s2,1 s2,N B1 BN = 4p(1 − p)s2,1 s2,N s1,1 c1,2 c1,N −1 s1,N sin4 α cos2 α = β.

(B67) (B68) (B69) (B70)

Thus, β ̸= 0 implies that the two boundary outcomes have nonzero covariance. By Lemma 10, their computationalbasis marginal therefore cannot factorize into the product of its single-qubit marginals. By contrast, consider the corresponding purely unitary model obtained from MBQC on the same cluster state as in Fig. 7 by fully adapting all the measurement outcomes. This removes the stochastic correlated Pauli byproducts and yields the unitary circuit U (θ) in Eq. (B50) associated with the cluster-state computation. For the depths under consideration, the backward light cones of the two boundary measurements are disjoint. Thus, according to Lemma 10 one can write CovρU (Ẑ1 , ẐN ) = 0.

(B71)

Consequently, the computational-basis marginal on the two boundary qubits factorizes into the product of its singlequbit marginals. Applying the covariance–total-variation bound (see Lemma 14) to the two endpoint marginals Q⋆1,N and P1,N for the channel and unitary model respectively,
1 |β| CovE ∗ (Ẑ1 , ẐN ) − CovρU (Ẑ1 , ẐN ) = . TV Q⋆1,N , P1,N ≥ 6 6

(B72)

Since total variation cannot increase under marginalization,

|β| inf TV Q⋆ , PU (θ) ≥ inf TV Q⋆1,N , P1,N ≥ . θ θ 6

(B73)

β is maximized in absolute value by choosing the angle factors to have unit magnitude, namely |s2,1 | = |s2,N | = |s1,1 | = |s1,N | = 1,

|c1,2 | = |c1,N −1 | = 1.

(B74)

Thus the remaining optimization is over f (α) := sin4 α cos2 α. Writing x = sin2 α, we have f (α) = x2 (1 − x),

x ∈ [0, 1].

(B75)

4 The maximum occurs at x = 23 , i.e., sin2 α = 32 , cos2 α = 13 , and gives maxα sin4 α cos2 α = 27 . Therefore, for fixed 16 p, |β|max = 27 p(1 − p). If one also optimizes over the branch probability, the maximum is attained at p = 1/2, giving

|β|max =

4 . 27

(B76)

Therefore no such purely unitary local circuit can reproduce Q⋆ . For the cluster-state layer convention used here, each layer expands an endpoint backward light cone by at most one site, and thus the endpoint backward light cones are disjoint whenever D < (N − 1)/2. Therefore, if the endpoint distance is Θ(N ), any purely unitary nearest-neighbor realization requires depth D = Ω(N ). The above proof applies to a cluster state with open boundary conditions, but it can be extended to periodic boundary conditions as well.

Appendix C: Distribution classes

This appendix clarifies the structured target family of distributions used in the main text. They are not intended to characterize the full expressive power of the channel model. Rather, they isolate simple distributional structure that are naturally produced by shared branch randomness.

30 1.

Branch-peaked mixture distributions

A branch-peaked mixture distribution has the form X P (x) = π(s) [δs 1[x = x⋆s ] + (1 − δs )Rs (x)] ,

x ∈ {0, 1}N ,

(C1)

s∈S

where S ⊆ {0, 1}L is a finite set satisfying |S| ≤ Smax , with Smax = O(1) is independent of N . Here, π(s) ≥ 0 is the probability of the corresponding branch s with X π(s) = 1, (C2) s∈S

δs ∈ (0, 1], and x⋆s ∈ {0, 1}N is the dominant bit string associated with branch s. Each Rs is a normalized residual distribution on {0, 1}N and is allowed to depend on the branch. The residual Rs describes the probability mass of branch s away from its dominant bit string. More explicitly, suppose the output distribution of branch s is Ps . If x⋆s is chosen as a dominant bit string of Ps and δs := Ps (x⋆s ), then, for δs < 1, one can write Ps (x) = δs 1[x = x⋆s ] + (1 − δs )Rs (x),

(C3)

  x = x⋆s , 0, Rs (x) = Ps (x)   , x= ̸ x⋆s . 1 − δs

(C4)

with

This makes Rs a normalized distribution: X

Rs (x) =

x∈{0,1}N

X 1 Ps (x) = 1. 1 − δs ⋆

(C5)

x̸=xs

P Thus Eq. (C1) is simply the branch average P = s∈S π(s)Ps written in a way such that the dominant contribution of each branch is explicitly separated from the remaining branch-dependent fluctuations, which is denoted as the residual distribution Rs associated with branch s. When δs = 1, the branch is a point mass at x⋆s , and the residual term does not contribute. To use this as a nontrivial peaked class, one should assume a peaked regime, for example δs ≥ δmin > 0,

Rs (x⋆s ) = 0,

for all s ∈ S.

(C6)

An explicit example of such a distribution is provided in Eq. (62). This class is naturally suited to the correlated channel learning model, in which shared randomness, in the form of stochastic Pauli strings, appears in the middle of the circuit as shown in Eq. (A11) and in Appendix D. In those cases, the sampled branch can change the effective circuit evolution, so different branches may have different dominant bit strings and different residual shapes. Appendix D: Correlated channel model with Pauli-correction

As a concrete realization of the learning model with shared randomness in Sec. II B, we consider the MBQC resource state shown in the left panel of Fig. 8. With an appropriate choice of adaptive single-qubit projective measurements, this resource state implements the one-dimensional nearest-neighbor circuit with open boundary conditions shown in the right panel. The single-qubit rotations in each circuit layer are realized using standard XY -plane MBQC measurement patterns [21], while the two-qubit Rzz rotations are implemented using appropriate graph-state gadgets involving Y Z-plane measurements [45, 46]. Moreover, as described in Sec. II C 3, after collecting the measurement outcomes from layer l of the resource state, classical feedforward can be used to implement correlated stochastic Pauli operations on a subset of qubits in that layer, controlled by a single shared random variable. Each layer in the corresponding induced circuit can be written as Uk (θk ) =

N O i=1

Rx (θik,x )

N O i=1

Rz (θik,z )

N −1 Y i=1

k,zz Rzz (θi,i+1 )

(D1)

31

Corresponding quantum circuit

Two distant correlated qubits

Whole layer repeats without the correlation

Measured in 𝑋𝑌- Plane

𝑍!"

!

𝑅' (𝜃"",' )

𝑅! (𝜃$",! )

𝑅' (𝜃$",' )

𝑅! (𝜃&",! )

𝑅' (𝜃&",' )

……

", !! 𝑅!! (𝜃(*",( )

Input state

𝑅! (𝜃"",! )

", !! 𝑅!! (𝜃$,& )

𝛼 ⊗"

", !! 𝑅!! (𝜃&,) )

", !! 𝑅!! (𝜃",$ )

S" ∼ 𝐵𝑒𝑟𝑛𝑜𝑢𝑙𝑙𝑖(𝑝" )

Implements

……

All qubits are initialized in |+⟩ state

Resource state for QML

𝑅! (𝜃(",! )

!

𝑍#"

𝑅' (𝜃(",' )

……

Measured in ±$ ⟨±$ | basis

Measured in 𝑌𝑍- Plane

FIG. 8. Resource state and learning model: The left panel shows an open-boundary graph-state resource, where vertices represent qubits and edges denote CZ entangling gates. All resource qubits are initialized in |+⟩ and subsequently measured in the color-coded basis indicated in the legend. Measuring the qubits within the dashed region implements one layer of the circuit shown on the right, consisting of nearest-neighbor Rzz gates, local Rz rotations, a correlated stochastic Z-byproduct layer, and local Rx rotations. Repeating the dashed graph pattern generates additional circuit layers. Classical feedforward is chosen so that the two distant boundary qubits, in the dashed box, share the same effective byproduct bit s1 ∈ {0, 1}, with Pr(s1 = 1) = p1 ∈ [0, 1] as described in Sec. II C 3. Consequently, the measurement-induced byproducts either occur jointly or 1 s1 are both absent, corresponding to the stochastic Pauli string Z1s ⊗ ZN , at the designated location in the circuit picture. The input-measurement pattern prepares the effective circuit input state |α⟩⊗N , where |α⟩ = Rx (α)|0⟩ and α ∈ / π2 Z.

with layer parameter vector   k,z N k,zz N −1 θk = {θik,x }N . i=1 , {θi }i=1 , {θi,i+1 }i=1

(D2)

For a chosen insertion point associated with layer l, we decompose the ordered circuit as U (θ) = U>l (θ)U≤l (θ),

(D3)

where U≤l and U>l denote the circuit portions before and after the insertion slot, respectively. We sample a shared bit sl ∈ {0, 1} with Pr(sl = 1) = pl and insert the stochastic Pauli string O l sl sl PM = ZM := Zjs , (D4) j∈M l

s at this slot, where M ⊆ [1, N ]. Propagating ZM through the remaining Pauli rotations induces branch-dependent sign flips of the angles whose generators anticommute with ZM , while leaving the Pauli string itself unchanged. After sl † applying the final Pauli correction P̂ (s)† = (ZM ) as described in Sec. II C 4 and shown in Fig. 9, the corrected branch unitary becomes l

l

l

s s U (s ) (θ) = ZM U>l (θ)ZM U≤l (θ)

(D5)

l

s Now, the final ZM before measurements does not alter the computational-basis measurement outcomes. Thus, it can be omitted at the level of the computational-basis output probabilities. The resulting channel, for input state ρin = (|α⟩⟨α|)⊗N with |α⟩ = Rx (α)|0⟩, and α ∈ / π2 Z, is

Eθ,pl (ρin ) =(1 − pl )U (0) (θ)ρin U (0) (θ)† + pl U (1) (θ)ρin U (1) (θ)† ,

(D6)

32

(a) Model with stochastic Pauli-string

(b) Model with stochastic flipped angles

𝑠 ! ∼ 𝐵(𝑝! )

𝛼 ⊗"/ 𝑈!" (𝜃) 𝑃 $! #

𝑈%" (𝜃)

𝛼 ⊗"/

!

𝑃#$

𝑈!" (𝜃)

𝑈%" (𝜃' )

FIG. 9. Learning model with Pauli correction: Consider the unitary model with total D layers where each layer consists of Pauli rotations as parameterized gates of the form exp(−iθQi,i+1 ), acting on two qubits, where Q ∈ {I, X, Y, Z}⊗2 . (a) A N sl stochastic Pauli string PM , where PM = j∈M Pj , Pj ∈ {X, Z}, M ⊆ [1, N ], controlled by a shared variable sl ∼ Bernoulli(pl ), is inserted after layer l. The same sl -dependent Pauli string is applied again at the output, with sl = 0 corresponding to the identity and sl = 1 to PM . (b) Propagating the inserted Pauli string through U>l (θ) leaves commuting gates unchanged and l sl sl flips the signs of the angles of anticommuting Pauli rotations. Specifically, PM exp(−iθQi,i+1 ) = exp(−i(−1)s θQi,i+1 )PM if sl sl 2 [PM , Qi,i+1 ] ̸= 0. The propagated Pauli string then cancels the final correction because (PM ) = I. The resulting branch is e ≤l (θ) with branch-dependent sign-flipped angles θ 7→ θ. e therefore equivalent to the purely unitary circuit U>l (θ)U

and measurement in the computational Z basis produces output distribution   PEθ,pl (x) = Tr |x⟩⟨x|Eθ,pl (ρin )

(D7) 1

1

1

s s In Fig. 8 (right), we choose l = 1, and M = {1, N }. We deliberately place the stochastic Pauli string PM = Z1s ⊗ZN NN k,x in the first layer before the sub-layer i=1 Rx (θi ). Propagating this string through the remaining circuit induces 1 the correlated angle flips of the corresponding Rx angles, θ 7→ (−1)s θ, while leaving the Rz and Rzz rotations unchanged. Since the final byproduct remains diagonal in the computational basis, it does not alter the sampled bit 1 s1 s1 string and need not be physically corrected. By contrast, choosing XM = X1s ⊗ XN flips the angles of subsequent Rz s1 and Rzz rotations whose generators anticommute with XM . Since the final XM byproduct flips the corresponding computational-basis outputs, it is removed using the final Pauli correction shown in Fig. 9 and described in Sec. II C 4. In both cases, the retained stochastic effect is the correlated branch-dependent angle-flip pattern rather than an output bit-flip map or classical post-processing.

Appendix E: Numerical details 1.

Gradient of the loss function

In this section, we derive the gradient of the squared MMD loss in Eq. (52) with respect to the application probabilities {pi }L i=1 . The output distribution of the channel model, in Eq. (18), can be rewritten using Eq. (16) as X X PEθ,p (x) = πp (s) ⟨x| U (s) (θ)ρin U (s) (θ)† |x⟩ = πp1 (s1 ) · · · πpL (sL )Pθ (x|s1 , · · · , sL ) (E1) si ∈{0,1} i∈{1,··· ,L}

s∈{0,1}L

i

i

where s = (s1 , . . . , sL ) ∈ {0, 1}L and πpi (si ) = (pi )s (1 − pi )1−s and Pθ (x | s) = ⟨x|U (s) (θ)ρin U (s) (θ)† |x⟩ is the output probability of bitstring x conditioned on the branch s. For each random variable sl ∈ {si }L i=1 ( 0 with probability 1 − pl , sl = 1 with probability pl . Thus, for any variable sl , Eq. (E1) can be written as

(E2)

(E3)

33

PEθ,p (x) =

(E4)   Y  πpi (si ) Pθ (x|s1 , · · · , 1, · · · , sL )+

X

pl · i

s , i∈{1...L}, i̸=l

  Y  πpi (si ) Pθ (x|s1 , · · · , 0, · · · , sL )

X

(1 − pl )

(E5)

i̸=l

i

(E6)

i̸=l

s , i∈{1...L}, i̸=l

The rest of the calculation remains the same as in Appendix B of Ref. [14]. This gives the final gradient as ∂L =2 [K(x, y)] − 2 [K(x, y)] E E ∂pl x∼PE (l,1) x∼PE (l,0) θ,p

θ,p

y∼PEθ,p

y∼PEθ,p

−2

[K(x, y)] + 2

E

x∼PE

y∼Y

[K(x, y)],

E

x∼PE

θ,p(l,1)

(E7)

θ,p(l,0)

y∼Y

where p(l,1) and p(l,0) denote the parameter vector p = (p1 , . . . , pL ) with pl replaced by 1 and 0, respectively. Here, Y is the target distribution. Hence, the gradient with respect to pl can be estimated by evaluating the model twice: once with pl = 1 and once with pl = 0, while keeping all other parameters fixed. The gradients with respect to the variational angles θ ∈ θ can be evaluated using standard parameter-shift rules for parametrized Pauli rotations [6, 14] as ∂L = [K(x, y)] − [K(x, y)] E E ∂θjl x∼PE + x∼PE − θ ,p θ ,p y∼PEθ,p

−

y∼PEθ,p

[K(x, y)] +

E

x∼PE + θ

y∼Y

,p

[K(x, y)]

E

x∼PE − θ

(E8)

,p

y∼Y

Here, PEθ+ ,p and PEθ− ,p are the output distributions of the channel model with parameters θ ± = θ ± π2 elj and elj is a vector with a 1 at position (l, j) and 0s elsewhere. The parameter shifting is done for each angle individually, while the other angles remain unchanged. For the unitary model, to estimate the gradient of the variational angles we set p = 0 as PU (θ) ≡ PEθ,p=0 . Eq. (E7) and (E8) can be used to compute the gradient of the learning model defined in Sec. II B.

2.

Box plot details

Each box plot in Fig. 5 summarizes the minimum MMD losses obtained from 20 independent training runs. The losses are first ordered from smallest to largest. The lower and upper boundaries of the box are the first and third quartiles, denoted by Q1 and Q3 . Thus, approximately 25% of the observations lie below Q1 , approximately 50% lie between Q1 and Q3 , and approximately 25% lie above Q3 . The box therefore represents the central 50% of the training outcomes, corresponding approximately to 10 of the 20 runs. The interquartile range, IQR = Q3 − Q1 , measures the spread of the central half of the data and is less sensitive to extreme values than the full range. The lower whisker extends to the smallest observed loss that is not below Q1 −1.5 IQR, while the upper whisker extends to the largest observed loss that is not above Q3 +1.5 IQR. Observations outside these limits are displayed individually as outliers (white circles). In a standard box plot, the horizontal line inside the box denotes the median, which separates the lower and upper halves of the data. In Fig. 5, the median is shown with the orange line.

Related documents

• Observation of Universal Quantum Chaos at Shallow Depths#1076279
• Provably Efficient Learning of Fermionic Correlations under Particle-Number Symmetry#1144836
• Dephasing-Enhanced Response and Phase Transitions in Quantum Boltzmann Samplers#1014181
• Displacement Geometry Captures Platonic Shared Reality Across Models and Modalities#1050392
• Revisiting Spectral Representations in Generative Diffusion Models#985624