Sampling and the complexity of nature

Peer-reviewed publications

• Peer-reviewed publications include work on phononic probing [Han+15], toy models [RHH18], direct certification [Han+17], and quantum-speedup architectures [Ber+18].These works appear in Physical Review A, the British Journal for the Philosophy of Science, Quantum Science and Technology, and Physical Review X.Source: Peer-reviewed publications · p. 5
• Further peer-reviewed publications address anticoncentration [Han+18], device-independent certification [Han+19], and the average-case hardness of contracting projected entangled pair states [Haf+20].The listed venues are Quantum, Physical Review Letters, and Physical Review Research.Source: Peer-reviewed publications · p. 5
• Additional peer-reviewed work covers quantum certification and benchmarking [EH+20] and easing the Monte Carlo sign problem [Han+20].The latter is published in Science Advances and is identified with arXiv: 1906.02309.Source: Peer-reviewed publications · p. 5

Preprints

• The preprints concern analogue quantum simulation [HCT17], quantum advantage from short-time Hamiltonian dynamics [Haf+19], and pinned QMA [Nag+20].All three entries are dated 2017–2020 and identified by arXiv numbers.Source: Preprints · p. 6

What is the complexity of nature?

• The thesis investigates when quantum sampling experiments can be simulated on classical computers, using the Hong-Ou-Mandel experiment as physical motivation.Quantum measurement samples from Born-rule distributions, so simulating an experiment means reproducing its output distribution.Source: What is the complexity of nature? · p. 12, The complexity of physics: simulating… · p. 14

The Hong-Ou-Mandel experiment

• Indistinguishable photons interfere destructively at a beam splitter, eliminating coincidence outcomes and producing photon bunching.Hong, Ou, and Mandel observed the corresponding coincidence-count dip as photon distinguishability was varied.Source: §1.1 · pp. 13–14

The complexity of physics: simulating quantum experiments

• Boson-sampling output probabilities are hard to compute because they involve matrix permanents, whose approximation is #P-hard [Sch08], and sampling the distribution is also intractable [AA13].The permanent captures constructive and destructive interference across a combinatorially growing number of photon paths.Source: §1.1 · p. 15

The physics of complexity: interference and entanglement

• Quantum Monte Carlo fails in sign-problem regimes because destructive interference requires estimating precise path-interference patterns rather than merely counting paths.Classical pseudo-random sampling can approximate path counts, but the interference pattern quickly becomes intractable.Source: The physics of complexity:… · p. 16
• Tensor networks overcome sign problems in some settings but become inefficient when entanglement grows dynamically or when evaluating properties in higher dimensions, where the task is #P-hard [Sch+07; Haf+20].They efficiently describe states with little local entanglement, while computing observables or outcome probabilities is efficient only in one dimension.Source: §1.2 · p. 17

The computational power of quantum systems

• Quantum computers provide universal quantum simulation and outperform classical algorithms on selected tasks, including database search and integer factorization [Gro96; Sho94; Sho97].Local quantum operations and Trotter decomposition enable controlled simulation of locally interacting quantum systems, while finite precision is sufficient and errors can be corrected.Source: The computational power of quantum… · pp. 17–18

Simulating quantum systems using classical sampling

• Quantum Monte Carlo provides a classical sampling framework for estimating quantum-system properties, where the quantum sign problem appears as its practical manifestation.The severity of the sign problem depends strongly on the basis used to represent the Hamiltonian, linking representation choices to both simulation complexity and algorithm design.Source: Simulating quantum systems using… · p. 26
• Computationally meaningful measures assess the severity of the sign problem and support optimization over meaningful basis sets.These measures address how far the sign problem can be eased for a given system, while estimating its severity is generically as hard as performing the simulation itself.Source: Simulating quantum systems using… · p. 26
• Numerical optimization studies the sign problem under local basis choices for physically relevant simple models.The analysis tests whether practical basis changes can reduce the sign problem in concrete Quantum Monte Carlo simulations.Source: Simulating quantum systems using… · p. 26
• Finding a sign-optimal basis is computationally hard, making the intrinsic degree of a system’s sign problem intractable to determine.The thesis identifies a fundamental obstacle: even assessing the optimal simulation representation reproduces the hardness of simulating quantum devices.Source: Simulating quantum systems using… · p. 26
• Quantum sampling hardness is linked to approximate output-probability computation and strong simulation, providing the complexity-theoretic basis for supremacy experiments.The required evidence must exclude every efficiently runnable classical algorithm, not merely outperform existing classical methods.Source: Simulating quantum systems using… · p. 29

Basics of computational complexity theory

• Computational complexity compares worst-case runtimes under resource restrictions, with P containing efficiently solvable classical decision problems and NP containing efficiently verifiable ones.The thesis uses this framework to seek quantum-classical separations while retaining tasks realizable and error-resilient on near-term devices.Source: Basics of computational complexity… · pp. 30–31

2.1 Where look for a quantum-classical separation?

• Quantum and classical computation are formalized as BQP and BPP, with quantum circuits generalizing reversible classical circuits through unitary evolution and measurement.Quantum computation is intrinsically randomized by measurement, whereas classical circuits require externally supplied random bits.Source: §2.1 · pp. 31–33

Computing acceptance probabilities of randomized algorithms

• Classical acceptance probabilities are #P-complete, while quantum probabilities use signed functions taking values in {+1, −1}, enabling destructive interference and path cancellation.Hadamard-Toffoli universality connects quantum amplitudes to signed sums, whereas classical randomized computation counts accepting random inputs.Source: Computing acceptance probabilities of… · pp. 34–35
• Quantum-circuit success probabilities are absolute values of normalized GapP gaps, whereas classical success probabilities are fractions of accepting paths of #P functions.Because #P is contained in GapP, the text identifies classical computations as a strict subset of quantum computations, with the difference emerging in approximation complexity.Source: Computing acceptance probabilities of… · p. 36

2.2 Approximating GapP

• Approximating a #P gap within any constant multiplicative error is GapP-hard, yielding P^Apx·cGapP = P^GapP for every c ∈ (0, 1).The reduction exploits the sign guaranteed by relative-error approximation to recover the gap’s bits iteratively.Source: §2.2 · pp. 37–38
• Approximating ngap(f)^2 within any relative error ϵ < 1/2 is GapP-complete, despite quantum output probabilities being nonnegative [BMS16].The proof uses relative-error approximations to certify successive guesses of the underlying gap, with the procedure halting after O(n) steps when the correct choices are made.Source: §2.2 · pp. 38–39

2.3 Approximating #P: Stockmeyer’s algorithm

• Stockmeyer’s algorithm approximately counts accepting paths of #P functions with small multiplicative error from the third level of the polynomial hierarchy, motivating classical–quantum sampling separations.The text contrasts this with the difficulty of relative-error approximation for GapP sums, whose positive and negative contributions can cancel.Source: §2.3 · p. 40

The polynomial hierarchy

• The polynomial hierarchy generalizes P and NP through alternating existential and universal quantifiers, with the conjecture that its successive levels are strict.This hierarchy provides the complexity-theoretic framework for claims about quantum supremacy and approximating #P functions.Source: The polynomial hierarchy · pp. 40–41

Stockmeyer’s approximate counting algorithm

• Stockmeyer’s algorithm approximates exponentially large counts to inverse-polynomial multiplicative error within the third level Δp_3 ⊆ PH.The method uses NP-oracle-accessible hashing to estimate accepting computations, then amplifies the approximation to 1 + 1/poly(n).Source: Stockmeyer’s approximate counting… · pp. 42–43

The complexity of Stockmeyer’s algorithm

• Toda’s theorem and multiplicative-approximation inclusions separate approximating GapP functions from approximating #P functions, yielding evidence for an exponential quantum–classical hardness gap.The text identifies this difference as the quantum sign problem and uses it to support a conditional exponential separation for sampling tasks.Source: The complexity of Stockmeyer’s algorithm · pp. 43–44

Sampling versus approximating outcome probabilities

• Stockmeyer’s theorem converts output-probability approximation for derandomizable classical samplers into a 1 − 1/poly(|y|)-multiplicative approximation, linking sampling directly to probability estimation.This connection forms the basis of the subsequent sampling-hardness proofs.Source: Sampling versus approximating outcome… · pp. 45–46

Some history

• Earlier work connected efficient probability computation or sampling for restricted quantum circuits to unlikely complexity consequences, including polynomial-hierarchy collapse or BQP ⊂ AM [TD04] [Nes11] [SB09] [BJS10] [AA13].Postselection and its equivalence with PP also supplied a key ingredient in these arguments [Aar05].Source: Some history · p. 46, §2.4 · p. 47

2.4 Quantum random sampling

• The chapter provides strong complexity-theoretic evidence that sampling random computations from certain quantum circuit families is classically hard.Instances are random circuits drawn from a family at size n, with sampling performed from their output distributions.Source: §2.4 · p. 47
• The relevant families include random universal circuits, IQP circuits, and boson sampling, with IQP instances including commuting diagonal constructions such as Z, CZ, and CCZ circuits [BMS16].The accompanying circuit definitions specify random gates for universal circuits, Hadamard-diagonal commuting circuits for IQP, and passive linear optics for boson sampling.Source: §2.4 · p. 47, Figure 2.3 · p. 48
• Quantum random-sampling schemes generate measurement outcomes from randomly selected circuits or optical networks, including boson sampling and random circuit sampling.Boson sampling injects n photons into m polynomially many modes transformed by a Haar-random unitary, while random circuit sampling samples from pS(C) = |⟨S|C|0⟩|2.Source: §2.4 · pp. 48–49

