# First radiative shock experiments on the SG-II laser

Francisco Suzuki-Vidal<EMAIL_ADDRESS>Blackett Laboratory, Imperial
College London, London SW7 2BW, UK  Thomas Clayson  First Light Fusion Ltd.,
Yarnton OX5 1QU, UK  Current affiliation: Magdrive Ltd, Harwell OX11 ORL, UK
Chantal Stehlé  LERMA, Sorbonne-Université, Observatoire de Paris, CNRS,
France  Uddhab Chaulagain  ELI Beamlines Center, Institute of Physics, Czech
Academy of Sciences, Za Radnici 835, Dolni Brezany, Czech Republic  Jack W.D.
Halliday  Blackett Laboratory, Imperial College London, London SW7 2BW, UK
Mingying Sun  Shanghai Institute of Optics and Fine Mechanics, Chinese Academy
of Sciences, China  Lei Ren  Shanghai Institute of Optics and Fine Mechanics,
Chinese Academy of Sciences, China  Ning Kang  Shanghai Institute of Optics
and Fine Mechanics, Chinese Academy of Sciences, China  Huiya Liu  Shanghai
Institute of Optics and Fine Mechanics, Chinese Academy of Sciences, China
Baoqiang Zhu  Shanghai Institute of Optics and Fine Mechanics, Chinese Academy
of Sciences, China  Jianqiang Zhu  Shanghai Institute of Optics and Fine
Mechanics, Chinese Academy of Sciences, China  Carolina de Almeida Rossi
Blackett Laboratory, Imperial College London, London SW7 2BW, UK  Teodora
Mihailescu  Blackett Laboratory, Imperial College London, London SW7 2BW, UK
Pedro Velarde  Instituto de Fusión Nuclear Guillermo Velarde, Universidad
Politécnica de Madrid, 28006 Madrid, Spain  Manuel Cotelo  Instituto de Fusión
Nuclear Guillermo Velarde, Universidad Politécnica de Madrid, 28006 Madrid,
Spain  John M. Foster  AWE plc., Aldermaston, Reading, Berkshire RG7 4PR, UK
Colin N. Danson  AWE plc., Aldermaston, Reading, Berkshire RG7 4PR, UK
Christopher Spindloe  Science and Technology Facilities Council, Rutherford
Appleton Laboratory, Harwell Campus, Chilton, Didcot, Oxon OX11 0QX, UK
Jeremy P. Chittenden  Blackett Laboratory, Imperial College London, London SW7
2BW, UK  Carolyn Kuranz  University of Michigan, Ann Arbor, MI 48109, USA

###### Abstract

We report on the design and first results from experiments looking at the
formation of radiative shocks on the Shenguang-II (SG-II) laser at the
Shanghai Institute of Optics and Fine Mechanics in China. Laser-heating of a
two-layer CH/CH-Br foil drives a $\sim$40 km/s shock inside a gas-cell filled
with argon at an initial pressure of 1 bar. The use of gas-cell targets with
large (several mm) lateral and axial extent allows the shock to propagate
freely without any wall interactions, and permits a large field of view to
image single and colliding counter-propagating shocks with time resolved,
point-projection X-ray backlighting ($\sim 20$ $\mu$m source size, 4.3 keV
photon energy). Single shocks were imaged up to 100 ns after the onset of the
laser drive allowing to probe the growth of spatial non-uniformities in the
shock apex. These results are compared with experiments looking at counter-
propagating shocks, showing a symmetric drive which leads to a collision and
stagnation from $\sim$40 ns onward. We present a preliminary comparison with
numerical simulations with the radiation hydrodynamics code ARWEN, which
provides expected plasma parameters for the design of future experiments in
this facility.

##  I Introduction

Radiative shocks are formed when radiative losses from the shock can modify
its structure. This occurs when the radiative energy flux is comparable to the
kinetic energy flux at the shock front. In this regime, radiation can modify
both the pre- and post-shock regions. Radiative effects increase with the
shock speed due to stronger post-shock heating and, in a first approximation
for typical experimental conditions, radiative effects start playing a role at
shock velocities of 10$-$100’s km/s and gas pressures of $\sim$0.1$-$1 bar
[Drake (2005)]. With present day laser facilities it is possible to reach such
shock speeds by compressing and focusing the laser energy into a solid (e.g. a
piston) or gas target. This has been done in a number of different laser
facilities with a variety of energies, intensities (typically $\gtrsim$ 1014
W/cm2) and configurations, e.g. point-explosions in a gas background, shock
tubes and gas-cells (a recent review can be found in [Drake (2019)]).

Recent works have looked at bridging the gap between experiments and
theory/numerical simulations of radiative shocks [Mabey  _et al._ (2020)] and
applications to astrophysics [Mabey  _et al._ (2020)]. In particular, recent
experiments have looked at the interaction of a piston driven shock with an
obstacle [Michel  _et al._ (2018), Michel  _et al._ (2019)]. However, several
issues have lead to difficulties to make a complete bridge between simulation
and experiments, for instance the question of opacity for heavy gases (e.g.
xenon) or the nature of the rise of instabilities and the role played by
radiation. In addition, at higher velocity, temperature increases strongly and
non-LTE effects start to play a role [Rodríguez  _et al._ (2015)]. It is,
therefore, of key importance to continue experimental efforts to obtain more
experimental data to be compared with theoretical works.

The experiments presented here use the Shenguang-II (SG-II) laser to drive
shocks via piston-action from a foil attached to one of the ends of a gas-cell
target. Although the SG-II laser has been operational for many years, future
improvements planned for this facility in the coming years make these first
experiments critical for planning and testing of future experimental
campaigns.

The targets are characterised by a large internal volume and field of view to
probe the dynamics of the shock as a function of time without any shock-wall
interactions. This configuration is similar to first experiments performed on
the Orion laser, where shocks were driven in xenon [Suzuki-Vidal  _et al._
(2017)] and neon [Clayson  _et al._ (2017)] with similar laser energies and
gas pressures. However, the SG-II targets have a larger diagnostic field
compared to the Orion experiments and, through the use of argon, we aim to
study the formation of spatial non-uniformities in the shocks which were only
investigated preliminarily at Orion.

Figure 1: (a) Schematic diagram of the experimental setup for a single shock
target on the SG-II laser, with a similar configuration used for counter-
propagating shocks. (b)-(c) Cross-section of single and counter-propagating
shock targets.

##  II Experimental setup

The SG-II laser [Zhu  _et al._ (2018)] can drive up to eight beams with a
pulse duration of 1 ns in two opposite directed groups of four beams. Thus,
four to eight beams were used depending on whether the experiment was aimed at
producing single or counter-propagating shocks. The overall experimental setup
is shown schematically in Fig. 1a for a single shock target. The targets are
similar for the case of counter-propagating shocks, where 4 additional beams
are focused on a second piston placed opposite to the first one. Detailed
dimensions for both types of targets are shown in Figs. 1b-c.

The lasers driving each shock had a total energy of $\sim$1 kJ, a top-hat
temporal profile with a duration of $\sim$1 ns and a frequency of 3$\omega$
($\lambda$ = 351 nm). The laser beams were focused to a nominal spot diameter
of $\sim$300 $\mu$m with a super-Gaussian spatial profile with $n\sim 4-6$.
Measured laser parameters for the experiments are presented in the Results
section. An external laser beam (the $9^{th}$ beam) was used to drive X-ray
backlighting onto a scandium foil to image the shock inside the gas-cell side-
on, i.e. normal to the direction of propagation of the shock. The backlighter
beam had an energy $E_{9th}\sim 500$ J and a pulse duration of $t_{9th}\sim 1$
ns, with a spot size of $\phi_{9th}\sim 150$ $\mu$m at $3\omega$. In addition
to the X-ray backlighter diagnostic, a filtered, time-integrated pinhole
camera recorded the X-ray emission from the laser-piston interaction onto an
image plate to estimate the size of the focal spot during each shot. An
example of results from the two diagnostics is presented in Fig. 2.

###  II.1 Target design

Gas-cell targets were designed for SG-II with two main purposes: 1) To provide
a large ambient gas volume in order to allow the shocks to propagate without
being subject to radiative or hydrodynamic interactions with the gas cell-
walls, 2) To maximize the X-ray backlighter diagnostic field of view in order
to follow the evolution of the shocks for times up to 100 ns.

Two target designs (Fig. 1b) were fielded on SG-II: A single-shock target with
a diagnostic window size (width$\times$height) of 6$\times$5 mm2, and a
counter-propagating shock target with a diagnostic window size of 3.6$\times$5
mm2. The window width of the counter-propagating shock targets was constrained
by the maximum separation between the two opposite groups of long-pulse laser
beams, i.e. 4 mm between focal spots. The gas-cell windows were sealed with a
25 $\mu$m thick polyimide foil, with a transverse distance between windows of
8 mm. The targets were positioned inside the chamber with a 3 mm diameter
plastic rod glued at the top of each target, connected to a 5-axis target
positioner.

The targets for SG-II were designed based on previous experiments on the Orion
laser [Spindloe  _et al._ (2017)], with several improvements implemented for
SG-II: 1) a thinner, 0.2 mm thick frame between the piston and the edge of the
diagnostic window to probe the early-time behaviour of the shock (cf. 1 mm for
Orion). A drawback of decreasing the frame thickness was that this reduced the
shielding which the target provided to prevent hard X-ray emission from the
laser-piston interaction from contaminating the signal on the X-ray
backlighter diagnostic. This meant the level of background noise in diagnostic
images from these experiments was higher than the level observed previously on
Orion. 2) A smaller, 1 mm diameter aperture for the piston was in contact with
the gas (cf. 3$-$5 mm in Orion) to reduce the ‘swelling’ of the piston with
gas-fill pressure inside the vacuum chamber. This aids to achieve a more
consistent laser focal spot size during each shot. 3) Lastly, the SG-II
targets were gas-filled in situ while inside the vacuum chamber, allowing for
a faster shot turnaround and accurate gas-pressure measurement right before
each shot. This gas-fill system was also used in previous experiments on the
PALS laser [Chaulagain  _et al._ (2015), Singh  _et al._ (2017)]. For the
experiments presented here, argon with an initial gas pressure of $P_{Ar}$=1
bar was used ($\rho_{Ar}$=1.67 mg/cc).

The pistons for SG-II were made with a layer of 30 $\mu$m thick CH (on the
laser-drive side, $\phi\sim 3.2$ mm diameter, nominal mass density
$\rho_{CH}$=0.9 g/cc) followed by a 50 $\mu$m thick CH-Br layer (on the gas
side, diameter $\phi\sim 2$ mm, nominal mass density $\rho_{CH-Br}$=1.53
g/cc). The brominated plastic layer helped shielding the gas from X-rays
produced in the laser-CH interaction in order to reduce radiative pre-heating.