Strongly simulating random quantum computations

• Random circuit, IQP, and boson-sampling families commonly have GapP-hard output probabilities, making strong classical simulation computationally intractable.For boson sampling, probabilities are squared moduli of permanents, whose multiplicative approximation remains #P-hard; IQP probabilities connect to hard Ising-model partition functions.Source: Strongly simulating random quantum… · pp. 50–51

2.5 The complexity of quantum random sampling

• The general sampling-hardness strategy reduces efficient classical sampling to approximate probability computation via Stockmeyer’s algorithm, whose consequence would be an unlikely third-level polynomial-hierarchy collapse.The argument requires worst-case GapP-hardness of approximating circuit success probabilities within a constant relative error.Source: §2.5 · pp. 51–52, Proof of exact sampling hardness:… · p. 53

Proof of exact sampling hardness: worst-case hardness

• If a circuit family has output probabilities that are GapP-hard to approximate within constant multiplicative error, efficient exact sampling would collapse the polynomial hierarchy to its third level.The proof uses Stockmeyer’s algorithm to infer probability estimates from a derandomizable sampler.Source: Proof of exact sampling hardness:… · p. 52

Multiplicative-error sampling hardness

• The same hardness argument extends to constant multiplicative-error sampling, because Stockmeyer estimation composes with the sampler’s multiplicative approximation.Under suitable constants c and d, an efficient sampler would yield a GapP-hard multiplicative approximation and collapse the polynomial hierarchy.Source: Multiplicative-error sampling hardness · pp. 53–54

Errors in quantum devices

• Realistic state-preparation, gate, crosstalk, and measurement errors induce additive state deviations, while trace distance upper-bounds the total-variation distance of fixed measurement outcomes.This motivates additive-error notions for physical devices, since additive errors need not preserve the sign of quantities or their relative scale.Source: Errors in quantum devices · pp. 54–55, Multiplicative-error sampling hardness · p. 54
• As the trace-distance error approaches 1, the uniform distribution becomes an allowed approximation and makes sampling classically easy, exposing the limitation of broad additive-error guarantees.The proof burden grows because hardness must hold throughout an entire error neighborhood rather than at a single target distribution.Source: Errors in quantum devices · pp. 55–56

From multiplicative to additive robustness

• With constant additive error, approximating quantum success probabilities to inverse-polynomial additive precision is only BQP-complete, whereas inverse-exponentially small additive precision remains GapP-hard.Therefore, polynomial-hierarchy-collapse arguments still require relative-error or exponentially small additive-error hardness.Source: From multiplicative to additive… · p. 57
• Additive robustness requires hardness across a constant fraction of reasonably large output probabilities, formalized through average-case hardness and anticoncentration.Unlike multiplicative errors, additive error is a global budget that can be concentrated on selected probabilities, so hardness cannot be hidden in isolated tiny probabilities.Source: From multiplicative to additive… · p. 57

Additive-error sampling hardness

• The proof hides queried instances by appending uniformly random Pauli-X gates, making the relevant outcome indistinguishable from a uniformly random one to the adversarial sampler.This hiding property holds naturally for many random circuit families, including universal Haar-random circuits.Source: Additive-error sampling hardness · pp. 59–60
• Under hiding, anticoncentration, and approximate average-case hardness, an efficient classical sampler within constant ℓ1 error would collapse the polynomial hierarchy.The theorem applies when the sampler achieves ∥p − p(C)∥ℓ1 ≤ γ/8 = ϵ on randomly drawn circuits.Source: Additive-error sampling hardness · p. 62
• For boson sampling, collision-free postselection enables hardness because a constant fraction of outcomes remains collision-free when m scales appropriately with n.If m ∈Ω(n^5 log(n)^2), Haar-random unitary submatrices approach complex Gaussian matrices, and Stockmeyer estimates their probabilities to recover a #P-hard permanent problem.Source: Additive-error sampling hardness · p. 64
• Additive-error sampling hardness requires approximate average-case hardness, hiding, and anticoncentration; approximate average-case hardness remains conjectural for all such schemes.The conjecture is considered plausible for GapP functions because cancellations can make values much smaller than the underlying #P path counts.Source: §2.6 · p. 65

2.6 Summary

• The chapter connects weak sampling and strong probability approximation through Stockmeyer’s algorithm and the polynomial hierarchy, establishing classical hardness for certain random quantum output distributions.Making this hardness robust to total-variation additive errors additionally requires approximate average-case hardness, hiding, and anticoncentration.Source: §2.6 · p. 65

Closing gaps: anticoncentration

• Exact average-case hardness is known for many proposed random-circuit sampling schemes, but existing techniques are unlikely to establish the needed approximate version.Anticoncentration is more tractable and is known for many circuit families, though it remains elusive for boson sampling.Source: §3.1 · p. 67

3.1 Anticoncentration

• Unitary 2-designs anticoncentrate, and nearest-neighbour universal random circuits achieve anticoncentration in linear depth, motivating two schemes for locally controllable platforms.The linear-depth scaling follows the ballistic spread of correlations in one-dimensional architectures.Source: §3.1 · pp. 67–68

The Haar measure and designs on the unitary group

• Unitary k-designs capture pseudorandomness by matching the first k Haar moments, while exact or approximate k-designs also imply corresponding lower-order designs.Approximating the full n-qubit Haar measure requires exponentially many gates, motivating polynomial-size design-based circuit families.Source: The Haar measure and designs on the… · pp. 68–70

Anticoncentration of 2-designs

• Approximate unitary 2-designs anticoncentrate their computational-basis success probabilities, and the same theorem applies to relative ϵ-approximate state 2-designs.The proof combines bounded second moments with the Paley-Zygmund inequality; a relative approximate 1-design condition is crucial for a nontrivial constant lower bound.Source: Anticoncentration of 2-designs · pp. 70–71

Moments of the Haar measure

• Haar-random output probabilities approach the exponential Porter–Thomas distribution as D grows, with moments that can also be derived using Schur-Weyl duality for state and unitary 2-designs.The moments are obtained either from random-matrix methods or from the symmetric-subspace moment operators.Source: Moments of the Haar measure · pp. 73–74

3.2 A quantum speedup recipe

• The speedup recipe combines anticoncentration, #P-hard strong classical simulation, and an average-case hardness conjecture following the Stockmeyer-based framework of [AA13] [BMS16].For universal random circuits, [Boi+18] relates output probabilities to an imaginary-time random-Ising partition function, while Lemma 3.7 establishes the required hardness for a broad gate-set class.Source: §3.2 · pp. 74–76
• Universal random circuits in one dimension anticoncentrate at depth O(n log(1/ϵ)), while suitable finite universal gate sets have #P-hard output-probability approximation at O(n) depth.The anticoncentration result follows because these circuits form approximate unitary 2-designs; the hardness holds up to relative error 1/4 for gate sets satisfying the stated synthesis conditions.Source: §3.2 · pp. 75–77
• The gate-set hardness extension remains limited: arbitrary synthesis may incur polynomial depth overhead, and gate-set independence for postselected circuits is unresolved.Under counting ETH, Solovay–Kitaev synthesis requires Ω(n^α) overhead for some α > 0 in the relevant setting.Source: §3.2 · p. 77
• Commuting diagonal circuits with discrete phases form a state 2-design, anticoncentrate, achieve postC = postBQP with postselection, and admit an Ising-partition-function average-case formulation.These circuits can be implemented in linear depth with long-range interactions or nearest-neighbour SWAPs.Source: §3.2 · pp. 77–78
• The speedup recipe guarantees anticoncentration from the exact 2-design property, yet only approximate worst-case hardness is established and approximate average-case hardness remains conjectural.This limitation applies to the cases summarized in Table 3.1, including Clifford circuits forming exact 2-designs.Source: §3.3 · p. 78, §3.2 · p. 78

3.3 Average-case hardness

• Average-case hardness is difficult under natural distributions: for random 3SAT, efficient guessing rules out hardness except near the threshold m/n ∼4.26.Positive average-case hardness results are known for counting problems via random self-reducibility, which reduces arbitrary instances to random ones.Source: §3.3 · pp. 78–79

Random self-reducibility of the permanent

• Random self-reducibility of the permanent uses polynomial interpolation and Reed–Solomon error correction, reducing worst-case computation to random instances on a 3/4 + 1/poly(n) fraction.Infinite fields require small interpolation parameters to control distribution shifts and stable interpolation to tolerate finite-precision errors.Source: Random self-reducibility of the… · pp. 79, 81, 83

Average-case hardness of quantum success probabilities

• Quantum-circuit reductions achieve worst-to-average-case robustness to additive errors 2^-poly(n), but evaluate approximating numbers that need not be valid circuit success probabilities.The Taylor-truncation approach uses K = poly(n), while rational-function interpolation stays within the unitary group and generalizes Berlekamp–Welch decoding.Source: Average-case hardness of quantum… · p. 85
• For two-dimensional circuits of depth √n, interpolation robustness scales as exp(−Ω(n3 log n)), while general robustness is exp(−Ω(mϵ−1)).Here m is the number of gates, and (0, ϵ] is the interval over which success probabilities are evaluated.Source: Average-case hardness of quantum… · p. 86

3.4 Discussion and conclusion

• Unitary 2-designs imply anticoncentration in linear depth for one-dimensional local random circuits and in depth O(√n) for two-dimensional nearest-neighbour circuits.The two-dimensional result follows because nearest-neighbour universal circuits form unitary 2-designs in depth O(√n).Source: §3.4 · p. 86
• Average-case reductions require continuous gate distributions and therefore do not trivially extend to discrete gate sets such as Clifford circuits.For IQP circuits, the edge weights must be sampled from the unit circle rather than a discrete set of angles.Source: §3.4 · p. 87

4.1 Simulating quantum systems using other quantum systems

• Quantum simulators are restricted quantum devices whose practical computational advantage requires architecture-specific sampling schemes and complexity-theoretic grounding.The framework targets experimentally available platforms, including optical-lattice and ion-trap simulators.Source: §4.1 · pp. 89–90

Cold atoms in optical lattices

• Cold-atom optical lattices support coherent evolution of hundreds to thousands of atoms and access two-dimensional regimes where classical simulation methods fail for practical purposes.Their tunable interactions and local probing make them suitable for quantum simulation across broad parameter regimes.Source: Cold atoms in optical lattices · pp. 92–93

4.2 Short-time Hamiltonian dynamics in optical lattices

• Short-time, translation-invariant Hamiltonian evolution followed by standard-basis measurements can realize a bona fide quantum speedup in cold-atom architectures.The protocol is designed to satisfy experimentally feasible cold-atom requirements while matching the complexity standards of universal and IQP circuit sampling.Source: §4.2 · p. 93, Experimental desiderata · p. 94

Experimental desiderata

• The architecture is designed around translation-invariant interactions, simple periodic interaction graphs such as cubic or hexagonal lattices, and translation-invariant measurements requiring little control.The measurement stage remains experimentally challenging, especially for individually addressing atoms in different bases.Source: Experimental desiderata · p. 94

A translation-invariant quantum sampling protocol

• The protocol trades universal random-circuit depth for qubit count, using Haar-random initial phases, translation-invariant nearest-neighbor Ising evolution for constant time, and X-basis measurements [Haf+19].It thereby satisfies the stated desiderata of simple translation-invariant interactions, simple lattice geometry, and minimally controlled translation-invariant measurement.Source: A translation-invariant quantum… · pp. 94–95, Experimental desiderata · p. 94

Hardness of strong simulation

• Approximating pβ(0) up to relative error 1/4 + o(1) on an n × m square lattice is GapP-hard for m ∈ O(n^2), via postBQP universality and hiding.The construction encodes universal Clifford+T circuits through measurement-based computation and gate teleportation.Source: Hardness of strong simulation · p. 97

Anticoncentration and closeness to the Porter-Thomas distribution

• For both n × n and n × n^2 lattices, the anticoncentration fraction quickly approaches 1/e with rapidly decreasing variance, while output distributions approach Porter–Thomas statistics as n increases.The numerical tests used 100 random instances for each system size and exactly evaluated the fraction of output probabilities satisfying the anticoncentration condition.Source: Anticoncentration and closeness to the… · pp. 99–100, Figure 4.4 · p. 99
• Effective circuits form relative ε-approximate unitary 2-designs on an n × O(n) square lattice, proving anticoncentration for the sampling architecture [Haf+19].The result applies after measuring the first m−1 columns in the X-basis, with the effective unitary acting on the last column.Source: Anticoncentration and closeness to the… · p. 101
• The output distribution pβ of Protocol 4.1 anticoncentrates by combining the previous chapter’s anticoncentration theorem with identity (4.14).Source: Anticoncentration and closeness to the… · p. 101

4.3 Ion trap quantum simulation of IQP circuits

• An ion-trap implementation exploits high-fidelity local control and long-range gates by realizing IQP circuits with XX couplings and on-site X rotations in a single interaction round.The architecture supports up to around 50 ions, making efficient use of limited qubit numbers central to the design.Source: §4.3 · p. 102, An IQP protocol for trapped ions · p. 103

Experimental methods in ion-trap architectures

• Ion-trap operations provide parallel X−Y rotations, individual Z rotations, global Mølmer–Sørensen entangling gates, and arbitrary individual addressing through laser and spectroscopic control.Source: Experimental methods in ion-trap… · pp. 102–103

An IQP protocol for trapped ions

• The protocol uses single-qubit Z gates and global Mølmer–Sørensen gates to generate uniformly distributed, mutually decoupled IQP weights, with an alternative implementation realizing arbitrary circuits in depth k · n.Lemma 4.5 produces uniform marginals and requires linear-depth repetition for full decoupling; Lemma 4.6 achieves depth k · n using k · n(n + 1)/2 random bits but is experimentally more expensive.Source: An IQP protocol for trapped ions · pp. 103, 106

4.4 Reducing the experimental requirements

• A total-variation distance of 1/5 can support the hardness proof under a conjecture that 0.07 of instances are approximately average-case #P-hard.Choosing γ = 1/e, ε = γ/8, and δ = γ/2 yields a relative-error 1/4 + o(1) approximation with probability at least 0.3.Source: §4.4 · p. 108

4.5 Conclusion and outlook

• The chapter develops simulator-compatible sampling schemes that bridge rigorous hardness results with quantum architectures already outperforming classical simulation algorithms.The dynamical-simulator scheme uses constant-depth evolution of a disordered product state followed by global X-basis measurement, while its space-time tradeoff transfers quantum power to measurements and two-local gates.Source: §4.5 · pp. 108–109
• Standard-basis measurements enable robust sampling-hardness arguments, but these rely on an exponentially large sample space and do not directly measure physical properties such as correlators or magnetization [Tro+12].With smaller sample spaces, constant total-variation distance could permit constant or inverse-polynomial probability approximations, making computation feasible within BQP and weakening the polynomial-hierarchy-collapse argument.Source: §4.5 · p. 109
• Digital ion-trap simulators efficiently implement IQP circuits using high-precision local control, arbitrary-pair entanglement, and a decoupling procedure with random local Z-flips.The available fixed-angle X−Y rotations and global Mølmer-Sørensen gate motivate the procedure, while scalability is limited because current ion-trap simulators reach up to 50 ions [Zha+17].Source: §4.5 · p. 109
• The discussion concludes rigorous hardness results for quantum random sampling and turns to the problem of certifying a sampling device’s correct functioning.This passage marks the transition to the thesis’s next theme: verification of quantum sampling devices.Source: §4.5 · p. 109

The question of verification [Han+19]

• Quantum sampling verification asks whether a device’s outputs are sufficiently close to the ideal distribution defined by PC(S) = |⟨S|C|0⟩|2 using only feasible samples.The central challenge is convincing a sceptical certifier that a device samples correctly even when the computation’s outcomes cannot be reproduced classically.Source: Can we efficiently certify devices… · p. 113, The question of verification [Han+19] · p. 113, Figure 5.1 · p. 113

5.1 Traditional approaches to certification

• Traditional predict-and-measure verification fails for classically intractable experiments, while component-level certification leaves a composition loophole.Predicting outcomes becomes infeasible as system size grows, and certifying individual gates, preparations, or measurements cannot rule out unwanted effects between components.Source: §5.1 · pp. 114–115

5.2 Classifying quantum certification

• The framework classifies certification by which state preparations, measurements, and operations are trusted, thereby defining the boundary between the quantum device and its user.For this thesis, the user initiates the device and classically processes its outputs in a single round; protocol costs include measurement, sample, and post-processing complexity.Source: §5.2 · pp. 117–118
• Tomographic methods provide detailed device-dependent information, whereas device-independent methods treat the apparatus as a black box, require more resources, and are preferred for closing verification loopholes.Intermediate semi-device-dependent approaches relax trust assumptions, but typically incur substantial sample or measurement costs.Source: §5.2 · pp. 119–120

5.3 Verifying quantum samplers

• The sampling-verification problem is the sampling analogue of deciding whether efficient certification exists despite the inability to predict individual outcomes.The thesis identifies cryptographic and physics-motivated settings for analyzing this task, including secret-hiding schemes whose recovered secret acts like an NP proof [SB09].Source: §5.1 · p. 116, §5.3 · p. 120

Device-independently verifying quantum samplers

• In the device-independent setting, a classical test receives i.i.d. samples from a black-box sampler and must accept when Q is ϵ-close in total variation to PC or reject otherwise.This formulation treats the circuit prescription as input and the sampler’s outputs as classical data only, with verification expressible through weak-membership testing [Aol+15] [Han+17].Source: verifying quantum sampling devices · p. 120, Figure 5.2 · p. 121, §5.3 · p. 121

5.3 Verifying quantum samplers

• Verification tests impose completeness and soundness conditions separated by a finite gap α, with weak-membership verification requiring acceptance near the target and rejection outside the prescribed distance.Minimal verification only requires accepting the exact target and rejecting distributions beyond the distance threshold, while allowing arbitrary behavior in between.Source: §5.3 · pp. 121–122

Measurement-device-dependent quantum certification