Figure 2: (a)-(c) View of the piston: (a) X-ray emission from the laser-piston
interaction from a time-integrated pinhole camera diagnostic. (b) Microscope
image of the 1 mm diameter shock aperture and CH-Br / CH pistons. (c) Lineout
of (a) and Gaussian fit to estimate the laser spot size. (d)-(e) Target view:
Field of view of the X-ray backlighting diagnostic of a single shock target
and example of raw X-ray image result respectively.

###  II.2 X-ray backlighter diagnostic

A point-projection X-ray backlighter (XRBL) package was attached to the side
of each target. It consisted of a 5 $\mu$m thick, 500 $\mu$m diameter scandium
foil (a ‘microdot’) which was supported on a 100 $\mu$m thick tantalum
substrate, glued to a 3-D printed acrylic frame that was aligned to the center
of the gas-cell window. The X-ray source size was constrained by a
$\phi_{PH}=$20 $\mu$m diameter pinhole which was laser-cut into the Ta
substrate. This pinhole was coated with a 9 $\mu$m Parylene-N layer which
served to prevent the closure of the pinhole by the plasma which was formed in
the interaction between the backlighter beam and the Sc foil [Kuranz  _et al._
(2006)]. Laser etched markings were added to the Ta substrate and the Sc foil
to ensure accurate alignment during target manufacture and target alignment
before each shot.

The backligher beam average laser parameters were an energy of $E_{9th}=478\pm
71$ J and pulse duration $t_{9th}=1042\pm 188$ ps. The nominal spot size was
$\sim$150 $\mu$m, giving an intensity of $I_{9th}\sim 2.6\times 10^{15}$
Wcm-2. Under these drive conditions, the X-ray emission from the interaction
of the backlighter beam with the Sc foil is dominated by He-alpha emission
with a photon energy of 4.3 keV [Ruggles  _et al._ (2003)], providing a quasi-
monoenergetic source of X-rays to study the plasma in the shocks. The X-rays
were recorded in a film-pack with Fuji BAS-TR image plate, filtered with a
12.5 $\mu$m thick titanium filter and 2$-$3 layers of 8 $\mu$m thick
aluminised polypropylene for optical and debris shielding. The XRBL package
was placed at a distance of $p=21$ mm from the axis of the gas-cell, with the
image plate placed at a typical distance of $q\approx 226$ mm, thus resulting
in a point-projection magnification of $M=(p+q)/p\approx$12.

The spatial resolution of the XRBL was estimated by illuminating a vanadium
grid attached to a target and fitting the resulting spatial profile to the
convolution of the ideal point projection from the grid with a Gaussian
function. This results in a resolution of $\sim 19$ $\mu$m, which is
compatible with the size of the pinhole ($\phi_{PH}=20$ $\mu$m) and the
geometrical resolution given by $\delta\approx\phi_{PH}(M-1)/M\sim$18 $\mu$m
[Sinars  _et al._ (2004)]. The field of view of the XRBL diagnostic for a
single shock target together with an example of results is shown in Fig. 2d-e.
It should be noted that for the shock speed of $\sim$40 km/s, the motion
blurring for a 1 ns exposure XRBL is $\sim$40 $\mu$m, about twice the size of
the pinhole.

##  III Results

Results from single and colliding radiative shock experiments are presented in
Figs. 3a-b respectively. Each image was obtained from a different shot with
similar initial conditions for the laser drive and gas-fill pressure. Overall,
the results showed good shot-to-shot reproducibility for the shock dynamics.
Average laser-drive parameters in these experiments were an energy of
$E_{laser}=960\pm 53$ J and a pulse duration of $t_{laser}=1039\pm 63$ ps. The
spot size was estimated from the full-width half-maximum of Gaussian fits from
X-ray self-emission recorded with the time-integrated pinhole camera (Fig.
2c), resulting in an oval spot with size $\phi_{laser}\approx 424\pm 11\times
324\pm 15$ $\mu$m (width$\times$height), thus an average laser intensity of
$I_{laser}\sim 8.6\times 10^{14}$ Wcm-2. The laser intensity could be lower
than this measured value due to the spot size images being time-integrated.

Dark spots in the images are due to debris reaching the image plate, which
appear to be more pronounced in the case of colliding shocks. The XRBL results
were characterised by vertical bands with abrupt changes in X-ray intensity
which are attributed to background X-ray emission coming from the laser-piston
interaction (see the right side of Fig. 2e). These artefacts were removed from
the images in Fig. 3 by subtracting the average intensity distribution from
regions where the shock was not present. Future experiments will look at
reducing debris and background emission on the image plate by adding extra
shielding on the targets.

Fig. 3a shows the results for a single shock for times between 20$-$100 ns,
with each image corresponding to a separate experiment with nominally
identical initial conditions. The shocks show a semi-hemispherical shape with
a good degree of axial symmetry, i.e. respect to a height of 0 mm in the
window. In the earliest image, at 20 ns, the shock front is seen as a fairly
smooth feature, however from 40 ns onwards the shock develops spatial non-
uniformities which grow in size as time increases. Rough wavelengths of these
features are $\lambda\sim 250$ $\mu$m at 80 ns and $\lambda\sim 500$ $\mu$m at
100 ns.

Fig. 3b shows the results for two colliding shocks in a counter-propagating
configuration. Before and after the collision, the two shocks show a good
degree of left-right symmetry and thus demonstrate a well controlled laser
drive and a consistent target fabrication procedure. These results show
similar dynamics to previous experiments on the Orion laser using xenon at the
same initial gas mass density ($\rho_{Xe}\sim$1.6 mg/cc) [Suzuki-Vidal  _et
al._ (2017)], thus proving that is possible to carry on and improve similar
experiments of this type in SG-II in the future.

Figure 3: X-ray backlighting results for (a) single and (b) colliding shocks.
Artefacts from hard X-ray background (see Fig. 2e) have been removed for
visual purposes. For colliding shocks, the position is taken relative to the
left-hand side piston and the vertical arrows mark the approximate position of
the shock fronts in each frame. The arrows suggest that the shocks
interpenetrate however, in reality, the experiments are in a collisional
regime where no interpenetration occurs. Figure 4: Shock front position as a
function of time measured from the results in Fig. 3 for single and colliding
shocks. For the latter, the positions of the shock fronts are marked in Fig.
3b with matching colours.

Fig. 4 shows the position of the tip of the shock fronts with respect to the
initial position of the piston for single and colliding shocks, measured from
the data shown in Fig. 3. For visual purposes, the position of the shocks is
marked at 40, 50 and 60 ns as if the shocks interpenetrated, however the argon
plasma in the shocks is expected to be in the collisional regime as the ion
mean free path of argon is $\lambda_{mfp}\lesssim 1$ $\mu$m [Park  _et al._
(2012)]. This is estimated from plasma parameters from initial simulations
presented later in the paper together with an estimate of the average
ionization of argon for these parameters from [Espinosa  _et al._ (2017)].
Fig. 4 shows that the shock front position is fairly indistinguishable between
single and colliding shocks up until 40 ns, i.e. right at the time of the
collision. The collision leads to the stagnation of the shocks which is
supported by the ram pressure of the piston material behind the shock front.
For a single shock, a linear fit of the shock position as a function of time
results in a velocity of $V_{shock~{}front}\sim 39$ km/s.

To complement the experimental results, preliminary numerical simulations of
the experiments are presented in Fig. 5 for single shock at 20 ns. The
simulations were performed with the 2-D radiative hydrodynamics code ARWEN
[Ogando and Velarde (2001), García-Senz  _et al._ (2019)]. A full comparison
with the experimental data requires further testing of these simulations with
several initial conditions, thus this single output is used to infer
characteristic plasma conditions and make first estimates and further work
will look at presenting a detailed simulation study. These first simulations
were obtained using the initial conditions in the experiments, i.e. an initial
argon pressure of $P_{0}=1$ bar ($\rho_{0}=1.67$ mg/cc), a laser drive energy
of $E_{laser}=962$ J, a duration of $t_{laser}=1$ ns and a focal spot of
diameter $\phi_{laser}=370$ $\mu$m. The resolution of the simulations was 7
$\mu$m.

Fig. 5 shows 2-D maps of mass density and temperature together with axial (at
a radius of r=0 mm) lineouts of these quantities together with materials and
ionisation. The profiles of density, temperature and ionisation are
representative of the typical structure of a radiative shock: a sharp jump in
temperature and density at the shock front position (shown as a vertical
dashed line at $\sim$1.79 mm), followed by a decrease in temperature and an
increase in density post-shock, which we identify as the cooling region. The
post-shock region extends for $\sim$20 $\mu$m with a characteristic mass
density of $\rho_{post-shock}\sim 12-15$ mg/cc resulting in a density jump of
$\rho_{post-shock}/\rho_{0}\sim 12/1.67\sim 7$, of the order of the density
jump of 4 expected for a strong shock. The profile of materials post-shock
shows a mixing region of CH-Br and Ar extending up to $\sim$1.77 mm. The
temperature in the shock peaks at $T\sim 20$ eV, and the temperature profile
is characterised by a pre-heating region ahead of the shock with $T\sim 2-5$
eV, which can be identified as the radiative precursor.

Figure 5: Numerical simulations of the experiments with the 2-D radiation
hydrodynamics code ARWEN at 20 ns. (a) Maps of mass density and temperature.
(b) Axial lineouts (at a radius of 0 mm) of mass density, temperature,
materials and ionization from (a).

##  IV Discussion and conclusions

We have presented first results from experiments looking at the formation of
radiative shocks in argon with piston-driven gas-cells on the SG-II laser. The
main diagnostic fielded was point-projection X-ray backlighting which,
combined with a new gas-cell design, allowed the study of shock evolution for
single and counter-propagating colliding shocks. In the case of colliding
shocks, the results are similar to previous experiments on the Orion laser,
demonstrating the feasibility of this platform on SG-II to carry on future
experiments of this type. The study of the post-shock region in single shocks
had not been looked at in detail in previous experiments, e.g. on Orion and
other similar laser facilities. For instance, work by [Michel  _et al._
(2018)] and references therein have mostly focused on the radiative precursor
region ahead of the shock and rarely studied the dense post-shock region.

One of the main results of these experiments on SG-II was to study the
morphology of a single shock up to 100 ns to understand its evolution. The
shock is characterised by the growth of spatial non-uniformities, with typical
wavelenghts $\lambda\sim 250-500$ $\mu$m. Our first numerical simulations with
the code ARWEN show the formation of similar features at 20 ns with a rough
wavelength of $\lambda\sim 125$ $\mu$m in line with the experimental results,
however it is not clear how sensitive are these features to different initial
conditions in the simulations and how can these features change if the
resolution of the XRBL diagnostic is improved.