• Measurement-device-dependent certification assumes calibrated high-fidelity measurements, enabling state verification through single-qubit measurements, Pauli correlators, and full quantum-state tomography.For the architecture developed in Section 4.2, the resource cost of rigorous measurement-device-dependent verification is asymptotically constant.Source: Measurement-device-dependent quantum… · p. 122, §5.3 · p. 123

6.1 Introduction

• Device-independent certification from classical samples is inefficient for boson, universal random-circuit, IQP, and postselected-universal 2-design sampling schemes, even with unbounded computational power.The same anticoncentration property used in approximate-sampling hardness proofs prevents non-interactive, sample-efficient certification.Source: §6.1 · pp. 126–128

Proof sketch

• For exponentially flat target distributions, minimal certification requires exponentially many samples, whereas polynomially supported truncated distributions permit sample-efficient certification.The lower bound is essentially controlled by 1/√p0, where p0 is the largest target probability; quantum-supremacy distributions are exponentially flat with high probability.Source: Proof sketch · p. 128

Setup and definitions

• The analysis defines min-entropy as H∞(P) = −log max_i p_i and uses ℓp norms and Rényi entropies to state asymptotic certification bounds.These quantities provide the notation for relating distribution flatness and support to certification sample complexity.Source: Setup and definitions · p. 129

6.2 No certification of flat distributions

• The certification bounds derive from the Valiant–Valiant optimal sample complexity, expressed through the ℓ2/3 quasi-norm after removing the largest probability and a tail of weight at most ϵ.Bounds in terms of min-entropy and support imply square-root-of-sample-space lower bounds for high-min-entropy distributions and polynomially many samples for polynomial support.Source: §6.2 · pp. 129–130
• Postselected distributions yield certification lower bounds whenever the retained subspace has sufficiently large weight, with a non-trivial bound requiring P(F) > 2ϵ.The argument formalizes why samples outside the postselected region do not help distinguish distributions differing there.Source: §6.2 · pp. 131–132

6.3 Quantum supremacy distributions are flat

• Anticoncentration does not alone guarantee high min-entropy, but the second-moment bounds used for prominent supremacy schemes do, making their output distributions effectively flat for certification analysis.A counterexample shows that anticoncentration can coexist with min-entropy at most log(2) with probability one.Source: §6.3 · p. 133, Second moments bound the min-entropy · p. 134

Second moments bound the min-entropy

• Exponentially small second moments imply high min-entropy with high probability and therefore exponential, rather than polynomial, certification sample complexity.The same second-moment property that supports sampling hardness also prevents efficient certification from classical samples.Source: Second moments bound the min-entropy · pp. 133–134

IQP circuits

• For IQP circuits, the established second-moment bound implies the min-entropy lower bound required by the certification lower-bound framework.The min-entropy statement holds with probability at least 1 − δ over the random IQP circuit.Source: §6.4 · p. 135

Universal random circuits and spherical 2-designs

• Any circuit family whose output states form a relative ˜ε-approximate spherical 2-design inherits the min-entropy bound, including depth O(n^2) + O(n log 1/˜ε) local random universal circuits.The result holds with probability at least 1 − δ over the sampled circuit.Source: Universal random circuits and… · p. 135, §6.4 · p. 136

6.4 Quantum supremacy distributions cannot be efficiently certified

• Boson sampling, IQP circuits, and suitable random universal-circuit schemes cannot be certified with polynomially many classical samples and a target-distribution description alone.The lower bounds hold with high probability over the random instance; the boson-sampling statement assumes m ∈ Θ(n^ν) under the stated hardness conditions.Source: §6.3 · p. 132, §6.4 · p. 136

6.5 Lower bounds for boson sampling

• The boson-sampling certification lower bound relies on Gaussian approximation of Haar submatrices and inherits explicit scaling and probability limitations from the underlying hardness argument [AA13].The result is exponentially likely for ν > 3, while for ν > 2 it is only polynomially likely and misses a small set of instances; the Gaussian-measure condition is provable for ν > 5 and conjectured for ν > 2.Source: §6.4 · p. 136, §6.5 · p. 138
• For boson sampling, efficient certification from classical samples is impossible in the regimes covered by the hardness argument, even under optimistic assumptions extending hardness beyond m ≥ c n^ν with ν > 2.The result fully covers the regime where boson sampling is provably hard, while part b. removes dependence on collision-free probability by restricting to ν > 3; the case 2 < ν ≤ 3 remains open.Source: §6.5 · pp. 138–141

6.6 Discussion

• The obstruction is high min-entropy or flatness: distributions spread over exponentially many outcomes cannot be minimally certified from polynomially many samples, even with unlimited computational power and a full target description.The same second-moment properties supporting approximate sampling hardness also prevent sample-efficient classical verification, motivating interactive, assumption-based, or partially quantum alternatives.Source: §6.5 · p. 140, §6.6 · p. 141, Hardness, certification, and flatness · pp. 141–142

Hardness, certification, and flatness

• Classical simulation and certification exhibit a flatness boundary: concentrated distributions can be efficiently simulated and certified, whereas exponentially flat distributions support hardness but require prohibitively many certification samples.Figure 6.3 identifies a possible middle regime in which distributions may be classically hard yet sample-efficiently certifiable.Source: Hardness, certification, and flatness · pp. 141–142, Figure 6.3 · p. 142

Practical verification of quantum

• Practical verification circumvents the no-go result by progressively relaxing protocol complexity, using assumptions, interactions, computational tests, or trusted measurement capabilities.Measurement-device-dependent protocols exploit accurate single-qubit measurements to provide a fidelity witness and direct fidelity estimation requiring only a constant number of state copies.Source: Hardness, certification, and flatness · p. 143, Practical verification of quantum · pp. 145–146

7.1 Sample-optimal classical verification

• Valiant and Valiant’s instance-optimal χ2-based identity test [VV17] achieves the necessary sample scaling up to constant factors in ϵ, but evaluating it requires exponentially many probabilities and is computationally inefficient.It remains an assumption-free certificate useful for small or intermediate-sized instances and as a benchmark for other certification tools.Source: §7.1 · pp. 146–147

7.2 Sample-efficient classical verification

• Cross-entropy-style verification uses polynomially many device samples and avoids the sampling no-go result, but requires exponential post-processing and cannot distinguish the target from arbitrary adversarial distributions.Its guarantees apply only to subclasses related to the target by specified noise conditions [Boi+18] [Bou+19].Source: §7.2 · p. 147

Heavy-outcome generation

• HOG is sample-efficiently verifiable because sampled outcomes can be compared with the median of the ideal probabilities, but its hardness relies on the strong QUATH conjecture.HOG verifies achievement of a hard task rather than total-variation proximity, and distributions can score well while remaining far from the target.Source: Heavy-outcome generation · pp. 148–149

Cross-entropy difference

• Cross-entropy difference equals 1 for the uniform distribution and vanishes for the ideal distribution under Porter–Thomas statistics, interpolating linearly for Qλ.It can be estimated efficiently from iid samples, but its total-variation guarantee requires entropy-increasing noise, a condition not checkable from fewer than exponentially many samples.Source: Cross-entropy difference · pp. 150–151

Cross-entropy fidelity

• Linear XEB resembles cross-entropy difference under random-circuit assumptions, yet it has no general total-variation bound and can be fooled efficiently for log-depth two-dimensional circuits.Its circuit-averaged value can also be used to estimate depolarization error under an uncorrelated-noise model.Source: Cross-entropy fidelity · pp. 152–153

Binned outcome generation

• Fine-grained binning improves HOG and cross-entropy measures by comparing observed and expected frequencies across polynomially many probability bins.For ideal sampling the binned measure is zero, and for nonideal distributions it converges to total-variation distance as the number of bins increases.Source: Binned outcome generation · pp. 153–154
• Binned outcome generation retains sample efficiency while converging to total-variation distance as the number of probability bins grows.For k bins, identity testing to error ϵ requires O(k/ϵ^2) samples, asymptotically optimally.Source: Binned outcome generation · p. 154, Figure 7.2

7.3 Efficient classical verification

• Sample-efficient classical verification methods compute overlaps or coarse-grained distances using the ideal output probabilities, whereas fully efficient verification seeks to avoid computing those probabilities.The latter approach uses cryptographic and additional complexity-theoretic assumptions but encounters limitations.Source: §7.3 · pp. 154–155

Cryptographic tests of computational quantumness

• Shepherd and Bremner’s IQP protocol [SB09] uses a certifier-chosen classical input and a hidden sample bias to efficiently certify a task beyond classical capability under cryptographic assumptions.The protocol is formulated for X-programs, whose instances can be represented by binary matrices when all nonzero Hamiltonian terms share a constant angle.Source: Cryptographic tests of computational… · p. 155
• The Shepherd–Bremner cryptographic test hides a string whose output bias separates quantum sampling from classical strategies, but relies on conjectured hardness and does not certify the correct distribution.For quadratic residue codes with θ = π/8, the quantum bias is cos^2(π/8) ≈ 0.854 versus 3/4 for the best known classical strategies [SB09].Source: Cryptographic tests of computational… · p. 156

7.3 Efficient classical verification

• A classical cheating strategy extracts the secret vector from the Shepherd–Bremner matrix with probability arbitrarily close to unity in empirically observed average time O(n^3), undermining that protocol [SB09].The strategy was later circumvented using a different approach than quadratic residue codes [YC20].Source: §7.3 · p. 157

Efficient state discrimination

• The row-norm estimator efficiently discriminates boson-sampling outputs from uniform and other informed distributions using outcome samples, despite only weak correlation with the permanent.It can be computed in time O(n^2), and differing fluctuations under boson-sampling and uniform sampling enable discrimination [AA14].Source: Efficient state discrimination · pp. 157–158

7.4 Efficient quantum fidelity witnessing

• With trusted single-qubit measurements, fidelity witnesses enable fully efficient verification of ground states of inverse-polynomially gapped Hamiltonians and can extend to universal quantum computations.Characterizing individual detectors avoids exponential scaling and can scale linearly with the number of measurement apparatuses [Han+17].Source: §7.4 · pp. 158–159

Efficiently verifying ground states of gapped Hamiltonians

• The ground-state protocol estimates local Hamiltonian-term energies and converts them into a fidelity-witness estimate, efficiently certifying preparations at least 1/poly(n) close in fidelity for polynomially gapped Hamiltonians.The witness W_ρ = 1 − H/∆ lower-bounds fidelity, and the same copies can subsequently be used for sampling readout if certification accepts.Source: Efficiently verifying ground states of… · pp. 160–162
• The ground-state protocol provides weak-membership certification for Hamiltonians with known inverse-polynomial gap and energy, with completeness and soundness error controlled by α.States above the fidelity threshold are accepted with probability greater than 1−α, while states below it are rejected with probability at least 1−α.Source: Application to universal computations · p. 164, Efficiently verifying ground states of… · p. 164

Application to universal computations

• The protocol verifies arbitrary universal quantum computations by certifying a pre-measurement cluster state using a parent Hamiltonian with ground-state energy E0 = −N and gap ∆ = 2.For square-lattice cluster states, the relevant star operators can be measured using single-qubit measurements, whereas arbitrary output-state parent Hamiltonians may be nonlocal and inefficient to estimate this way.Source: Application to universal computations · pp. 164–165

Application to quantum supremacy architectures

• The fidelity-witness protocol applies to quantum-simulation architectures and general IQP circuits, including states obtained by conjugating a cluster-state parent Hamiltonian.For the simulation architecture, the resulting state can be certified from mCS copies of the imperfect preparation; efficient single-qubit measurement decompositions require suitable interaction weights.Source: Application to quantum supremacy… · pp. 165–166

7.5 Rapid quantum fidelity estimation

• Rapid fidelity estimation certifies restricted quantum states with O(1/ϵ^2) samples and verifies quantum-supremacy output distributions with approximately 10^5 samples independent of qubit number.The method applies to states expressible as convex mixtures of efficiently measurable operators, including local-unitary equivalents of graph states.Source: §7.5 · pp. 167–168

Fidelity estimation protocol

• Rapid fidelity estimation is efficient when the target decomposition uses efficiently measurable bounded-spectrum operators and a classically samplable distribution over them.It estimates fidelity within additive error ϵ with high probability, thereby also providing bounds on trace distance.Source: Fidelity estimation protocol · p. 168, §7.5 · p. 169

Application to generalized graph states

• Generalized graph states are local-unitary equivalent to cluster states, enabling efficient random stabilizer generation and rapid certification through rotated single-qubit Pauli measurements.The stabilizer structure permits implementation of the rapid certification protocol for the supremacy architecture state |ϕβ⟩ = Uβ|0N⟩.Source: Application to generalized graph states · pp. 169–170

Discussion and outlook

• Rapid fidelity estimation trades quantum sample complexity O(n2) for O(1) against measurement-setting complexity rising from O(1) to O(1/ϵ2).The practical choice depends on whether switching settings or repeating a fixed setting is more costly.Source: Discussion and outlook · p. 171

7.6 Further approaches to the verification of quantum samplers

• For arbitrary-state certification, the optimal projective strategy has sample complexity log(1/δ)/ϵ, while stabilizer-state verification scales as n log(1/δ)/(2ϵ) under single-qubit restrictions [PLM18] [TM18] [MK20].Restricted measurements increase complexity through the spectral gap Δ(Ω), which is 2/n for the stabilizer strategy.Source: §7.6 · p. 172
• Weak-membership protocols avoid the near-total rejection caused by experimental infidelity in optimal exact-membership protocols, while arbitrary-state schemes scale roughly O(d/ϵ) [BOW19].Exact protocols become highly sensitive because realistic preparations do not attain unit acceptance probability.Source: §7.6 · p. 172, §7.7 · p. 173

7.7 Conclusion

• The fidelity witness for gapped-Hamiltonian ground states requires ˜O(n2/ϵ2) samples and becomes impractical for n ≳50, despite using only single-qubit measurements.Its drawbacks include a relatively small acceptance region and polynomial scaling in the number of qubits.Source: §7.7 · p. 174

Application to generalized graph states

• O(1/ϵ2) samples suffice for direct fidelity estimation of graph-state-equivalent supremacy states, improving by roughly two orders of magnitude over the fidelity witness near 50 qubits.The rapid protocol uses single-qubit measurements and iid preparations but has more limited applicability.Source: Application to generalized graph states · p. 170, §7.7 · p. 174

Bringing quantum supremacy to the lab

• Single-qubit measurements with iid state preparations enable fully efficient verification of quantum output states under experimentally motivated assumptions.The framework assumes precise single-qubit measurements and independently, identically distributed preparations.Source: §7.7 · p. 174, Bringing quantum supremacy to the lab · pp. 177–178

7.7 Conclusion

• The no-go result shows that provably speedup-producing samplers require exponentially many samples for efficient classical verification because their output distributions have small second moments.Cross-entropy is sample-efficient but gives rigorous total-variation bounds only under particular noise conditions and may require exponentially costly probability estimates.Source: §7.7 · pp. 173–174, Bringing quantum supremacy to the lab · p. 177

Complexity-theoretic foundations of sampling hardness

• Major open challenges include proving approximate average-case hardness, making sampling hardness robust to constant local noise, and finding efficiently verifiable distributions between exponentially flat and polynomially concentrated regimes.Noise robustness may require heralded errors, while verification seeks a possible middle ground with larger second moments.Source: Complexity-theoretic foundations of… · p. 178, §8.1 · p. 179, Verification · p. 180

Verification

• Verification tools may need to be custom-tailored to the specific device and sampling scheme, limiting when cross-entropy fidelity can rigorously certify the global distribution.This includes the cross-entropy fidelity used in the Google Quantum AI demonstration.Source: Verification · p. 180

8.2 Applications of quantum random sampling

• Gaussian boson sampling can estimate Franck–Condon factors and graph properties because its output probabilities are determined by Hafnians related to weighted perfect matchings.Its distribution favors denser subgraphs with more perfect matchings, supporting quantum-enhanced machine learning and related optimization problems [AB18; Brá+18; Sch+20; ABR18].Source: §8.2 · p. 180, §8.3 · p. 181

8.3 Simulating quantum supremacy classically

• Quantum supremacy distributions may support cryptography, certified random number generation, and hardware-level benchmarking because they are very flat and have large min-entropy.These applications are proposed in [Nik19] [Hua+19] [HKL20] [EH+20].Source: §8.3 · p. 181
• ∼40 photons are required before boson samplers may surpass currently available classical computers, after improved algorithms account for photon-loss scaling.Neville et al. [Nev+17] developed an approximate sampler, followed by the exact algorithm of Clifford and Clifford [CC18] with runtime O(n2n + poly(m, n)).Source: §8.3 · p. 182
• Noise can make quantum sampling efficiently simulatable by driving output distributions toward simple distributions, while realistic quantum advantage depends on the competition between classical algorithms and larger, less noisy devices.This has been studied for photon loss, partial distinguishability, mode mismatching, IQP circuits, and universal random circuits [OB18; GRS19; RSG18; RSG19; Moy+19; RRC16; BMS17; YG17; GD18; BSN17].Source: §8.3 · pp. 181–182

Estimating physical properties

• The Monte Carlo sign problem links the computational and practical obstructions to simulating quantum systems, motivating questions about when it is intrinsic or removable by changing descriptions [TW05].The work introduces a systematic, generally applicable, and practically feasible framework for easing the sign problem through physically equivalent but computationally inequivalent descriptions.Source: Estimating physical properties · pp. 185–186
• Quantum Monte Carlo uses classical sampling to efficiently approximate equilibrium properties of quantum many-body systems, especially expectation values in ground and thermal states.The part approaches the quantum–classical boundary from below, treating sampling as a computational tool for strong simulation rather than as the final output.Source: Estimating physical properties · pp. 185–186

9.1 Classical sampling algorithms

• Classical sampling methods transform uniform random bits into samples from prescribed discrete distributions, but their correctness and efficiency depend on perfect randomness and distribution-specific conditions.The reviewed methods are rejection sampling, marginal sampling, and Metropolis sampling.Source: §9.1 · pp. 186–187

Rejection sampling

• Rejection sampling is correct but can be inefficient: its runtime scales as O(|Ω|) in the basic case, while the rejection constant c measures proposal mismatch and controls acceptance time.Choosing an efficiently sampleable proposal q close to the target p improves efficiency, whereas exponentially large, highly uneven distributions can remain difficult.Source: Rejection sampling · pp. 187–188

Marginal sampling