We can estimate characteristic timescales for the growth of hydrodynamic
instabilities from a shocked- clump model presented in [Hansen  _et al._
(2017)]. For a strong shock, the Rayleigh-Taylor instability is expected to
grow in a timescale given by
$t_{RT}\sim\frac{\sqrt{\eta}~{}r_{spot}}{v_{shock}}$ with $\eta$ the ratio of
post-shock to pre-shock density, $r_{spot}$ the radius of the laser focal spot
and $v_{shock}$ the tip shock velocity. From the simulations at 20 ns we
estimate $\eta\sim 12/1.67\sim 7$ and from the experiments $r_{spot}\sim 185$
$\mu$m and $v_{shock}\sim 39$ km/s, resulting in $t_{RT}\sim 5$ ns in line
with the experimental results. Similarly, the growth of the non-linear thin
shell instability (NLTSI) is given by the fragmentation time
$t_{frag}\sim\frac{h}{C_{s}}$ with $h$ the thickness of the shocked layer and
$C_{s}$ its sound speed. For shocked argon at a temperature of $T\sim 20$ eV,
$C_{s}\sim 9$ km/s, and for a shock thickness of $h\sim 100$ $\mu$m this
results in $t_{frag}\sim 10$ ns, again consistent with the timescales observed
in the experiments presented here.

The role of radiative cooling in the shock can be estimated using the plasma
parameters from the simulations of $\rho\sim 10$ mg/cc and $T\sim 20$ eV. The
expected cooling time for argon for these conditions (see Fig. 4 in [Espinosa
_et al._ (2017)]) is $t_{cool}\sim 1$ ns, indicating that the plasma in the
shock is radiatively cooled and thus could be prone to the formation of
instabilities mediated by radiative losses. We note that the formation of
similar spatial features was also observed in previous laser experiments with
shocks in argon [Loupias  _et al._ (2009)], pointing to a common cause. It is
worth noting the work by [Visco  _et al._ (2012)] and [Reighard  _et al._
(2006)] driving shocks in argon at a pressure of 1 bar however, besides these
works, we were unable to find imaging results that provide data on the shock
morphology.

The use of argon at a relatively high initial pressure (1 bar) and the
resulting shock velocity of $\sim$40 km/s opens the question of the importance
of radiative effects in these experiments. These effects can be quantified
using the Boltzmann and Mihalas numbers following the definitions in [Falize,
Michaut, and Bouquet (2011), Chaulagain  _et al._ (2015), Mabey  _et al._
(2020)] and references therein. For the plasma conditions from our first
simulations we estimate a Boltzmann number $\sim$1 and a Mihalas number of
$\sim 10^{3}$. The latter is unsurprising as only a handful of experiments in
the past has claimed to be in a pressure dominated regime (see e.g. [Dizière
_et al._ (2011)]). A Boltzmann number $\sim$1 implies that the radiative flow
in our experiments is of the same order as the material flow which means we
are in the threshold where the shock might not be strongly influenced by
radiation. Looking at radiative effects from intermediate cases like this one
to the case where the structure is dominated by radiation is necessary for a
better understanding of the radiation of effect on shock waves as a general
topic, which remains a very difficult topic at present.

Future work on SG-II will aim at providing more statistics of single shocks in
argon and assess the role of radiative losses in the formation of these
features. This will be complemented by a more detailed simulation work with
the ARWEN code.

###### Acknowledgements.

This research was supported by The Royal Society (UK) through a University
Research Fellowship (URF-R-180032), a Research Fellows Enhancement Award (RGF-
EA-180240), an International Exchanges grant (IES-R3-170140), and a Research
Grant (RG2017-R2). The authors would like to thank the operation group of the
SG-II laser facility. C.S. acknowledges support from the French INSU-PNPS
program. U.C. acknowledges support by the project Advanced Research
(CZ.02.1.01/0.0/0.0/16$\\_$019/0000789) from European Regional Development
Fund (ADONIS). F.S-V. acknowledges the technical support from Paul Brown, Alan
Finch and the entire team at the Physics Mechanical Instrumentation Workshop
at Imperial College London.

## References

  * Drake (2005) R. P. Drake, “Radiative Shocks in Astrophysics and the Laboratory,” in  _High Energy Density Laboratory Astrophysics_, April 2004 (Springer-Verlag, Berlin/Heidelberg, 2005) pp. 49–59.
  * Drake (2019) R. P. Drake, “A journey through high-energy-density physics,” Nuclear Fusion 59, 035001 (2019).
  * Mabey  _et al._ (2020) P. Mabey, T. Michel, B. Albertazzi, E. Falize, N. Charpentier, and M. Koenig, “Calculating the temperature of strongly radiative shocks,” Physics of Plasmas 27, 083302 (2020), https://doi.org/10.1063/5.0008301 .
  * Mabey  _et al._ (2020) P. Mabey, B. Albertazzi, G. Rigon, J. R. Marquès, C. A. J. Palmer, J. Topp-Mugglestone, P. Perez-Martin, F. Kroll, F. E. Brack, T. E. Cowan, U. Schramm, K. Falk, G. Gregori, E. Falize, and M. Koenig, “Laboratory Study of Bilateral Supernova Remnants and Continuous MHD Shocks,” Astrophys. J. 896, 167 (2020).
  * Michel  _et al._ (2018) T. Michel, E. Falize, B. Albertazzi, G. Rigon, Y. Sakawa, T. Sano, H. Shimogawara, R. Kumar, T. Morita, C. Michaut, and et al., “Analytical modelling of the expansion of a solid obstacle interacting with a radiative shock,” High Power Laser Science and Engineering 6, e30 (2018).
  * Michel  _et al._ (2019) T. Michel, B. Albertazzi, P. Mabey, G. Rigon, F. Lefevre, L. V. B. Som, P. Barroso, S. Egashira, R. Kumar, C. Michaut, M. Ota, N. Ozaki, Y. Sakawa, T. Sano, E. Falize, and M. Koenig, “Laboratory observation of radiative shock deceleration and application to SN 1987a,” The Astrophysical Journal 888, 25 (2019).
  * Rodríguez  _et al._ (2015) R. Rodríguez, G. Espinosa, J. M. Gil, C. Stehlé, F. Suzuki-Vidal, J. G. Rubiano, P. Martel, and E. Mínguez, “Microscopic properties of xenon plasmas for density and temperature regimes of laboratory astrophysics experiments on radiative shocks,” Phys. Rev. E 91, 053106 (2015).
  * Suzuki-Vidal  _et al._ (2017) F. Suzuki-Vidal, T. Clayson, C. Stehlé, G. F. Swadling, J. M. Foster, J. Skidmore, P. Graham, G. C. Burdiak, S. V. Lebedev, U. Chaulagain, R. L. Singh, E. T. Gumbrell, S. Patankar, C. Spindloe, J. Larour, M. Kozlova, R. Rodriguez, J. M. Gil, G. Espinosa, P. Velarde, and C. Danson, “Counterpropagating Radiative Shock Experiments on the Orion Laser,” Physical Review Letters 119, 1–6 (2017), arXiv:1706.04824 .
  * Clayson  _et al._ (2017) T. Clayson, F. Suzuki-Vidal, S. V. Lebedev, G. F. Swadling, C. Stehlé, G. C. Burdiak, J. M. Foster, J. Skidmore, P. Graham, E. Gumbrell, S. Patankar, C. Spindloe, U. Chaulagain, M. Kozlová, J. Larour, R. L. Singh, R. Rodriguez, J. M. Gil, G. Espinosa, P. Velarde, and C. Danson, “Counter-propagating radiative shock experiments on the Orion laser and the formation of radiative precursors,” High Energy Density Physics 23, 60–72 (2017), arXiv:1703.01205 .
  * Zhu  _et al._ (2018) J. Zhu, J. Zhu, X. Li, B. Zhu, W. Ma, X. Lu, W. Fan, Z. Liu, S. Zhou, G. Xu, G. Zhang, X. Xie, L. Yang, J. Wang, X. Ouyang, L. Wang, D. Li, P. Yang, Q. Fan, M. Sun, C. Liu, D. Liu, Y. Zhang, H. Tao, M. Sun, P. Zhu, B. Wang, Z. Jiao, L. Ren, D. Liu, X. Jiao, H. Huang, and Z. Lin, “Status and development of high-power laser facilities at the NLHPLP,” High Power Laser Science and Engineering 6, 1–23 (2018).
  * Spindloe  _et al._ (2017) C. Spindloe, D. Wyatt, S. Astbury, G. F. Swadling, T. Clayson, C. Stehlé, J. M. Foster, E. Gumbrell, R. Charles, C. N. Danson, P. Brummitt, and F. Suzuki-Vidal, “Design and fabrication of gas cell targets for laboratory astrophysics experiments on the Orion high-power laser facility,” High Power Laser Science and Engineering 5, 2–6 (2017).
  * Chaulagain  _et al._ (2015) U. Chaulagain, C. Stehlé, J. Larour, M. Kozlová, F. Suzuki-Vidal, P. Barroso, M. Cotelo, P. Velarde, R. Rodriguez, J. Gil, A. Ciardi, O. Acef, J. Nejdl, L. de Sá, R. Singh, L. Ibgui, and N. Champion, “Structure of a laser-driven radiative shock,” High Energy Density Physics 17, 106–113 (2015), 10th International Conference on High Energy Density Laboratory Astrophysics.
  * Singh  _et al._ (2017) R. Singh, C. Stehlé, F. Suzuki-Vidal, M. Kozlova, J. Larour, U. Chaulagain, T. Clayson, R. Rodriguez, J. Gil, J. Nejdl, M. Krus, J. Dostal, R. Dudzak, P. Barroso, O. Acef, M. Cotelo, and P. Velarde, “Experimental study of the interaction of two laser-driven radiative shocks at the pals laser,” High Energy Density Physics 23, 20–30 (2017).
  * Kuranz  _et al._ (2006) C. C. Kuranz, B. E. Blue, R. P. Drake, H. F. Robey, J. F. Hansen, J. P. Knauer, M. J. Grosskopf, C. Krauland, and D. C. Marion, “Dual, orthogonal, backlit pinhole radiography in OMEGA experiments,” Review of Scientific Instruments 77, 10E327 (2006).
  * Ruggles  _et al._ (2003) L. E. Ruggles, J. L. Porter, P. K. Rambo, W. W. Simpson, M. F. Vargas, G. R. Bennett, and I. C. Smith, “Measurements of 4–10 keV x-ray production with the Z-Beamlet laser,” Review of Scientific Instruments 74, 2206–2210 (2003).
  * Sinars  _et al._ (2004) D. Sinars, L. Gregorian, D. Hammer, and Y. Maron, “Plasma imaging and spectroscopy diagnostics developed on 100-500-kA pulsed power devices,” Proceedings of the IEEE 92, 1110–1121 (2004).
  * Park  _et al._ (2012) H.-S. Park, D. Ryutov, J. Ross, N. Kugland, S. Glenzer, C. Plechaty, S. Pollaine, B. Remington, A. Spitkovsky, L. Gargate, G. Gregori, A. Bell, C. Murphy, Y. Sakawa, Y. Kuramitsu, T. Morita, H. Takabe, D. Froula, G. Fiksel, F. Miniati, M. Koenig, A. Ravasio, A. Pelka, E. Liang, N. Woolsey, C. Kuranz, R. Drake, and M. Grosskopf, “Studying astrophysical collisionless shocks with counterstreaming plasmas from high power lasers,” High Energy Density Physics 8, 38–45 (2012).
  * Espinosa  _et al._ (2017) G. Espinosa, R. Rodríguez, J. M. Gil, F. Suzuki-Vidal, S. V. Lebedev, A. Ciardi, J. G. Rubiano, and P. Martel, “Influence of atomic kinetics in the simulation of plasma microscopic properties and thermal instabilities for radiative bow shock experiments,” Physical Review E 95, 033201 (2017).
  * Ogando and Velarde (2001) F. Ogando and P. Velarde, “Development of a radiation transport fluid dynamic code under AMR scheme,” Journal of Quantitative Spectroscopy and Radiative Transfer 71, 541–550 (2001).
  * García-Senz  _et al._ (2019) D. García-Senz, P. Velarde, F. Suzuki-Vidal, C. Stehlé, M. Cotelo, D. Portillo, T. Plewa, and A. Pak, “Interaction of Hemispherical Blast Waves with Inhomogeneous Spheres: Probing the Collision of a Supernova Ejecta with a Nearby Companion Star in the Laboratory,” The Astrophysical Journal 871, 177 (2019), arXiv:1812.06285 .
  * Hansen  _et al._ (2017) E. C. Hansen, A. Frank, P. Hartigan, and S. V. Lebedev, “The shock dynamics of heterogeneous YSO jets:3d simulations meet multi-epoch observations,” The Astrophysical Journal 837, 143 (2017).
  * Loupias  _et al._ (2009) B. Loupias, C. D. Gregory, E. Falize, J. Waugh, D. Seiichi, S. Pikuz, Y. Kuramitsu, A. Ravasio, S. Bouquet, C. Michaut, P. Barroso, M. Rabec le Gloahec, W. Nazarov, H. Takabe, Y. Sakawa, N. Woolsey, and M. Koenig, “Experimental results to study astrophysical plasma jets using Intense Lasers,” Astrophysics and Space Science 322, 25–29 (2009).
  * Visco  _et al._ (2012) A. J. Visco, R. P. Drake, S. H. Glenzer, T. Döppner, G. Gregori, D. H. Froula, and M. J. Grosskopf, “Measurement of radiative shock properties by x-ray thomson scattering,” Phys. Rev. Lett. 108, 145001 (2012).
  * Reighard  _et al._ (2006) A. B. Reighard, R. P. Drake, T. Donajkowski, M. Grosskopf, K. K. Dannenberg, D. Froula, S. Glenzer, J. S. Ross, and J. Edwards, “Thomson scattering from a shock front,” Review of Scientific Instruments 77, 10E504 (2006), https://doi.org/10.1063/1.2220069 .
  * Falize, Michaut, and Bouquet (2011) É. Falize, C. Michaut, and S. Bouquet, “SIMILARITY PROPERTIES AND SCALING LAWS OF RADIATION HYDRODYNAMIC FLOWS IN LABORATORY ASTROPHYSICS,” The Astrophysical Journal 730, 96 (2011).
  * Dizière  _et al._ (2011) A. Dizière, C. Michaut, M. Koenig, C. D. Gregory, A. Ravasio, Y. Sakawa, Y. Kuramitsu, T. Morita, T. Ide, H. Tanji, H. Takabe, P. Barroso, and J. M. Boudenne, “Highly radiative shock experiments driven by GEKKO XII,” Astrophysics and Space Science 336, 213–218 (2011).