• Marginal sampling decomposes sampling an exponentially large bit-string distribution into sequential biased coin flips, provided the required marginal probabilities can be computed efficiently.Efficiently computable probabilities alone may not suffice because marginals involve exponentially large sums; sparse output distributions can make the method feasible.Source: Marginal sampling · pp. 188–189

Metropolis sampling

• Metropolis-Hastings constructs a Markov chain with target stationary distribution p and yields correct samples after convergence when stationarity, uniqueness, and convergence conditions hold.Detailed balance provides a sufficient condition, and the Metropolis acceptance rule depends only on p(x′)/p(x), avoiding direct computation of normalized probabilities such as Boltzmann distributions.Source: Metropolis sampling · pp. 190–191
• Metropolis sampling converges efficiently when its Markov chain is irreducible and aperiodic and its spectral gap is at least inverse-polynomial in the number of degrees of freedom.Irreducibility can be ensured when every configuration is reachable with non-vanishing probability; proving rapid mixing is highly nontrivial.Source: Metropolis sampling · pp. 191–192

Classical Monte Carlo

• Classical Monte Carlo estimates observables from Metropolis samples without computing the partition function, while partition functions can be estimated through products of ratios at successive temperatures.The required sample count for a relative error grows with the variance normalized by the observable’s expectation; Jerrum and Sinclair’s method yields an FPRAS for specific models.Source: Classical Monte Carlo · p. 192, §9.2 · p. 193, Quantum Monte Carlo · p. 193

Quantum Monte Carlo

• Quantum Monte Carlo represents quantum expectation values as averages over a classical configuration distribution, requiring polynomial estimator variance and efficiently generated samples, typically via rapidly mixing Markov chains.World-line methods sample paths from an m-fold expansion of e−βH/m; diagonal observables can use closed paths, while non-diagonal observables require more difficult estimators.Source: Quantum Monte Carlo · pp. 193–194

9.3 The sign problem of Quantum Monte Carlo

• Negative or complex off-diagonal matrix elements turn quantum path weights into a normalized but nonpositive quasiprobability, causing the Quantum Monte Carlo sign problem and typically exponential sampling overhead.Replacing the quasiprobability with a suitable probability distribution reproduces sampling averages but generally increases runtime exponentially.Source: §9.3 · pp. 195–196
• The average sign can scale as e−βn∆f, making Quantum Monte Carlo simulations infeasible as particle number, inverse temperature, or free-energy density difference increases.The average sign is the ratio between the original system’s partition function and that of a corresponding stoquastic ‘bosonic system’.Source: §9.3 · p. 196

Curing the sign problem

• The sign problem is basis-dependent, motivating efficiently computable basis transformations that can eliminate negative weights in selected systems but must avoid exponentially costly eigenbasis constructions.Known cures include auxiliary-field, Jordan-Wigner, and Majorana transformations, as well as transformations exploiting dimerization [WHZ03] [OH14] [LJY15] [LJY16].Source: §9.3 · p. 197, Curing the sign problem · p. 197

Stoquastic Hamiltonians

• Stoquasticity—nonpositive off-diagonal Hamiltonian entries in a chosen basis—ensures nonnegative transfer-matrix weights and therefore a sign-problem-free world-line representation.For sufficiently large m, the transfer matrix has nonnegative entries, so the path amplitudes and quasiprobabilities are nonnegative.Source: Stoquastic Hamiltonians · p. 198, Figure 9.4 · p. 198
• Finding a stoquastic representative under allowed unitary basis transformations is an NP-complete curing problem for 2-local Hamiltonians with additional local fields [MLH19] [Kla+19].The computational problem depends on restricting transformations to efficiently representable classes such as local or quasi-local circuits.Source: Curing the sign problem · p. 197, Stoquastic Hamiltonians · p. 198

9.4 A pragmatic approach: Easing the sign problem

• The framework targets approximately solving or easing the sign problem rather than exactly curing it, using basis rotations and computationally meaningful measures.It is designed without prior knowledge of the system’s physics or dependence on a particular Quantum Monte Carlo procedure.Source: §9.4 · p. 199, Easing the Monte Carlo sign problem · p. 200

Overview

• The thesis develops efficiently computable sign-problem measures, demonstrates easing numerically for translationally invariant models, and studies hardness under orthogonal Clifford and general orthogonal transformations.These chapters provide partial answers and potential starting points rather than full solutions.Source: Overview · p. 200

10.1 Finding the optimal basis for Quantum Monte Carlo

• Directly optimizing the inverse average sign is typically infeasible because estimating it inherits partition-function complexity and may require exponential-size matrix diagonalization.The optimization is also non-convex and cannot generally certify basis quality through stochastic minimization.Source: §10.1 · p. 202

10.2 Gaining intuition: Case studies

• Highly nonstoquastic Hamiltonians can have unit average sign, whereas arbitrarily small nonstoquasticity can yield an arbitrarily small average sign for tuned QMC parameters.The examples show that average-sign behavior depends on the Hamiltonian, discretization, and other Monte Carlo parameters.Source: §10.2 · pp. 203, 204, 206

10.3 Measures of nonstoquasticity

• The ℓ1-norm is selected as the most versatile structure-agnostic measure because it relates to approximate stoquasticity and naturally regularizes toward sparse representations.Its connection to average-sign sampling complexity is meaningful for generic cases but can fail under fine-tuned path combinatorics.Source: §10.2 · p. 203, §10.3 · p. 206
• For local Hamiltonians, the νp nonstoquasticity measures are efficiently computable on bounded-degree graphs, vanish exactly for stoquastic Hamiltonians, and support local basis optimization.For 2-local Hamiltonians on arbitrary graphs, ν1 can be efficiently approximated to any inverse-polynomial error.Source: §10.2 · p. 203, §10.3 · p. 206
• The ℓ1 norm of the nonstoquastic Hamiltonian part is proposed as the most meaningful measure because it reduces positive-entry weights while promoting sparse matrix representations.Sparsity trades fewer contributing paths against smaller individual path weights, and dense Hamiltonians produce broader-tailed, harder sampling distributions at fixed nonstoquasticity.Source: §10.3 · p. 208

Numerical analysis

• Inverse average sign grows roughly exponentially with ν1(H) in random 5-qubit Hamiltonians, supporting ν1 as a measure of sample complexity.For large Monte Carlo step counts, the dependence is reported as exponential and generically monotonic.Source: §10.4 · p. 209, Figure 10.1 · p. 209

10.4 Efficiently computing the nonstoquasticity

• For 2-local Hamiltonians, ν1 is exactly computable in polynomial time on bounded-degree graphs and efficiently approximable to inverse-polynomial additive error on arbitrary graphs.This provides the proposed measure with efficient evaluation despite the general difficulty of computing sign-problem quantities.Source: §10.4 · pp. 209, 211, 212

Can we find the sign-optimal basis?

• The basis-optimization study stress-tests whether minimizing nonstoquasticity can ease sign problems in physically relevant translation-invariant quasi-one-dimensional systems.The systems include frustrated ladder geometries, where geometric frustration produces a sign problem.Source: Can we find the sign-optimal basis? · p. 213

11.1 Sign easing for translation-invariant systems

• On-site orthogonal transformations preserve locality and translation invariance, reducing global ν1 optimization to a constant-size local problem and exponentially improving over direct average-sign optimization.The remaining optimization is nevertheless generally non-convex and high-order over orthogonal matrices.Source: §11.1 · pp. 213–214

11.2 Algorithmic procedure

• The implemented conjugate-gradient method optimizes over O(d), using a Frobenius-norm preoptimization and a smooth approximation to ℓ1 nonstoquasticity to improve numerical behavior.The smooth approximation addresses the discontinuous gradient of the exact ℓ1 objective, and the hybrid procedure compares multiple minimization outcomes.Source: §11.2 · p. 214, §11.3 · p. 215

11.3 Results

• The algorithm essentially recovers stoquastic bases for nearly all tested random Hamiltonians known to admit one, but can become trapped in local minima when recovery fails.This indicates a limitation of first-order optimization for easing the sign problem in general Hamiltonians.Source: §11.3 · p. 215
• For the J0-J1-J2-J3 model, on-site orthogonal basis choices improve nonstoquasticity by factors of 2 to 5, without correlating with the region admitting a non-local stoquastic basis [Nak98].This indicates that sign-problem-free behavior in some quantum Monte Carlo variants need not arise from a stoquastic dimer basis.Source: §11.3 · p. 216
• For frustrated Heisenberg ladders, optimization substantially reduces nonstoquasticity in the fully frustrated case but only slightly improves it in the partially frustrated case.The phase diagram qualitatively agrees with stochastic-series-expansion findings, while the optimized basis remains nonstoquastic throughout the parameter regime.Source: §11.3 · pp. 216–217

11.4 Discussion

• Conjugate-gradient optimization encounters rugged landscapes caused by combinatorial sign assignments, creating obstacles to efficient or universal sign-problem reduction.The algorithm may converge to local minima, and more general ansatz classes such as quasi-local circuits could further reduce nonstoquasticity.Source: §11.3 · pp. 217–218, §11.4 · p. 220

11.3 Results