$|\mathcal{S}^{n}_{n}|=2^{n}\cdot 2{n(n+1)/2}=2^{n+n(n+1)/2}$ (86)

This follows from [KG15]. In particular, Corollary 2 in Ref. [KG15] gives a
formula for the number of stabilizer states with pre-described inner product
with respect to a fixed reference stabilizer state. For our purposes, it
suffices to take as reference state the all-zero state $\ket{0^{n}}$ and find
the number of stabilizer states $\ket{\psi}$ such that
$|\bra{\psi}\ket{0^{n}}|=2^{-n}$. Such states are precisely the $n$-qubit
stabilizer states giving rise to the uniform distribution.

Hence,

$\operatorname*{\mathbf{Pr}}_{U\sim\mathrm{Cl}(2^{n})}\left(P_{U}=\mathcal{U}\right)=\frac{2^{n+n(n+1)/2}}{2^{n+n(n+1)/2}\prod_{i=1}^{n}\left(1+\frac{1}{2^{i}}\right)}=\frac{1}{\prod_{i=1}^{n}\left(1+\frac{1}{2^{i}}\right)}$
(87)

The asymptotic behavior of this product for $n\to\infty$ is found in [Ben21].
∎

##  Appendix E Deterministic algorithms

The aim of this appendix is to give a detailed proof of Lemma 1 which is
restated as Theorem 30. We follow a similar strategy as Feldman in [Fel17] by
proving the result for learning via a reduction to a suitably chosen decision
problem.

######  Problem 2: (Decide $\mathcal{D}$ versus $Q$)

Let $\mathcal{D}$ be some distribution class and $Q$ some fixed reference
distribution. The task decide $\mathcal{D}$ versus $Q$ is defined as, given
access to an unknown $P\in\mathcal{D}\cup\left\\{Q\right\\}$ to decide whether
“$P=Q$” or “$P\in\mathcal{D}$”.

We connect the query complexity of learning with the query complexity of
deciding by the following lemma. .

######  Lemma 28: (Learning is as hard as deciding)

Let $\mathcal{D}$ be a distribution class and let $Q$ be such that
$\mathrm{d}_{\mathrm{TV}}(P,Q)>\epsilon+\tau$ for all $P\in\mathcal{D}$. Let
$0<\tau\leq\epsilon\leq 1$. Let $\mathcal{A}$ be a deterministic algorithm
that $\epsilon$-learns $\mathcal{D}$ from $q$ many $\tau$ accurate statistical
queries. Then there exists a deterministic algorithm that decides
$\mathcal{D}$ versus $Q$ from $q+1$ many $\tau$ accurate statistical queries.

###### Proof.

We run $\mathcal{A}$ on the unknown distribution
$P\in\mathcal{D}\cup\left\\{Q\right\\}$ and obtain either

  * •

a representation of some $P^{\prime}$ which is $\epsilon$ close to $P$ if
$P\in\mathcal{D}$, or

  * •

anything if $P=Q$.

In case we do not receive a representation of any distribution return “$P=Q$”.
Now, assume we receive a representation of some distribution $P^{\prime}$.
Using this representation compute whether $P^{\prime}$ is $\epsilon$ close to
any distribution in $\mathcal{D}$. While this step is computationally costly,
it does not require any further queries to $\mathtt{Stat}(P)$. If there does
not exists such a distribution in $\mathcal{D}$ which is $\epsilon$-close to
$P^{\prime}$, return “$P=Q$”.

Now assume there exists an $H\in\mathcal{D}$ such that
$\mathrm{d}_{\mathrm{TV}}(P^{\prime},H)<\epsilon$. To assure, that
$\mathcal{A}$ is not biased towards returning distributions close to
$\mathcal{D}$ if it fails, compute the set $S$ that maximizes the total
variation distance between $Q$ and $P^{\prime}$,
$\absolutevalue{P^{\prime}(S)-Q(S)}=\mathrm{d}_{\mathrm{TV}}(P^{\prime},Q)$.
Denote by $\phi=\mathds{1}_{S}$ the characteristic function on $S$ and query
$v_{\phi}\leftarrow\mathtt{Stat}_{\tau}(P)[\phi]$. If
$\absolutevalue{Q[\phi]-v_{\phi}}\leq\tau$ return “$P=Q$”, else return
“$P\in\mathcal{D}$”.

We analyze the algorithm for each case separately. Common to both is that the
algorithm makes, by definition, at most $q+1$ statistical queries.

To begin with assume $P\in\mathcal{D}$. By the correctness of $\mathcal{A}$ we
receive a representation of some $P^{\prime}$ that is at most $\epsilon$ far
from $P$. By assumption, for any $H\in\mathcal{D}$ it holds
$\mathrm{d}_{\mathrm{TV}}(H,Q)>\epsilon+\tau$. Then, by the definition of $S$
using the reverse triangle inequality we find

$\displaystyle\absolutevalue{Q[\phi]-v_{\phi}}\geq\absolutevalue{\absolutevalue{Q[\phi]-P[\phi]}-\absolutevalue{P[\phi]-v_{\phi}}}>\absolutevalue{\epsilon+\tau-\tau}=\epsilon\geq\tau\,.$
(88)

Hence, we correctly decide “$P\in\mathcal{D}$”.

For the other case assume $P=Q$. If $\mathcal{A}$ does not return a valid
representation or, if $\mathcal{A}$ returns a representation of some
$P^{\prime}$ that is more than $\epsilon$ far away from any distribution in
$\mathcal{D}$, we know, by the correctness of $\mathcal{A}$, that it must hold
$P=Q$. It remains to show the last step. Assume there is an $H\in\mathcal{D}$
which is at most $\epsilon$ far from $P^{\prime}$. Then, by assumption, for
every $\phi$ it must hold $\absolutevalue{Q[\phi]-v_{\phi}}\leq\tau$. Hence,
we correctly decide “$P=Q$”. ∎

Using Lemma 28 it will be sufficient to bound the query complexity of
deciding. This is achieved by the next lemma.

######  Lemma 29: (Hardness of deciding, deterministic version)

Let $\mathcal{A}$ be a deterministic algorithm that decides $\mathcal{D}$
versus $Q$ from $q$ many $\tau$-accurate statistical queries, then for any
measure $\mu$ over $\mathcal{D}$ it holds

$\displaystyle
q\geq\left(\max_{\phi}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\absolutevalue{P[\phi]-Q[\phi]}>\tau\right]\right)^{-1}\,.$
(89)

###### Proof.

Assume we run $\mathcal{A}$ and answer every query $\phi$ by $Q[\phi]$. Denote
by $\phi_{1},\dots,\phi_{q}$ the queries made. Assume for a contradiction,
that for some $P\in\mathcal{D}$ there does not exist any distinguishing query.
Then, the responses $Q[\phi_{i}]$ for $i=1,\dots,q$ would be valid responses
for some $\mathtt{Stat}_{\tau}(P)$ contradicting the assumption that
$\mathcal{A}$ successfully decides whether $P=Q$. Thus, for any
$P\in\mathcal{D}$ there must exist at least one $i$ that distinguishes $Q$
from $P$. In particular,

$\displaystyle 1$
$\displaystyle=\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\exists
i,\,\absolutevalue{P[\phi_{i}]-Q[\phi_{i}]}>\tau\right]$ (90)
$\displaystyle\leq\sum_{i=1}^{q}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\absolutevalue{P[\phi_{i}]-Q[\phi_{i}]}>\tau\right]$
(91) $\displaystyle\leq
q\max_{\phi}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\absolutevalue{P[\phi_{i}]-Q[\phi_{i}]}>\tau\right]\,,$
(92)

which completes the proof. ∎

We are now set to prove our bound for the deterministic average case query
complexity. Note, that Lemma 28 holds for learners that learn all of
$\mathcal{D}$. Thus, the core of the remaining proof will be to translate the
implications on worst to average case learners.

######  Theorem 30: (Lemma 1 restated)

Suppose there is a deterministic algorithm $\mathcal{A}$ that
$\epsilon$-learns a $\beta$ fraction of $\mathcal{D}$ with respect to $\mu$
from $q$ many $\tau$-accurate statistical queries. Then for any $Q$ it holds

$\displaystyle
q+1\geq\frac{\beta-\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,Q)\leq\epsilon+\tau\right]}{\max_{\phi}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\absolutevalue{P[\phi]-Q[\phi]}>\tau\right]}\,,$
(93)

where again, the $\max$ is over all functions $\phi:X\to[-1,1]$.

###### Proof.

Let $\mathcal{D}^{\prime}\subseteq\mathcal{D}$ with
$\mu(\mathcal{D}^{\prime})=\beta$ be a set on which $\mathcal{A}$ is
successful. Define

$\displaystyle\mathcal{D}_{Q}=\left\\{P\in\mathcal{D}^{\prime}:\mathrm{d}_{\mathrm{TV}}(P,Q)>\epsilon+\tau\right\\}$

and let $\mu_{Q}$ be the measure $\mu$ conditioned on $\mathcal{D}_{Q}$, such
that $\mu_{Q}(P)=\mu(P\mid P\in\mathcal{D}_{Q})$. Then, by the definition of
the conditional probability,

$\displaystyle\beta-\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,Q)\leq\epsilon+\tau\right]\leq\mu(\mathcal{D}_{Q})\,.$
(94)

Therefore, for any $\phi$ it holds

$\displaystyle\begin{split}\operatorname*{\mathbf{Pr}}_{P\sim\mu_{Q}}\left[\absolutevalue{P[\phi]-Q[\phi]}>\tau\right]&=\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\absolutevalue{P[\phi]-Q[\phi]}>\tau\mid
P\in\mathcal{D}_{Q}\right]\leq\frac{\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\absolutevalue{P[\phi]-Q[\phi]}>\tau\right]}{\beta-\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,Q)\leq\epsilon+\tau\right]}\end{split}$
(95)

where we used the definition of the conditional probability.

The claim then follows from the observation that the average learner
$\mathcal{A}$ for $\mathcal{D}$ implies a learner for $\mathcal{D}_{Q}$, the
complexity of which can be bounded by the complexity of deciding
$\mathcal{D}_{Q}$ vs $Q$ via the reduction Lemma 32. We obtain a bound for the
latter from Lemma 33 applying the measure $\mu_{Q}$. ∎

Before we end this section we state a variant of this bound due to Feldman to
discuss the connection to Theorem 30. We restate his proof adapted to our
notation for the sake of completeness.

######  Lemma 31: (Variation of Lemma C.2 from [Fel17] for deterministic
algorithms)

Suppose there is a deterministic algorithm $\mathcal{A}$ that
$\epsilon$-learns a $\beta$ fraction of $\mathcal{D}$ with respect to $\mu$
from $q$ many $\tau$-accurate statistical queries. Then for any $Q$ it holds

$\displaystyle
q\geq\frac{\beta-\sup_{D}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,D)<\epsilon\right]}{\max_{\phi}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\absolutevalue{P[\phi]-Q[\phi]}>\tau\right]}\,,$
(96)

where the $\max$ is over all functions $\phi:X\to[-1,1]$ and the $\sup$ is
over all distributions $D$ over the domain $X$.

###### Proof.

Denote by $\mathcal{D}^{\prime}\subseteq\mathcal{D}$ the subset of size
$\mu(\mathcal{D}^{\prime})=\beta$ on which $\mathcal{A}$ successfully
$\epsilon$-learns from $q$ queries. We run $\mathcal{A}$ and answer every
query $\phi$ by $Q[\phi]$. By assumption $\mathcal{A}$ makes $q$ queries
$\phi_{1},\dots,\phi_{q}$ to $Q$ and, without loss of generality, we assume
that the algorithm returns some distribution $D$. Now, let $P$ be any
distribution in $\mathcal{D}^{\prime}$ at least $\epsilon$-far from $D$.
Exactly as in the proof of Lemma 29, there must exists at least one query
function $\phi_{i}$ that distinguishes $Q$ from $P$. In particular, it must
hold

$\displaystyle\begin{split}\beta-\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,D)<\epsilon\right]&\leq\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\exists
i:\,\absolutevalue{P[\phi_{i}]-Q[\phi_{i}]}>\tau\right]\\\
&\leq\sum_{i=1}^{q}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\absolutevalue{P{\phi_{i}]-Q[\phi_{i}]}>\tau}\right]\\\
&\leq
q\max_{\phi}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\absolutevalue{P[\phi]-Q[\phi]}>\tau\right]\,.\end{split}$
(97)

Now assume that, after interacting with $Q$, the algorithm does not return any
valid distribution. Then, again by $\mathcal{A}$’s determinism, for any
$P\in\mathcal{D}^{\prime}$ there must exist a distinguishing query $\phi_{i}$
that distinguishes $Q$ from $P$. The claim then follows by taking the supremum
over $D\in\mathcal{D}_{X}$ to bound the $\epsilon$-ball around the unknown
$D$. ∎

###### Note 2:

We want to highlight that Lemma 31 is tight with respect to $\beta$: The
trivial algorithm, which makes zero queries and always outputs that $D$ which
maximizes the open $\epsilon$-ball will, with probability
$\mu(B_{\epsilon}(D))$ over $P\sim\mu$ be correct.

###### Note 3:

As stated above, Lemma 31 gives the optimal lower bound with respect to
$\beta$. However, in some cases directly bounding the weight of all
$\epsilon$-balls may not be convenient. In Appendix G we give a general recipe
for obtaining bounds for all $\epsilon$-balls just from the two ingredients
used in Theorem 30: The maximally distinguishable fraction and the mass of the
ball around the reference distribution. While this strategy is straight
forward, the bounds obtained are slightly worse than those obtained by
directly invoking Theorem 30, which is why we stick to the latter result in
this work.

##  Appendix F Quantum and probabilistic algorithms

In this appendix we will detail the connection between statistical query
learning via deterministic and random algorithms. Throughout the section we
will refer by random algorithm to both classical probabilistic as well as
quantum algorithms.

The randomized average case query complexity for $\epsilon$-learning
$\mathcal{D}$ with respect to the probability measure $\mu$ depends on the two
parameters $\alpha$ and $\beta$, where

  * •

$\alpha$ denotes the success probability with respect to the internal
randomness of the learning algorithm and

  * •

$\beta$ denotes the fraction of distributions in $\mathcal{D}$ measured with
respect to $\mu$ on which the learning algorithm must be successful.

The aim of this appendix is to bound the randomized average case query
complexity for $\epsilon$-learning $\mathcal{D}$ by (c.f. Theorem 34)

$\displaystyle
q\geq\frac{2\cdot\left(\alpha-\frac{1}{2}\right)\cdot\left(\beta-\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,Q)\leq\epsilon+\tau\right]\right)}{\max_{\phi}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\absolutevalue{P[\phi]-Q[\phi]}>\tau\right]}\,.$
(98)

Thus, the randomized average case query complexity of $\epsilon$-learning is
bounded by the same bounds as the deterministic average case query complexity
up to a prefactor $2(\alpha-1/2)$, which becomes trivial for $\alpha\leq 1/2$.

We will follow the same strategy as in the deterministic case laid out in
Appendix E. The main difference is that we need a bound on the decision
problem 2 for random algorithms. The subtlety, why the arguments from Lemma 29
fail, is that a random algorithm does not need to make a distinguishing query
to solve the problem. Rather, it may guess the correct solution using its
internal randomness. The main technical ingredient of this Appendix is thus a
result by Feldman which, first bounding the probability of guessing correctly,
bounds the statistical query complexity for 2 which is stated as Lemma 33.

To begin with, we can follow the same strategy as before to reduce deciding to
learning, also in the random setting.

######  Lemma 32: (Learning is as hard as deciding)

Let $\mathcal{D}$ be a distribution class and let $Q$ be such that
$\mathrm{d}_{\mathrm{TV}}(P,Q)>\epsilon+\tau$ for all $P\in\mathcal{D}$. Let
$0<\tau\leq\epsilon\leq 1$. Let $\mathcal{A}$ be an algorithm that
$\epsilon$-learns $\mathcal{D}$ from $q$ many $\tau$ accurate statistical
queries with probability $\alpha$ over its internal randomness. Then there
exists an algorithm that, with probability $\alpha$ over its internal
randomness, decides $\mathcal{D}$ versus $Q$ from $q+1$ many $\tau$ accurate
statistical queries.

###### Proof.

The proof is identical to that of Lemma 28. The only difference is that the
learner $\mathcal{A}$ only succeeds with probability $\alpha$, which leads to
the decider only succeeding with probability $\alpha$. The reduction itself
however is deterministic and, as such, does not change the statistics. ∎

We now state the result by Feldman on the randomized statistical query
complexity of 2. For the sake of self consistency we provide the proof adapted
to our notation.

######  Lemma 33: (Hardness of deciding. Taken from Theorem 3.9 from [Fel17])

Let $\mathcal{A}$ be a random algorithm that decides $\mathcal{D}$ versus $Q$
with probability at least $\alpha$ from $q$ many $\tau$ accurate statistical
queries. Then, for any measure $\mu$ over $\mathcal{D}$ it holds

$\displaystyle
q\geq\frac{2\cdot(\alpha-\frac{1}{2})}{\max_{\phi}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\absolutevalue{P[\phi]-Q[\phi]}>\tau\right]}\,.$
(99)

###### Proof.

Let $\mathcal{A}$ be an algorithm that decides $\mathcal{D}$ vs. $Q$ with
probability $\alpha$ over its internal randomness. We run $\mathcal{A}$ and,
on every query $\phi$ return $Q[\phi]$ . Denote by $\phi_{1},\dots,\phi_{q}$
the queries made. These queries then can be interpreted as random variables
with respect to $\mathcal{A}$’s randomness. Let $P\in\mathcal{D}$ and denote
by