• The inverse average sign approaches unity across large ladder-parameter regions after basis optimization, although a severe sign problem persists or worsens near J⊥/J∥≳3/4 and J×/J∥≲1/2.The observed improvement is compatible with ⟨sign⟩^-1 ∝ exp(cν1(H)), but nonstoquasticity and average-sign severity have no general simple correspondence.Source: §11.3 · pp. 218–219

12.1 The nonstoquasticity of 2-local Hamiltonians

• SignEasing is NP-complete for 2-local XYZ Hamiltonians under both on-site orthogonal Clifford and general orthogonal transformations.This remains true even where curing the sign problem can be decided efficiently, including strictly 2-local XYZ Hamiltonians [KT19] [Kla+19].Source: §12.1 · pp. 221–222
• The hardness proof reduces MAXCUT ground-state energy to minimizing nonstoquasticity, using ancilla penalties to restrict optimal transformations to encoded on-site choices.The result applies to any finite ℓp-norm of the nonstoquastic part and is hard even on subgraphs of the double-layered square lattice.Source: §12.1 · pp. 222–223
• The NP-completeness result establishes hardness in the simplest setting of easing rather than curing, efficiently evaluable nonstoquasticity, locality-preserving on-site transformations, and 2-local XYZ Hamiltonians.It therefore limits worst-case runtimes for systematic algorithms seeking optimal quantum Monte Carlo bases.Source: §12.1 · pp. 222, 224
• Lemma 12.2 bounds the nonstoquasticity contribution of XZ terms, implying each xi,jXiZj term costs at least |xi,j|/(2 deg(G′)).The analytical bound is needed because sampling cannot be used to evaluate nonstoquasticity in the hardness proof.Source: §12.1 · pp. 225–226

12.2 SignEasing under orthogonal Clifford transformations

• SignEasing is NP-complete for 2-local, including XYZ, Hamiltonians on arbitrary graphs under on-site orthogonal Clifford transformations.The reduction encodes MAXCUT and uses ancilla qubits to ensure Hadamard transformations cannot outperform sign flips corresponding to Ising spin assignments.Source: §12.2 · pp. 226–227

Orthogonal Clifford transformations

• Orthogonal Clifford transformations map each Pauli X or Z to another signed Pauli operator, while X_iX_j terms contribute at least max{a_i,j, 0} and X_iZ_j terms at least |x_i,j|/(4 deg(G)).These transformation and cost properties support the MAXCUT embedding.Source: Orthogonal Clifford transformations · p. 227

Yes-case: (Diagonal) transformations that map X to ±X ( ®w  0).

• Diagonal Clifford transformations correspond one-to-one with AF Ising spin configurations, so the optimal number of nonstoquastic X_iX_j terms equals the original Ising ground-state energy.A stoquastic transformed interaction corresponds to a cut edge, whereas a nonstoquastic interaction corresponds to an uncut edge.Source: Yes-case: (Diagonal) transformations… · p. 228

No-case: (Hadamard) transformations that map X to ±Z ( ®w , 0).

• Hadamard transformations cannot improve the constructed instance: frustrated ancillary triangles retain a lower-bounded cost, and choosing C so that C/(2 deg G′) ≥ 1 makes extra X or W transformations more expensive.Thus, in the no-case, the optimal transformation uses only sign flips, with x⃗,w⃗ = 0.Source: No-case: (Hadamard) transformations… · p. 230

12.3 SignEasing under orthogonal transformations

• SignEasing remains NP-complete for 2-local, including XYZ, Hamiltonians under arbitrary on-site orthogonal transformations.The proof parameterizes rotations and reflections, showing that no allowed angle choice can reduce a nonzero edge’s nonstoquasticity below 1; the construction extends to ν_p for 1 < p < ∞.Source: §12.3 · pp. 230, 232

12.4 Easing the sign problem: Summary and Outlook

• Part III introduces sign easing as a framework that defines a nonstoquasticity measure, optimizes it over local bases in simple settings, and establishes its complexity-theoretic limitations.The framework is presented as both practically feasible in simple cases and useful for guiding future systematic attempts to ease sign problems.Source: §12.4 · p. 233

Outlook

• The outlook extends the framework to other Monte Carlo and quasiprobability settings, while leaving the generalization from real-valued sign problems to complex phase problems open.The discussion is restricted to world-line Monte Carlo and real-valued Hamiltonians and transformations, with applications proposed for stochastic series expansion, determinantal and diffusion Monte Carlo, quantum-circuit simulation, and high-energy physics.Source: Outlook · pp. 233–234
• Trivial phases can have their sign problem removed by efficiently computable quasi-local conjugations, whereas topologically ordered systems may exhibit intrinsic obstructions [Has15] [SGR20] [GSR20].Levin-Wen fixed-point Hamiltonians provide examples of 12-local topologically ordered systems many of which are expected to remain incurable.Source: Outlook · p. 234
• Future work targets minimizing non-stoquasticity in translation-invariant systems and combining SAT solvers with manifold optimization to find tractable relevant instances despite worst-case hardness.The proposed optimization framework applies across dimensions, translation-invariant systems, and ansatz classes.Source: Outlook · p. 234

12.4 Easing the sign problem: Summary and Outlook

• The 2-local stoquastic local Hamiltonian problem is StoqMA-complete, limiting classical simulation even for Hamiltonians amenable to QMC [Bra+08] [BT09] [CM16] [CMP18].This complexity also relates to quantum annealing runtimes and classical complexity-theoretic questions [Hor+17] [AB19].Source: §12.4 · p. 235
• QMC can be intractable because finding a stoquastic basis is hard, because ground-state cooling is hard, or because both difficulties occur; the latter appears as nonconvergent polynomial-time MCMC.This hardness can arise even in classical models such as Ising spin glasses, leaving open whether simulation hardness can ever be attributed solely to basis finding.Source: §12.4 · p. 235

Conclusion 13

• Quantum sampling hardness arises from the quantum sign problem: destructive interference requires signed functions, unlike classical randomized computation, enabling complexity-theoretic separations and potential quantum supremacy.Approximate counting via Stockmeyer provides the key tool for separating classical and quantum sampling complexity.Source: Conclusion 13 · p. 237
• Anticoncentration for 2-design circuit families closes a major loophole in sampling-based quantum supremacy arguments and supports rigorously grounded schemes.The thesis also explains why polynomial interpolation and extrapolation establish exact but not approximate average-case hardness.Source: Conclusion 13 · pp. 237–238
• Quantum sampling schemes can be tailored to physical architectures, including optical lattices, by trading space for constant-time translation-invariant evolution with local rotations and measurements.This design addresses architectures where local control is expensive but many particles evolve coherently.Source: Conclusion 13 · p. 238
• Verification from few samples is impossible without further assumptions, but measurement-device-dependent schemes can certify universal computations and estimate restricted-state fidelity with constant sample complexity.These schemes require reliable, high-accuracy single-qubit operations and show that verification resources must exploit architecture-specific structure.Source: Conclusion 13 · p. 238
• The thesis characterizes the Monte Carlo sign problem as basis-dependent, proposes efficiently computable nonstoquasticity as a generic measure, and proves that optimizing it via SignEasing is NP-hard.The measure can be optimized in practice, but the NP-hardness result establishes fundamental limitations on such easing approaches.Source: Conclusion 13 · p. 238
• The work identifies future foundational questions about making the connection between destructive interference and sign problems rigorous, including links to quasiprobability negativity and phase-space ansatz choices.It also presents the complexity-theoretic and verification results as early landmarks for understanding quantum random sampling after the first quantum-supremacy demonstration by Arute et al..Source: Conclusion 13 · p. 239

Publication context

• The section was previously published as the appendix of Ref. [Han+19], joint work with Martin Kliesch, Jens Eisert, and Christian Gogolin.It provides details and proofs for statements made in Section 4.Source: Proofs for bounding the min-entropy · p. 245

Rényi-entropy equivalence

• The section proves equivalence of the Rényi entropies in (6.24) for α > 1, following an argument analogous to Ref. [Wil+19].The proof uses the relation between p0 and ∥P∥∞.Source: Proofs for bounding the min-entropy · p. 245

Alternative proof of Lemma 6.4

• An alternative proof of Lemma 6.4 is developed based on the proof of Ref. [Gog+13, Theorem 13].The argument applies the union bound and Markov’s inequality before concluding the lemma.Source: Proofs for bounding the min-entropy · p. 245

• It restates a bound due to Aaronson and Arkhipov [AA13] for the probability weight of the collision-free subspace.Source: Probability weight of the… · p. 246
• The bound is formulated as Lemma D.1, attributed to [AA13, Theorem 13.4], for Haar-random unitaries in U(m) with m ≥ n.Source: Probability weight of the… · p. 246

• The section presents a slightly improved proof of the boson-sampling min-entropy bound from [Gog+13, Theorem 12].Source: The min-entropy bound for boson sampling · p. 246
• The proof requires controlling all of Φm,n, whereas the prior measure-closeness lemma controlled only the collision-free subspace Φ∗m,n.Source: The min-entropy bound for boson sampling · p. 246
• The measure-closeness result extends to every S ∈ Φm,n by removing zero entries from S and repeating each remaining row according to its multiplicity.The resulting measure µGS(1/√m) is defined by independently Gaussian real and imaginary matrix entries followed by row repetition.Source: The min-entropy bound for boson sampling · p. 246
• For every S ∈ Φm,n, EU∼µH f(US) ≤ (1 + C) EX∼µGS(1/√m) f(X), whenever the corresponding bound holds for µG(1/√m).This multiplicative comparison applies to measurable f : Cn×n → [0, 1].Source: The min-entropy bound for boson sampling · p. 246