$\displaystyle p(P)=\operatorname*{\mathbf{Pr}}_{\mathcal{A}}\left[\exists
i\,:\,\absolutevalue{P[\phi_{i}]-Q[\phi_{i}]}>\tau\right]\,.$ (100)

We now show that $p(P)\geq 2(\alpha-1/2)$: By the correctness of $\mathcal{A}$
the corresponding output will be “$P\in\mathcal{D}$” with probability at most
$1-\alpha$. For the sake of contradiction assume $p(P)<2(\alpha-1/2)$. Thus,
when run on $P$, for some valid answers $\mathcal{A}$ will still return
“$P=Q$” with probability at least
$>1-p(P)-(1-\alpha)>1-2\alpha+1-1+\alpha=1-\alpha$. Since this probability is
bounded by $1-\alpha$ we find a contradiction $\alpha<\alpha$. Thus $p(P)\geq
2(\alpha-1/2)$.

The remainder now follows from the union bound as in Lemma 29:

$\displaystyle\begin{split}2(\alpha-1/2)\leq
p(P)&=\operatorname*{\mathbf{Pr}}_{\mathcal{A},P\sim\mu}\left[\exists
i\,:\,\absolutevalue{P[\phi_{i}]-Q[\phi_{i}]}>\tau\right]\\\
&\leq\sum_{i=1}^{q}\operatorname*{\mathbf{Pr}}_{\mathcal{A},P\sim\mu}\left[\absolutevalue{P[\phi_{i}]-Q[\phi_{i}]}>\tau\right]\\\
&\leq
q\max_{\phi}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\absolutevalue{P[\phi]-Q[\phi]}>\tau\right]\,.\end{split}$
(101)

∎

Thus, following Appendix E, we can state the main theorem of this appendix.

######  Theorem 34: (Randomized average case query complexity of learning)

Let $\mathcal{A}$ be a random algorithm for average case $\epsilon$-learning
$\mathcal{D}$ with respect to $\mu$ with parameters $\alpha$ and $\beta$ from
$q$ many $\tau$ accurate statistical queries. Then for any $Q$ it holds

$\displaystyle q+1\geq
2\cdot\frac{(\alpha-\frac{1}{2})\cdot(\beta-\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,Q)\leq\epsilon+\tau\right])}{\max_{\phi}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\absolutevalue{P[\phi]-Q[\phi]}>\tau\right]}\,.$
(102)

###### Proof.

The proof is identically to that of Theorem 30 using Lemma 32 and Lemma 33
instead of Lemma 28 and Lemma 29. ∎

For the sake of context relating to the discussion in the end of Appendix E
and [Fel17, Lemma C.2], we finish this appendix with two additional insights.

###### Note 4:

If we restrict the result to probabilistic algorithms we can follow the
argument from [Fel17, Lemma C.2]: One can make the randomness explicit by
writing the random algorithm $\mathcal{A}$ as an ensemble of deterministic
algorithms $\\{\mathcal{A}_{x}\\}$ with $x\sim\mathcal{A}$ the internal
randomness. Then the randomized average case query complexity can be bounded
by the deterministic average case query complexity replacing $\beta$ by
$\alpha\cdot\beta$. This yields

$\displaystyle
q\geq\frac{\alpha\cdot\beta-\sup_{D}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,D)<\epsilon\right]}{\max_{\phi}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\absolutevalue{P[\phi]-Q[\phi]}>\tau\right]}\,,$
(103)

where, for the sake of transparency, we used Feldmans bound stated as Lemma 31
for the deterministic reference bound.

Note that Equation 103 is tight with respect to $\alpha\cdot\beta$ and the
joint measure $\mu\times\mathcal{A}$. However, it has two disadvantages for
our usecase. First, it only holds for classical probabilistic algorithms, but
not for other random algorithms such as quantum algorithms. Second, we are
interested in the average case hardness as in Definition 2. This means, we
would like a statement that is tight with respect to $\beta$ with respect to
$\mu$ only. Thus, to obtain the corresponding tight bound for quantum
algorithms, we add the following lemma.

###### Lemma 35:

Let $\mathcal{A}$ be a random algorithm for average case $\epsilon$-learning
$\mathcal{D}$ with respect to $\mu$ with parameters $\alpha$ and $\beta$ from
$q$ many $\tau$-accurate statistical queries. Then for any $Q$ it holds

$\displaystyle q\geq
2\cdot\frac{(\alpha-\frac{1}{2})\cdot(\beta-\sup_{D}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,D)<\epsilon\right])}{\max_{\phi}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\absolutevalue{P[\phi]-Q[\phi]}>\tau\right]}\,,$
(104)

where the $\sup$ is over all distributions with the same domain $X$ and the
$\max$ is over all functions $\phi:X\to[-1,1]$.

###### Proof.

Assume $\mathcal{A}$ is a random algorithm that $\epsilon$-learns
$\mathcal{D}$ with respect to $\mu$, $\alpha$ and $\beta$ from $q$ many
$\tau$-accurate statistical queries. We run $\mathcal{A}$ and answer each
query $\phi$ by $Q[\phi]$. Denote by $\phi_{1},\dots,\phi_{q}$ the queries
made and, without loss of generality, assume $\mathcal{A}$ returns the
representation of some distribution $D$. Denote by
$\mathcal{D}^{\prime}\subseteq\mathcal{D}$ the set on which, with probability
at least $\alpha$, the algorithm is successful. Further, let $p(P)$ as in the
proof of Lemma 33 and let

$\displaystyle\mathcal{D}_{D}=\left\\{P\in\mathcal{D}^{\prime}:\mathrm{d}_{\mathrm{TV}}(P,D)\geq\epsilon\right\\}\,.$

Since $p(P)\geq 2(\alpha-1/2)$ for any
$P\in\mathcal{D}_{D}\subseteq\mathcal{D}^{\prime}$ we find

$\displaystyle\begin{split}2(\alpha-1/2)&\leq\operatorname*{\mathbf{Pr}}_{P\sim\mu,\mathcal{A}}\left[\exists
i\;,\;\absolutevalue{P[\phi_{i}]-Q[\phi_{i}]}>\tau\mid
P\in\mathcal{D}_{D}\right]\\\\[10.0pt]
&=\frac{\operatorname*{\mathbf{Pr}}_{P\sim\mu,\mathcal{A}}\left[\exists
i\;,\;\absolutevalue{P[\phi_{i}]-Q[\phi_{i}]}>\tau\right]}{\mu(\mathcal{D}_{D})}\leq\frac{\operatorname*{\mathbf{Pr}}_{P\sim\mu,\mathcal{A}}\left[\exists
i\;,\;\absolutevalue{P[\phi_{i}]-Q[\phi_{i}]}>\tau\right]}{\beta-\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,D)<\epsilon\right]}\\\\[10.0pt]
&\leq\sum_{i=1}^{q}\frac{\operatorname*{\mathbf{Pr}}_{P\sim\mu,\mathcal{A}}\left[\absolutevalue{P[\phi_{i}]-Q[\phi_{i}]}>\tau\right]}{\beta-\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,D)<\epsilon\right]}\leq
q\frac{\max_{\phi}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\absolutevalue{P[\phi]-Q[\phi]}>\tau\right]}{\beta-\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,D)<\epsilon\right]}\,,\end{split}$
(105)

where we used the definition of the conditional probability, the bound on
$\mu(\mathcal{D}_{D})$ similar to that on $\mu(\mathcal{D}_{Q})$ from the
proof of Theorem 30 and the union bound. The claim then follows from taking
the maximum over all distributions in order to estimate the unknown $D$. ∎

It is easy to see that Lemma 35 is tight with respect to $\beta$: The trivial
algorithm that always returns $D$, where $D$ is the distribution with the
$\epsilon$-ball of highest weight, will succeed with probability
$\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,D)<\epsilon\right]$.
We conclude this appendix with a note similar to Note 3.

###### Note 5:

In general Lemma 35 gives the optimal lower bounds with respect to $\beta$.
However, in some cases directly bounding the weight of all $\epsilon$-balls
may not be convenient. The following appendix Appendix G gives a general
recipe for obtaining such a bound just from the two ingredients used in
Theorem 34: The maximally distinguishable fraction and the mass of the ball
around the reference distribution. While this strategy is straight forward,
the bounds obtained are slightly worse than those obtained by directly
invoking Theorem 34, which is why we stick to the latter result in this work.

##  Appendix G Far from any fixed distribution

In the main text, we obtained multiple “far-from-uniform"-results for the
output distributions of random circuits for different depth regimes. In this
section, we show that random quantum circuits actually exhibit a more general
property. Namely, their output distributions are with overwhelming probability
far from any fixed distribution. This result was stated in the main text as 2.
Here, we restate it formally and then go on to prove it.

######  Theorem 36: (Formal version of 2)

Let ${\mu_{C}}$ be the measure on $\mathrm{U}(2^{n})$ induced by local random
quantum circuits of depth $d$. Then, there is a $d^{\prime}=O(n)$ such that at
any depth $d\geq d^{\prime}$, for any $\epsilon\leq 1/225$, and for any
distribution $D$ over $\\{0,1\\}^{n}$ it holds

$\displaystyle\operatorname*{\mathbf{Pr}}_{U\sim{\mu_{C}}}\left[\mathrm{d}_{\mathrm{TV}}(P_{U},D)\geq\epsilon\right]\geq
1-c2^{-n}\,,$ (106)

where $c$ is a constant that can be bounded by $c<7\times 10^{6}<2^{20}$.

In the following, let $D$ denote the arbitrary but fixed distribution as in
the above theorem. We note that to prove Theorem 36, we can distinguish two
cases: Either $D$ is itself close to uniform, then a far-from-uniform bound
implies a far-from-$D$ bound. In the other case, $D$ is at least some distance
away from the uniform distribution. As made explicit by the following lemma,
the “far-from-any-fixed-distribution"-result for such $D$ is implied by a
bound on the maximal distinguishable fraction with respect to the uniform
distribution, $\mathfrak{f}=\mathrm{frac}(\mu,\mathcal{U},\tau)$. In fact, the
lemma holds not only for the uniform distribution but any choice of reference
distribution $Q$.

Thus, a “far-from-any-fixed-distribution"-result follows from two ingredients:
A “far-from-$Q$" result and a bound on the maximally distinguishable fraction
against $Q$, for any reference distribution $Q$. We happen to have calculated
these bounds for the particular choice of $Q=\mathcal{U}$ already in the main
text.

###### Lemma 37:

Let $\epsilon,\tau>0$, $X$ be some domain and let $Q\in\mathcal{D}_{X}$ be the
reference distribution. Moreover, let $D\in\mathcal{D}_{X}$ be such that

$\mathrm{d}_{\mathrm{TV}}\left(Q,D\right)>\epsilon+\tau\,.$ (107)

Then for any measure $\mu$ over $\mathcal{D}_{X}$ it holds

$\displaystyle\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,D)<\epsilon\right]\leq\mathrm{frac}(\mu,Q,\tau)\,.$
(108)

###### Proof.

Recall that by the variational characterization of the total variation
distance it holds that $\mathrm{d}_{\mathrm{TV}}(Q,D)=\max_{T\subset
X}\absolutevalue{Q(T)-D(T)}$. Let $S\subseteq X$ be such a set maximizing the
total variation distance and denote by $\phi=\mathds{1}_{S}$ the
characteristic function on $S$. This is,
$\mathrm{d}_{\mathrm{TV}}(D,Q)=\absolutevalue{D[\phi]-Q[\phi]}$.

By the reverse triangle inequality for any $P^{\prime}\in B_{\epsilon}(D)$ it
then holds

$\displaystyle\begin{split}\absolutevalue{P^{\prime}[\phi]-Q[\phi]}&\geq\absolutevalue{\absolutevalue{P^{\prime}[\phi]-D[\phi]}-\absolutevalue{D[\phi]-Q[\phi]}}\\\
&\geq\absolutevalue{\mathrm{d}_{\mathrm{TV}}(Q,D)-\mathrm{d}_{\mathrm{TV}}(P^{\prime},D)}\\\
&>\absolutevalue{\epsilon+\tau-\epsilon}=\tau\,,\end{split}$ (109)

where we have used that
$\absolutevalue{P^{\prime}[\phi]-D[\phi]}\leq\mathrm{d}_{\mathrm{TV}}(P^{\prime},D)<\epsilon$
together with
$\mathrm{d}_{\mathrm{TV}}(Q,D)>\epsilon+\tau>\epsilon>\mathrm{d}_{\mathrm{TV}}(P^{\prime},D)$.

Hence, by Equation 109 it holds

$\displaystyle\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,D)<\epsilon\right]\leq\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\absolutevalue{P[\phi]-Q[\phi]}>\tau\right]\leq\mathrm{frac}(\mu,Q,\tau)\,,$
(110)

where the last inequality is due to the maximum over all functions $\phi$ in
the definition of $\mathrm{frac}(\mu,Q,\tau)$ (Definition 3). ∎

Applying Lemma 37 to the choice of $Q=\mathcal{U}$ and using our bound for the
maximally distinguishable fraction $\mathfrak{f}$ against uniform from Lemma 7
in Section 4.1, we find the following:

###### Corollary 38:

Let $\epsilon,\tau>0$ and let $D$ be any probability distribution over
$\left\\{0,1\right\\}^{n}$ satisfying

$\mathrm{d}_{\mathrm{TV}}\left(D,\mathcal{U}\right)>\epsilon+\tau$ (111)

where $\mathcal{U}$ is the uniform distribution. Let ${\mu_{C}}$ denote the
measure over brickwork random quantum circuits as in Definition 5. Then, there
is a $d^{\prime}=O(n)$ such that at any depth $d\geq d^{\prime}$ it holds

$\operatorname*{\mathbf{Pr}}_{U\sim{\mu_{C}}}\left[\mathrm{d}_{\mathrm{TV}}(D,P_{U})<\epsilon\right]\leq\frac{3}{2^{n}\tau^{2}}.$
(112)

We now complete the proof of Theorem 36 following the two-cases argument laid
out above.

###### Proof of Theorem 36.

Let $D$ be an arbitrary distribution, let $d$ large enough and let
$\epsilon=1/450$ such that $3\epsilon=\epsilon^{\prime}=1/150$. We distinguish
two cases:

  1. 1.

$\mathrm{d}_{\mathrm{TV}}(D,\mathcal{U})\leq 2\epsilon$,

  2. 2.

$\mathrm{d}_{\mathrm{TV}}(D,\mathcal{U})>2\epsilon$.

In case 1, we have that

$\operatorname*{\mathbf{Pr}}_{U\sim{\mu_{C}}}\left[\mathrm{d}_{\mathrm{TV}}(P_{U},D)<\epsilon\right]\leq\operatorname*{\mathbf{Pr}}_{U\sim{\mu_{C}}}\left[\mathrm{d}_{\mathrm{TV}}\left(P_{U},\mathcal{U}\right)<\epsilon^{\prime}\right]<3200\cdot
2^{-n}\leq O\left(2^{-n}\right)$ (113)

by our far-from-uniform result from the main text, namely Corollary 11.

In case 2, we have that $\mathrm{d}_{\mathrm{TV}}(D,\mathcal{U})>2\epsilon$.
Setting $\tau=\epsilon$ we can apply Corollary 38 to obtain

$\operatorname*{\mathbf{Pr}}_{U\sim{\mu_{C}}}\left[\mathrm{d}_{\mathrm{TV}}(P_{U},D)<\epsilon\right]<\frac{3}{2^{n}\epsilon^{2}}=607500\times
2^{-n}\,.$ (114)

Hence, for any distribution $D$, any $\epsilon\leq 1/450$ we find

$\operatorname*{\mathbf{Pr}}_{U\sim{\mu_{C}}}\left[\mathrm{d}_{\mathrm{TV}}(P_{U},D)<\epsilon\right]<607500\times
2^{-n}=O\left(2^{-n}\right)\,.$ (115)

∎

Finally, we summarize the connection between the $\epsilon$-ball with the
largest weight and the maximally distinguishable fraction as advertised at the
end of Appendix E as follows.

###### Lemma 39:

Let $\epsilon,\tau>0$, $X$ be some domain, $\mu$ be a measure over
$\mathcal{D}_{X}$ and $Q\in\mathcal{D}_{X}$ an arbitrary distribution. Then
for any $D\in\mathcal{D}_{X}$ it holds

$\displaystyle\begin{split}\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,D)<\epsilon\right]\leq\max\left\\{\mathrm{frac}(\mu,Q,\tau)\,,\,\,\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,Q)\leq
2\epsilon+\tau\right]\right\\}\,.\end{split}$ (116)

###### Proof.

We consider two cases. In case $\mathrm{d}_{\mathrm{TV}}(D,Q)>\epsilon+\tau$
we obtain the contribution from $\mathrm{frac}(\mu,Q,\tau)$ via Lemma 37. So
consider the case $\mathrm{d}_{\mathrm{TV}}(D,Q)\leq\epsilon+\tau$. In this
case we can bound

$\displaystyle\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,D)<\epsilon\right]\leq\operatorname*{\mathbf{Pr}}_{P\sim\mu}\left[\mathrm{d}_{\mathrm{TV}}(P,Q)\leq
2\epsilon+\tau\right]\,,$ (117)

which yields the claim. ∎