D.1 Sample complexity of device-independently certified quantum samplers

• The embedding and projection isolate one representative from each repeated row, reducing the analysis to the independent rows that determine fS(US).The composition η ◦ π projects onto matrices with the repetition structure of US, while permutation invariance of the Haar measure supports the reduction.Source: §D.1 · p. 247
• Gaussian concentration shows that even the largest matrix entry is unlikely to exceed the scale needed in the min-entropy analysis.The argument accounts for repeated entries in the Gaussian measure, which only increases the chance of avoiding an exceptionally large entry.Source: §D.1 · pp. 247–248
• Counting the boson-sampling sample space bounds its growth when m ≤ c n^ν, enabling the final asymptotic estimate.The resulting bound grows faster than exponentially in n but remains controlled by factors involving c, ν, and n.Source: §D.1 · p. 248
• The proof applies a union bound to control the maximum output probability over the boson-sampling sample space.It combines the indicator-function bound with the permanent representation of output probabilities.Source: §D.1 · pp. 248–249
• Theorem D.2 establishes the desired min-entropy bound when m ≤ c n^ν and ν > 3.The proof first identifies ν > 2 as sufficient for an intermediate bound, then requires ν > 3 to ensure the relevant term decays for large n.Source: §D.1 · p. 250

D.2 Easing the sign problem of translation-invariant Hamiltonians

• The section addresses easing the sign problem in translation-invariant Hamiltonians.Source: Derivation of the… · p. 250

Derivation of the translation-invariant formulation of ν1

• The translation-invariant formulation of ν1 was published as part of Appendix A in Ref. [Han+20].Source: Derivation of the… · p. 250

Derivation of Eq. (11.3)

• A differing basis-string index is designated as the (p+1)st position when summing over p.This choice organizes the sum while ensuring that the selected index differs between the two strings.Source: §D.2 · p. 251
• The sum is divided to avoid double-counting strings differing on at most two nearest neighbours, while larger patches vanish for nearest-neighbour Hamiltonians.The decomposition retains only local differences compatible with nearest-neighbour support.Source: §D.2 · p. 251
• Terms supported left of the pth qubit vanish, and translation invariance accounts for the sum over p through a factor n.The vanishing follows because the basis strings differ at the (p+1)st qubit.Source: §D.2 · p. 251

Gradient of the objective function

• The ansatz consists of on-site orthogonal transformations O ∈ O(d), where d is the dimension of each local constituent.Source: Gradient of the objective function · p. 251
• The transformed local Hamiltonian terms are represented by conjugation h(O) = C(O)hC†(O), with C(O) = O ⊗ O.Source: Gradient of the objective function · p. 252
• The objective-function gradient is formulated for the family of measures ν_p with p ≥ 1 and differentiated with respect to the orthogonal matrix O.Source: Gradient of the objective function · p. 252
• The derivation expands the derivative of the adjoint action and the circuit to obtain matrix forms for evaluating the Hamiltonian and circuit gradients.Source: Gradient of the objective function · pp. 252–253

D.3 Orthogonal transformations of the penalty terms (proof of Theorem 12.4)

• Every allowed continuous orthogonal rotation leaves the non-stoquasticity of an uncured edge and its ancilla qubit at least 1.The proof covers the full orthogonal group, whose continuous freedom is the main additional difficulty compared with the discrete orthogonal Clifford group.Source: §D.3 · p. 253
• The rotation analysis partitions the full angle domain into three sign-and-magnitude sectors and applies different transformed Hamiltonian terms to derive the lower bound.The sectors are defined by the relative signs of θ_i and θ_j and whether |θ_i|+|θ_j| is at most or above π/2; θ_a_i,j remains arbitrary.Source: §D.3 · p. 254, Figure D.1
• In the first sector, the relevant terms satisfy (D.73) + (D.74) ≥ cos(θ_i−θ_j) + C/(2 deg G′) · |sin(θ_i−θ_j)| ≥ 1.This handles angles with sign(θ_i) = sign(θ_j).Source: §D.3 · p. 255
• For the hardest opposite-sign sector with |θ_i|+|θ_j| ≤ π/2, Lemma D.5 reduces minimization to equal magnitudes |θ_i|=|θ_j|=α/2, enabling the same lower bound.The reduction uses monotonicity in the angle sum and shows that the minimum of ϵ(θ_i, θ_j) at fixed α occurs at equal magnitudes.Source: §D.3 · pp. 255–257
• Applying X-flips only changes signs or maps θ_i to −θ_i, so the preceding non-stoquasticity lower bounds remain unchanged.The argument relies on leaving the sign of θ_a_i,j unconstrained and uses the same bounds after the corresponding angle substitution.Source: §D.3 · p. 258

Z Zusammenfassung

• Das Quantenvorzeichenproblem erschwert die Berechnung von Ausgangswahrscheinlichkeiten zufälliger Quantenrechnungen und verhindert deren effiziente Verifizierung.Die komplizierte Struktur der betroffenen Ausgangswahrscheinlichkeiten ist dabei entscheidend.Source: Z Zusammenfassung · p. 262
• Das intrinsische Vorzeichenproblem lässt sich selbst nicht effizient abschätzen.Diese Schwierigkeit bildet eine ironische Schlussfolgerung der Arbeit.Source: Z Zusammenfassung · p. 262
• Die Arbeit basiert auf den Publikationen [Han+17] [Ber+18] [Han+18] [Han+19] [EH+20] [Han+20] und unveröffentlichten Arbeiten.Die Projekte entstanden in enger Zusammenarbeit mit anderen Wissenschaftlern.Source: Z Zusammenfassung · p. 263
• In [Han+17] war D.H. federführend, führte die Beweise und verfasste das Manuskript.Er war maßgeblich für die Gestaltung der Arbeit verantwortlich.Source: Z Zusammenfassung · p. 263
• In [Ber+18] war D.H. an Konzeption, Herleitung der Hauptergebnisse und Manuskriptformulierung beteiligt und führte die numerischen Anticoncentration-Rechnungen durch.Damit umfasste sein Beitrag sowohl zentrale theoretische als auch numerische Arbeiten.Source: Z Zusammenfassung · p. 263
• In [Han+18] und [Han+19] war D.H. federführend und trug wesentlich zu Hauptergebnissen, Beweisen, Grafiken und Manuskriptteilen bei.Für [Han+19] umfasste dies insbesondere die Projektkonzeption und die Ausarbeitung der zentralen Ergebnisse.Source: Z Zusammenfassung · p. 263
• In [EH+20], [Han+20], [Han+] und [BH] leistete D.H. zentrale Beiträge zu Klassifikation, Hauptergebnissen, numerischen Rechnungen, Beweisen und experimentellen Anforderungen.Zu [EH+20] gehörten insbesondere das Klassifikationsschema für Zertifizierungsmethoden und die tabellarische Methodenzusammenfassung; in [Han+] entwickelte er die Beweisidee von Lemma 4.5.Source: Z Zusammenfassung · p. 263

• P, BPP, and BQP contain decision problems solvable in polynomial time classically, probabilistically with bounded error, or quantumly with bounded error, respectively.Source: Complexity classes · p. 293
• NP comprises problems whose YES answers have proofs verifiable in P, while PP accepts when at least half of an NP problem’s paths accept.Source: Complexity classes · p. 293
• #P counts accepting paths of an NP problem, whereas GapP computes the difference between accepting and rejecting paths.Source: Complexity classes · p. 293
• MA and AM are classical interactive-proof classes using one or two rounds, respectively, with a BPP verifier and a powerful prover.Source: Complexity classes · p. 293
• QMA problems have quantum proofs accepted by a BQP verifier for YES instances and rejected for NO instances with bounded failure probability.Source: Complexity classes · p. 293
• StoqMA restricts QMA verification to stoquastic BQP machines using X, CNOT, and TOF gates.Source: Complexity classes · p. 293

Distance measures

• Vector ℓp norms are defined for vectors x = (x_1, ..., x_d) ∈ C^d and 0 < p < ∞.Source: Distance measures · p. 293
• Total-variation distance quantifies the distance between two probability distributions p and q on a sample space Ω.Source: Distance measures · p. 294
• Schatten-p norms are defined for an operator X using its matrix absolute value X†X.Source: Distance measures · p. 294
• The fidelity F(ρ, σ) measures similarity between quantum states ρ and σ; for a pure state, it reduces to the overlap Tr[ρσ] and relates to trace distance.Source: Distance measures · p. 294
• The diamond norm is the stabilized (1 → 1)-norm for a quantum channel E mapping operators on A to operators on B.Source: Distance measures · p. 294

Asymptotics

• Big O denotes an asymptotic upper bound, while Big Ω denotes an asymptotic lower bound for functions f and g.Source: Asymptotics · p. 294
• Big Θ denotes simultaneous asymptotic upper and lower bounds, whereas small o denotes asymptotic domination in the opposite direction.Source: Asymptotics · p. 294
• Small ω denotes asymptotic domination, ∼ denotes scaling equivalence, and tilded Landau symbols suppress logarithmic factors.Source: Asymptotics · pp. 294–295