## References

  * [AAK21] Naman Agarwal, Pranjal Awasthi and Satyen Kale “A deep conditioning treatment of neural networks” arXiv, 2021 arXiv:2002.01523
  * [Aar07] Scott Aaronson “The learnability of quantum states” In _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ 463.2088, 2007, pp. 3089–3114 DOI: 10.1098/rspa.2007.0113
  * [ABG+] Sanjeev Arora, Aditya Bhaskara, Rong Ge and Tengyu Ma “Provable bounds for learning some deep representations” arXiv arXiv: http://arxiv.org/abs/1310.6343
  * [AC17] Scott Aaronson and Lijie Chen “Complexity-theoretic foundations of quantum supremacy experiments” In _32nd Computational Complexity Conference (CCC 2017)_ 79, Leibniz International Proceedings in Informatics (LIPIcs) Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017, pp. 22:1–22:67 DOI: 10.4230/LIPIcs.CCC.2017.22
  * [AG04] Scott Aaronson and Daniel Gottesman “Improved simulation of stabilizer circuits” In _Phys. Rev. A_ 70 American Physical Society, 2004, pp. 052328 DOI: 10.1103/PhysRevA.70.052328
  * [AGS21] Srinivasan Arunachalam, Alex Bredariol Grilo and Aarthi Sundaram “Quantum hardness of learning shallow classical circuits” In _SIAM Journal on Computing_ 50.3 SIAM, 2021, pp. 972–1013
  * [AK21] Eddie Aamari and Alexander Knop “Statistical query complexity of manifold estimation” In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ Virtual Italy: ACM, 2021, pp. 116–122 DOI: 10.1145/3406325.3451135
  * [AS20] Emmanuel Abbe and Colin Sandon “Poly-time universality and limitations of deep learning” arXiv:2001.02992 arXiv, 2020 URL: http://arxiv.org/abs/2001.02992
  * [AW17] Srinivasan Arunachalam and Ronald Wolf “A survey of quantum learning theory”, 2017 arXiv:1701.06806 [quant-ph]
  * [Bar17] Boaz Barak “The complexity of public-key cryptography” https://eprint.iacr.org/2017/365, Cryptology ePrint Archive, Paper 2017/365, 2017 URL: https://eprint.iacr.org/2017/365
  * [BCG21] Boaz Barak, Chi-Ning Chou and Xun Gao “Spoofing linear cross-entropy benchmarking in shallow quantum circuits” In _12th Innovations in Theoretical Computer Science Conference (ITCS 2021)_ 185, Leibniz International Proceedings in Informatics (LIPIcs) Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021, pp. 30:1–30:20 DOI: 10.4230/LIPIcs.ITCS.2021.30
  * [BCH+21] Fernando G… Brandão et al. “Models of quantum complexity growth” In _PRX Quantum_ 2 American Physical Society, 2021, pp. 030316 DOI: 10.1103/PRXQuantum.2.030316
  * [BDM+05] Avrim Blum, Cynthia Dwork, Frank McSherry and Kobbi Nissim “Practical privacy: The SuLQ framework” In _Proceedings of the Twenty-Fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems - PODS ’05_ Baltimore, Maryland: ACM Press, 2005, pp. 128 DOI: 10.1145/1065167.1065184
  * [Ben21] Ben “Solve the limit of the sucession $\left(1+\frac{1}{2}\right)\left(1+\frac{1}{4}\right)\times\dots\times\left(1+\frac{1}{2^{n}}\right)$”, Mathematics Stack Exchange, 2021 URL: https://math.stackexchange.com/q/3386319
  * [Ber97] Bonnie Berger “The fourth moment method” In _SIAM Journal on Computing_ 26.4 SIAM, 1997, pp. 1188–1207
  * [BFJ+94] Avrim Blum et al. “Weakly learning DNF and characterizing statistical query learning using Fourier analysis” In _Proceedings of the twenty-sixth annual ACM symposium on Theory of computing_ , 1994, pp. 253–262
  * [BFK+94] Avrim Blum, Merrick Furst, Michael J. Kearns and Richard J. Lipton “Cryptographic primitives based on hard learning problems” In _Advances in Cryptology — CRYPTO’ 93_ Berlin, Heidelberg: Springer Berlin Heidelberg, 1994, pp. 278–291
  * [BHH16] Fernando G… Brandao, Aram W. Harrow and Michał Horodecki “Local random quantum circuits are approximate polynomial-designs” In _Communications in Mathematical Physics_ 346.2 Springer, 2016, pp. 397–434
  * [BJS11] Michael J. Bremner, Richard Jozsa and Dan J. Shepherd “Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy” In _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ 467.2126, 2011, pp. 459–472 DOI: 10.1098/rspa.2010.0301
  * [BMR+20] Tom Brown et al. “Language models are few-shot learners” In _Advances in neural information processing systems_ 33, 2020, pp. 1877–1901
  * [BMS17] Michael J. Bremner, Ashley Montanaro and Dan J. Shepherd “Achieving quantum supremacy with sparse and noisy commuting quantum computations” In _Quantum_ 1, 2017, pp. 8 DOI: 10.22331/q-2017-04-25-8
  * [CHM+15] Anna Choromanska et al. “The loss surfaces of multilayer networks” arXiv, 2015 arXiv:1412.0233
  * [CLL22] Sitan Chen, Jerry Li and Yuanzhi Li “Learning (very) simple generative models is hard” In _arXiv preprint arXiv:2205.16003_ , 2022
  * [CMD+20] Brian Coyle, Daniel Mills, Vincent Danos and Elham Kashefi “The Born supremacy: Quantum advantage and training of an Ising born machine” In _npj Quantum Information_ 6.1 Nature Publishing Group, 2020, pp. 1–11 DOI: 10.1038/s41534-020-00288-9
  * [Dan05] Christoph Dankert “Efficient simulation of random quantum states and operators” In _arXiv preprint quant-ph/0512217_ , 2005 URL: https://doi.org/10.48550/arXiv.quant-ph/0512217
  * [Dan17] Amit Daniely “SGD Learns the conjugate kernel class of the network” In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17 Red Hook, NY, USA: Curran Associates Inc., 2017, pp. 2419–2427
  * [DKS17] Ilias Diakonikolas, Daniel M. Kane and Alistair Stewart “Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures” In _2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)_ , 2017, pp. 73–84 DOI: 10.1109/FOCS.2017.16
  * [DMN+06] Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith “Calibrating noise to sensitivity in private data analysis” In _Theory of Cryptography_ , Lecture Notes in Computer Science Berlin, Heidelberg: Springer, 2006, pp. 265–284 DOI: 10.1007/11681878_14
  * [DV20] Amit Daniely and Gal Vardi “Hardness of learning neural networks with natural weights” In _Proceedings of the 34th International Conference on Neural Information Processing Systems_ , NIPS’20 Red Hook, NY, USA: Curran Associates Inc., 2020, pp. 930–940
  * [Fel08] Vitaly Feldman “Evolvability from learning algorithms” In _Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing_ Victoria British Columbia Canada: ACM, 2008, pp. 619–628 DOI: 10.1145/1374376.1374465
  * [Fel17] Vitaly Feldman “A general characterization of the statistical query complexity” In _arXiv: 2110.05517_ , 2017 arXiv: http://arxiv.org/abs/1608.02198
  * [FGR+17] Vitaly Feldman et al. “Statistical algorithms and a lower bound for detecting planted cliques” In _Journal of the ACM (JACM)_ 64.2 ACM New York, NY, USA, 2017, pp. 1–37
  * [FGV16] Vitaly Feldman, Cristobal Guzman and Santosh Vempala “Statistical query algorithms for mean vector estimation and stochastic convex optimization” arXiv:1512.09170 arXiv, 2016 URL: http://arxiv.org/abs/1512.09170
  * [FPV18] Vitaly Feldman, Will Perkins and Santosh Vempala “On the complexity of random satisfiability problems with planted solutions” arXiv:1311.4821 arXiv, 2018 URL: http://arxiv.org/abs/1311.4821
  * [GAE07] David Gross, Koenraad Audenaert and Jens Eisert “Evenly distributed unitaries: On the structure of unitary designs” In _Journal of Mathematical Physics_ 48.5 American Institute of Physics, 2007, pp. 052104
  * [Got98] Daniel Gottesman “The Heisenberg representation of quantum computers” arXiv, 1998 arXiv:quant-ph/9807006
  * [GPM+14] Ian Goodfellow et al. “Generative adversarial nets” In _Advances in neural information processing systems_ , 2014, pp. 2672–2680
  * [Haf22] Jonas Haferkamp “Random quantum circuits are approximate unitary $t$-designs in depth $O\left(nt^{5+o(1)}\right)$” In _Quantum_ 6 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2022, pp. 795
  * [Har13] Aram W. Harrow “The church of the symmetric subspace” In _arXiv:1308.6595_ , 2013
  * [HBM+22] Jordan Hoffmann et al. “Training compute-optimal large language models” In _arXiv:2203.15556_ arXiv, 2022 DOI: 10.48550/ARXIV.2203.15556
  * [HE22] Dominik Hangleiter and Jens Eisert “Computational advantage of quantum random sampling” arXiv, 2022 DOI: 10.48550/ARXIV.2206.04079
  * [HH21] Jonas Haferkamp and Nicholas Hunter-Jones “Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions” In _Physical Review A_ 104.2 APS, 2021, pp. 022417
  * [HIN+22] Marcel Hinsche et al. “A single $T$-gate makes distribution learning hard” arXiv, 2022 arXiv: http://arxiv.org/abs/2207.03140
  * [HL09] Aram W. Harrow and Richard A. Low “Random quantum circuits are approximate 2-designs” In _Communications in Mathematical Physics_ 291.1 Springer, 2009, pp. 257–302
  * [Hun19] Nicholas Hunter-Jones “Unitary designs from statistical mechanics in random quantum circuits” arXiv, 2019 DOI: 10.48550/ARXIV.1905.12053
  * [IL90] Russell Impagliazzo and Leonid A. Levin “No better ways to generate hard NP instances than picking uniformly at random” In _Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science_ , 1990, pp. 812–821 vol.2 DOI: 10.1109/FSCS.1990.89604
  * [JEP+21] John Jumper et al. “Highly accurate protein structure prediction with AlphaFold” In _Nature_ 596.7873 Nature Publishing Group, 2021, pp. 583–589 URL: https://doi.org/10.1038/s41586-021-03819-2
  * [JSA16] Majid Janzamin, Hanie Sedghi and Anima Anandkumar “Beating the perils of non-convexity: Guaranteed training of neural networks using tensor methods” arXiv, 2016 arXiv:1506.08473
  * [Kea93] Michael Kearns “Efficient Noise-Tolerant Learning from Statistical Queries” In _Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing_ , STOC ’93 San Diego, California, USA: Association for Computing Machinery, 1993, pp. 392–401 DOI: 10.1145/167088.167200
  * [KG15] Richard Kueng and David Gross “Qubit stabilizer states are complex projective 3-designs” In _arXiv:1510.02767_ , 2015 arXiv:1510.02767
  * [Kha93] Michael Kharitonov “Cryptographic hardness of distribution-specific learning” In _Proceedings of the twenty-fifth annual ACM symposium on Theory of computing_ , 1993, pp. 372–381
  * [KLN+11] Shiva Prasad Kasiviswanathan et al. “What can we learn privately?” In _SIAM Journal on Computing_ 40.3, 2011, pp. 793–826 DOI: 10.1137/090756090
  * [KMR+94] Michael J. Kearns et al. “On the learnability of discrete distributions” In _Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing_ , STOC ’94 Montreal, Quebec, Canada: ACM, 1994, pp. 273–282 DOI: 10.1145/195058.195155
  * [Kna88] Stefan Knabe “Energy gaps and elementary excitations for certain VBS-quantum antiferromagnets” In _Journal of Statistical Physics_ 52.3 Springer, 1988, pp. 627–638
  * [KV94] Michael J. Kearns and Umesh Vazirani “An introduction to computational learning theory” MIT press, 1994
  * [LMN93] Nathan Linial, Yishay Mansour and Noam Nisan “Constant depth circuits, Fourier transform, and learnability” In _Journal of the ACM (JACM)_ 40.3 ACM New York, NY, USA, 1993, pp. 607–620
  * [LSS14] Roi Livni, Shai Shalev-Shwartz and Ohad Shamir “On the computational efficiency of training neural networks” arXiv, 2014 arXiv: http://arxiv.org/abs/1410.1141
  * [MNK+18] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa and Keisuke Fujii “Quantum circuit Learning” arXiv:1803.00745 In _Physical Review A_ 98.3, 2018, pp. 032309 DOI: 10.1103/PhysRevA.98.032309
  * [Mon17] Ashley Montanaro “Learning stabilizer states by Bell sampling” In _arXiv:1707.04012_ , 2017 arXiv:1707.04012
  * [Nac96] Bruno Nachtergaele “The spectral gap for some spin chains with discrete symmetry breaking” In _Communications in Mathematical Physics_ 175.3 Springer, 1996, pp. 565–606
  * [Nan21] Mikito Nanashima “A theory of heuristic learnability” optissn: 2640-3498 In _Proceedings of Thirty Fourth Conference on Learning Theory_ PMLR, 2021, pp. 3483–3525 URL: https://proceedings.mlr.press/v134/nanashima21a.html
  * [SBG+19] Maria Schuld et al. “Evaluating analytic gradients on quantum hardware” arXiv:1811.11184 In _Physical Review A_ 99.3, 2019, pp. 032331 DOI: 10.1103/PhysRevA.99.032331
  * [Sha17] Ohad Shamir “Distribution-specific hardness of learning neural networks” arXiv, 2017 arXiv:1609.01037
  * [Spa98] James C. Spall “An overview of the simultaneous perturbation method for efficient optimization” In _Johns Hopkins APL Technical Digest_ 19.4, 1998, pp. 11
  * [SVW16] Jacob Steinhardt, Gregory Valiant and Stefan Wager “Memory, communication, and statistical queries” In _COLT_ , 2016, pp. 1490–1516
  * [TD02] Barbara M. Terhal and David P. DiVincenzo “Classical simulation of noninteracting-fermion quantum circuits” In _Physical Review A_ 65.3, 2002, pp. 032325 DOI: 10.1103/PhysRevA.65.032325
  * [Val09] Leslie G. Valiant “Evolvability” In _Journal of the ACM_ 56.1, 2009, pp. 1–21 DOI: 10.1145/1462153.1462156
  * [Val12] Leslie G. Valiant “Quantum circuits that can be simulated classically in polynomial time” In _SIAM Journal on Computing_ Society for Industrial and Applied Mathematics, 2012 DOI: 10.1137/S0097539700377025
  * [Val84] Leslie G. Valiant “A theory of the learnable” In _Proceedings of the sixteenth annual ACM symposium on Theory of computing_ , STOC ’84 New York, NY, USA: Association for Computing Machinery, 1984, pp. 436–445 DOI: 10.1145/800057.808710