PaperlayerView exact revision on arXiv

Source-linked AI summary

The Complexity of NISQ

Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry Li

arXiv:2210.07234v1quant-phcs.CCcs.ITcs.LGmath.IT

TL;DR

The computational power of the broad class of NISQ algorithms had not been rigorously characterized. This paper formalizes a classical-computation-plus-noisy-device model and studies its complexity, finding oracle separations and an exponential NISQ–BQP gap for shadow tomography.

  • Problem

    The computational power of all possible NISQ algorithms, relative to classical and fault-tolerant quantum computation, had not been rigorously examined.

    Source: §1 · p. 3

  • Method

    The paper defines NISQ as polynomial-time classical computation with access to a noisy quantum device and analyzes oracle separations and three well-studied problems.

    Source: §1 · pp. 3–4, §2 · p. 4

  • Results

    Modified Simon problems yield oracle separations between BPP, NISQ, and BQP, while shadow tomography requires NISQ at least Ω((1 − λ)^−n) copies versus at most O(n) for BQP.

    Source: §2.2 · pp. 5–6, §2.3 · p. 7

  • Takeaways & Limitations

    The results provide evidence that NISQ can exceed classical computation in some oracle settings yet remain weaker than fault-tolerant quantum computation.

    Source: §2.2 · pp. 5–6

    The model assumes noisy two-qubit gates and noisy initial preparation, with all qubits fixed in number and no fresh qubits introduced during computation.

    Source: §1 · p. 3

Abstract

from arXiv · show

The recent proliferation of NISQ devices has made it imperative to understand their computational power. In this work, we define and study the complexity class $\textsf{NISQ} $, which is intended to encapsulate problems that can be efficiently solved by a classical computer with access to a NISQ device. To model existing devices, we assume the device can (1) noisily initialize all qubits, (2) apply many noisy quantum gates, and (3) perform a noisy measurement on all qubits. We first give evidence that $\textsf{BPP}\subsetneq \textsf{NISQ}\subsetneq \textsf{BQP}$, by demonstrating super-polynomial oracle separations among the three classes, based on modifications of Simon's problem. We then consider the power of $\textsf{NISQ}$ for three well-studied problems. For unstructured search, we prove that $\textsf{NISQ}$ cannot achieve a Grover-like quadratic speedup over $\textsf{BPP}$. For the Bernstein-Vazirani problem, we show that $\textsf{NISQ}$ only needs a number of queries logarithmic in what is required for $\textsf{BPP}$. Finally, for a quantum state learning problem, we prove that $\textsf{NISQ}$ is exponentially weaker than classical computation with access to noiseless constant-depth quantum circuits.

1 Introduction

NISQ devices have stimulated new algorithmic proposals, but the computational power of the full class of such algorithms had not been rigorously characterized. The paper formalizes a hybrid classical–quantum model constrained by noisy preparation, gates, and final measurement.

1 Introduction

  • Existing noisy devices combine noisy state preparation, quantum gates, and final measurement, with classical computation directing repeated runs and processing their bitstrings.The paper frames this hybrid model as representative of current devices and NISQ algorithms.Source: §1 · pp. 3–4
  • The class of all possible NISQ algorithms had not been rigorously studied, leaving their power relative to classical and fault-tolerant quantum computation open.The paper identifies both comparisons as fundamental questions.Source: §1 · p. 3
  • The model assumes noisy two-qubit gates with local depolarizing noise, while noting that results extend to more general noise models.All qubits are prepared at the start, and noisy measurement occurs only at the end on all qubits simultaneously.Source: §1 · pp. 3–4
  • The stated device constraints preclude known general fault-tolerant schemes, and accumulating entropy prevents arbitrarily long useful computation under those constraints.The passage says removing any one constraint would allow some form of nontrivial fault tolerance.Source: §1 · p. 4
  • The formal model gives a classical computer access to a noisy device that prepares a noisy poly(n)-qubit zero state, executes noisy gates, and measures all qubits.The model is intended to capture capabilities of most existing quantum devices.Source: §1 · pp. 3–4

2 Main Results

The paper formalizes NISQ as polynomial-time classical computation augmented by a noisy quantum device, then studies oracle separations and three established problems. Its results range from oracle evidence placing NISQ between BPP and BQP to sharply different NISQ performance across search, Bernstein–Vazirani, and shadow tomography.

2.1 Definition of NISQ

  • The informal NISQ class consists of polynomial-time probabilistic classical algorithms with access to a noisy device for noisy preparation, gates, and simultaneous final measurement.The definition assumes constant per-qubit depolarizing noise and rules out known fault-tolerant schemes.Source: §2.1 · p. 5

2.2 Super-polynomial separations

  • Together, the oracle results give evidence that NISQ lies strictly between BPP and BQP relative to suitable oracles.The passage describes this as evidence about computational power, not an unrelativized strict separation.Source: §2.2 · pp. 5–6
  • Two modified Simon problems give oracle separations: BPP^O1 ⊊ NISQ^O1 and NISQ^O2 ⊊ BQP^O2.The first modification is robust to noise; the second is highly non-robust and gives NISQ exponentially less information than noiseless bounded-depth quantum computation.Source: §2.2 · pp. 5–6

2.3 NISQ in three well-studied problems

  • NISQ requires at least eΩ(N) queries for unstructured search, ruling out a Grover-like quadratic speedup for any NISQ algorithm.The lower bound applies to algorithms with access to poly(N) qubits; eΩ(·) neglects logarithmic factors.Source: §2.3 · p. 6
  • NISQ solves Bernstein–Vazirani on n bits in at most O(log n) queries, and a simple modification of the original algorithm is sufficiently noise-robust.The passage contrasts this with the classical lower bound of Ω(n) queries.Source: §2.3 · pp. 6–7
  • For shadow tomography, NISQ requires at least Ω((1 − λ)^−n) copies to learn absolute Pauli expectations, while BQP needs at most O(n) copies.The NISQ bound is for constant error and all n-qubit Pauli observables; for small λ, its exponential base is close to one.Source: §2.3 · p. 7

3 Related Work

Related work studies noisy oracles, noiseless hybrid models, the resilience of particular algorithms, and the complexity of noisy circuits. This paper distinguishes its focus on local noise within quantum computation and on the general power of classical computation augmented by noisy circuits.

3 Related Work

  • Prior faulty-oracle studies place noise in the oracle while leaving the computation noiseless; this work instead studies local qubit-wise noise in the computation.Some cited lower bounds also assume global rather than local oracle noise.Source: §3 · p. 7
  • Noiseless hybrid-model work studies search and oracle separations, whereas this paper examines hybrid computation with noisy quantum devices.The paper also relates its second Simon-based oracle to a simplified recursive Simon problem.Source: §3 · pp. 7–8
  • Earlier noise-resilience studies focus on specific algorithms such as Grover search, QAOA, and VQE; this work studies NISQ capabilities without requiring a particular algorithm.The cited work also includes results on noisy random-circuit output probabilities and classical simulation.Source: §3 · p. 8
  • Prior work bounds noisy circuits themselves by QNC1 under one model, while this paper studies classical computation augmented by noisy circuits.The cited result says polynomial-size noisy circuits are no stronger than logarithmic-depth noiseless circuits, while quasipolynomial-size circuits can compute any QNC1 function.Source: §3 · p. 8

4 Outlook

The outlook frames NISQ as a mathematical framework for evaluating noisy quantum advantage and proposes extending that framework to future devices. The appendices supply formal definitions for noisy circuits, oracle access, and bounded-depth hybrid computation.

4 Outlook

  • The authors propose studying future devices by defining complexity classes that capture their salient features, potentially yielding classes intermediate between NISQ and BQP.They identify standard-assumption separations, geometric locality, and additional natural algorithms as open directions.Source: §4 · pp. 8–9

A.1 Definition of the complexity class

  • The appendix formalizes NISQ algorithms as probabilistic classical machines querying noisy quantum circuit oracles, with polynomial-time decision and bounded error.A noisy circuit applies local depolarizing noise after quantum operations, and its oracle returns a random bitstring.Source: §A.1 · p. 16

A.2 Algorithms with oracle access

  • The oracle-access definitions allow classical algorithms to query a classical function and specify quantum circuits that may apply its unitary oracle.The appendix defines corresponding quantum and NISQ algorithms with access to the classical oracle.Source: §A.2 · p. 17

A.3 Algorithms of bounded depth

  • The appendix defines noiseless bounded-depth hybrid algorithms and the classes BPPQNC[f(n)] and BPPQNC for comparing bounded-depth quantum assistance.It notes BPPQNC is contained in BQP.Source: §A.3 · p. 18

B.1 Learning tree formalism and Le Cam’s method

The learning-tree formalism represents a NISQ algorithm’s classical and noisy-circuit queries as a tree of transcripts, enabling lower bounds through distributional comparisons. The section also gives a hybrid bound on how channel differences affect circuit outputs.

B.1 Learning tree formalism and Le Cam’s method

  • A learning tree records the transcript at each node and allows either a classical oracle query or a noisy-circuit query at each non-leaf node.The algorithm’s classical post-processing maps a leaf transcript to an oracle decision or prediction.Source: §B.1 · p. 18
  • Each node carries its transcript probability, noisy-circuit outcomes branch according to output probabilities, and query complexity bounds queries along every root-to-leaf path.Classical queries preserve the path probability; a noisy-circuit query branches over possible measured strings.Source: §B.1 · p. 18
  • Figure 2 illustrates how classical and noisy-circuit queries can be mixed across the algorithm’s memory states and represented in one tree.At each memory state, the algorithm may choose either query type.Source: Figure 2 · p. 19
  • Replacing each circuit query’s child distribution by one within ε in total variation changes the leaf distribution by at most εN for an N-query tree.The proof replaces circuits one layer at a time and bounds each layer’s change by ε.Source: §B.1 · p. 19
  • For lower bounds, the authors reduce to distinguishing two oracle families and use Le Cam’s method to relate their mixture distributions over tree leaves to distinguishing advantage.If the mixture distributions are less than 1/3 apart in total variation, no leaf-transcript algorithm distinguishes the families with advantage 1/3.Source: §B.1 · pp. 19–20

B.2 Basic hybrid argument

  • If two channels differ by at most ε in trace norm on every pure input state, a depth-T circuit’s output distributions differ by at most εT in total variation.The section presents this as a hybrid argument for quantum query lower bounds.Source: §B.2 · p. 20

C.1 NISQ vs. BPP

This section establishes a superpolynomial oracle separation between BPP and NISQ using a noise-robust version of Simon’s problem and a recursively concatenated code. It explains how NISQ can simulate fault-tolerant Simon computation without mid-circuit qubit initialization, including a noisy, shallow simulation of Simon’s final step and preservation of sparse deviations by the robustified oracle.

C.1.1 Recursively-defined concatenated code

  • The construction recursively concatenates a CSS code encoding one logical qubit, with disjoint error neighborhoods for the two codeword classes at each recursion level.The base CSS code uses a punctured doubly-even self-dual code and its dual; the code parameters and correctable error count are constant.Source: §C.1.1 · pp. 21–22

C.1.2 Robustified Simon’s problem

  • The robustified Simon oracle makes its output bitstring stable across a large number of inputs.It is constructed from the original Simon function by mapping inputs in error neighborhoods around recursively encoded codewords to the corresponding function output.Source: §C.1.2 · p. 23
  • With sufficiently small noise, NISQ solves the robustified Simon problem in polynomial time, while classical algorithms require superpolynomial time; thus BPP is strictly contained in NISQ relative to the constructed oracle.The separation holds with constant advantage for distinguishing whether the underlying Simon function is 2-to-1 or 1-to-1.Source: §C.1 · p. 21, §C.1.2 · p. 23

C.1.3 Simulating fault-tolerant Simon’s in NISQ with exponential overhead

  • The construction combines error-correction tools with [87]’s noisy majority vote to distill middle-circuit noisy zero states from initially prepared ones, enabling encoded Simon computation with poly(n) qubits and similar gates at λ < λ0, for small constant λ0.Source: §C.1.2 · pp. 23–24
  • A λ-noisy circuit with polylog(n′) layers and poly(n) qubits reproduces Simon’s final-step distribution D with probability at least 1−O(1/n′), using recursive-majority postprocessing.The construction replaces arbitrary-time ancilla initialization with circuits initialized at time zero while keeping the same depth.Source: §C.1.3 · pp. 26–27

C.1.4 Stability against deviation in the robustified Simon’s oracle

  • The robustified classical Simon oracle preserves the deviation metric, unlike the ordinary Simon function, so deviations remain sparse when the robustified oracle is applied.This stability supplies the condition needed to combine the encoded noisy preparation with simulation of Simon’s final step.Source: §C.1.4 · pp. 27, 29

C.1.5 Proof of super-polynomial separation between NISQ and BPP

The proof prepares approximate encoded states, applies the robustified Simon oracle, and measures to obtain samples that distinguish the 1-to-1 and 2-to-1 cases. Repeated sampling and solving linear equations recover the distinction with constant probability, and repetition raises the success probability.

C.1.5 Proof of super-polynomial separation between NISQ and BPP

  • Approximate states on Hmain,1 and Hanc,1 are prepared using Hanc,2, then the oracle acts on the relevant registers while Hmain,2 is ignored.After applying the oracle, the Hanc,1 register is traced out.Source: §C.1.5 · p. 30
  • With probability 1 − O(1/n′), measurement and recursive majority produce a sample uniform over all strings for a 1-to-1 function, or over strings satisfying z0 · s = 0 (mod 2) for a 2-to-1 function.The procedure applies Hadamards to encoded qubits before measuring.Source: §C.1.5 · p. 30
  • Repeating the procedure n′ times yields n′ useful samples with probability (1 − O(1/n′))^n′ = Ω(1).On this event, the samples provide the linear equations used in the distinction.Source: §C.1.5 · p. 30
  • Solving z_i · s = 0 (mod 2) determines whether s is zero, indicating a 1-to-1 function, or nontrivial, indicating a 2-to-1 function.If the useful-sample event does not occur, classical oracle queries at f_s(0) and f_s(s) can check the situation; repeating the procedure O(log(1/δ)) times gives success probability at least 1 − δ.Source: §C.1.5 · p. 30
  • The separation argument also holds when each qubit is independently corrupted by an adversary with probability λ at every layer.The paper states that this stronger-noise version follows from the proof verbatim.Source: §C.1.5 · p. 31

C.2 NISQ vs. BQP

This section establishes an oracle separation between NISQ and BQP using a lifted Simon problem, and shows that NISQ algorithms cannot achieve a quadratic speedup for unstructured search. The search lower bound uses bounded-depth quantum arguments and concentration analyses, including i-concentrated paths whose goodness and balancedness help ensure that expected L_i(z) is not too small.

C.2 NISQ vs. BQP

  • NISQλ algorithms need at least exp(Ω(λn)) queries to distinguish 1-to-1 from 2-to-1 functions on lifted Simon oracles with constant advantage, yielding NISQ^O ⊊ BQP^O.The argument also extends beyond Simon’s problem: for search problems over families of Boolean functions, NISQ query complexity is essentially the classical query complexity.Source: §C.2 · pp. 31, 33

D Unstructured Search

  • eΩ(dλ) queries are required for a NISQλ algorithm to identify the marked item among d possibilities with probability 2/3.The proof first establishes a lower bound for noiseless bounded-depth quantum computation, then uses it to obtain the NISQ bound.Source: D Unstructured Search · p. 34

D.1 Proof preliminaries

  • Bounded-depth algorithms are represented by learning trees whose nodes track query transcripts, whose edges correspond to circuit measurement outcomes, and whose leaves are classified by a classical decoder.The framework omits classical oracle queries because noiseless quantum query access can simulate them.Source: §D.1 · p. 34

D.2 Lower bound against bounded-depth computation

  • A noiseless depth-T quantum algorithm with at most cd/T queries cannot identify the marked item among d possibilities with probability 2/3, for an absolute constant c > 0.Source: §D.2 · p. 35

D.2.1 Likelihood ratio calculations

  • The bounded-depth lower bound compares path likelihood ratios under a marked-item oracle and the identity oracle, using a multiplicative sub-martingale argument.Source: §D.2.1 · p. 35

D.2.2 Good and balanced paths

  • Good paths limit large multiplicative decreases, while balanced paths control variance; at least 99% of paths are balanced for at least 99% of marked items.Source: §D.2.2 · pp. 37–38

D.2.3 Martingale concentration

  • For paths that are both i-good and i-balanced, bounded differences and variance yield Bernstein-type concentration of the log-likelihood ratio.Source: §D.2.3 · p. 38
  • For 0 < ε < 1/2, Z_t ≥ log(1 − ε) ≥ −2ε, and Freedman's inequality with Eqs. (16) and (17) establishes the lemma.The passage says {Z_t}_t is a submartingale difference sequence.Source: §D.2.3 · p. 39
  • i-concentrated paths have a Lemma D.12 sum that is not too negative and, alongside goodness and balancedness, help ensure E_i∼[d][L_i(z)] is not too small.Source: §D.2.3 · p. 39
  • I_conc(z) and I_anticonc(z) denote the indices i for which a path z is, respectively, i-concentrated or not i-concentrated.Source: §D.2.3 · p. 39

D.2.4 Completing the argument

The argument turns bounds on distinguishing the search oracles into a NISQ query lower bound, then applies the framework to Bernstein–Vazirani. For Bernstein–Vazirani, NISQ needs only logarithmically many queries and remains robust to sufficiently low-rate arbitrary local noise.

D.2.4 Completing the argument

  • The proof's oracle lower bound uses that, with probability at least 0.97, at least 0.97(N/G) indices satisfy the good, balanced, and concentrated conditions.For a uniformly random index, the associated likelihood is at least 9/10 with probability at least 0.972, supporting the total-variation bound.Source: §D.2.4 · p. 40

D.3 From bounded-depth to noisy computation

  • Choosing T = Cλ^-1(log log d + log N) makes the noisy and bounded-depth noiseless algorithms' leaf distributions arbitrarily close.The total variation distance is at most N(1 − λ)T/2 · O(√log d).Source: §D.3 · p. 41

D.2.4 Completing the argument

  • With query complexity at most cd/T, a NISQ algorithm cannot solve unstructured search with probability 2/3, yielding an eΩ(dλ) lower bound.The proof first shows that such an algorithm cannot distinguish O0 from Oi for a random i with constant advantage.Source: §D.2.4 · p. 40, §D.3 · p. 41

E Bernstein-Vazirani Problem

  • For 0 ≤ λ < 1/24, NISQ solves Bernstein–Vazirani with probability at least 1 − δ using O((1/(1 − 24λ)) log(n/δ)) queries.The section also states robustness to arbitrary local noise occurring at a sufficiently small constant rate.Source: E Bernstein-Vazirani Problem · p. 41

E.1 Proof preliminaries

The preliminaries review the Bernstein–Vazirani algorithm and introduce permutation notation for transforming the hidden-string function. Figure 3 labels the circuit's noise layers for use in the proof.

E.1 Proof preliminaries

  • Figure 3 marks local-noise layers where, with probability λ, an arbitrary adversarial single-qubit operation is applied.The layer labels are used for reference in the proof.Source: Figure 3 · p. 42
  • A permutation π acts on bit strings by rearranging their coordinates, and the transformed function is defined as fπ = f ◦ π.The operator definition also extends the permutation action to n-qubit states.Source: §E.1 · p. 42
  • The original algorithm prepares |+⟩⊗n ⊗ |−⟩, applies the oracle, traces out the |−⟩ qubit, and applies Hadamards to the first n qubits.The section states that this yields the hidden string.Source: §E.1 · p. 42

E.2 Proof of Theorem E.1

The proof analyzes how noise affects Bernstein–Vazirani decoding, while the following shadow-tomography sections establish an exponential copy lower bound for NISQλ and define the state oracle used to study it.

E.2 Proof of Theorem E.1

  • For λ ≤ 1/10, each Bernstein–Vazirani output bit is correct with probability greater than 1/2, so majority voting can recover the hidden string; for depolarizing noise bounded away from λ = 1, O(log(n/δ)) queries suffice.The analysis attributes corrupted output bits to qubits corrupted in the noise layers and does not optimize the threshold for general local noise channels.Source: §E.2 · p. 44

F Shadow Tomography

  • For shadow tomography, NISQλ requires 1/(1 − λ)^Ω(n) copies to estimate all Pauli observables to constant error, whereas BPPQNC0 requires O(n) copies.The comparison is for predicting |tr(Qρ)| across all n-qubit Pauli operators.Source: F Shadow Tomography · p. 45

F.1 A quantum oracle preparing an unknown state

  • The state oracle replaces the state register with a fresh copy of ρ, and the lower-bound analysis allows arbitrary noiseless computation between queries with depolarizing noise after each oracle call.This is a stronger model than a λ-noisy quantum algorithm or a NISQλ algorithm.Source: §F.1 · p. 45

F.2 Exponential lower bound

The section proves an exponential NISQλ query lower bound for identifying a Pauli-perturbed state, despite an O(n)-query classical constant-depth quantum-assisted approach. It relates this bound to the Pauli weight and to noise after oracle calls.

F.2 Exponential lower bound

  • NISQλ needs Ω((1 − λ)^−n) oracle queries to determine either s or P with constant advantage, while BPPQNC0 can determine both with O(n) queries.For arbitrary ρ, BPPQNC0 can also estimate |tr(Pρ)| for all n-qubit Pauli operators to small constant error with high probability.Source: §F.2 · p. 45
  • For a Pauli operator P, distinguishing the oracle for ρ = 1/2^n(I + P) from the maximally mixed-state oracle requires Ω((1 − λ)^−|P|) queries.Here |P| is the number of non-identity components of P.Source: §F.2 · p. 46
  • The lower bound holds even when computation between oracle calls is noiseless, because depolarizing noise makes the two oracle outcomes difficult to distinguish without exponentially many queries for full-weight P.The proof compares the noisy output states for the relevant oracle choices.Source: §F.2 · p. 46

G Separating NISQ and BPPQNC from BQP

The section uses shuffling Simon’s problem to separate NISQλ from BQP, while retaining a separation between BPPQNC and BQP. Its lower bound relies on noise suppressing the algorithm’s dependence on the underlying function.

G Separating NISQ and BPPQNC from BQP

  • Shuffling constructs the oracle using intermediate one-to-one functions and a final function acting on a random subset of the enlarged domain.The construction defines the active set from the images of the lexicographically first 2^n strings under the intermediate functions.Source: G Separating NISQ and BPPQNC from BQP · pp. 46–47
  • For d = log^ω(1)(n), d-SSP separates BQP from BPPQNC under the shuffling oracle [76].The section notes that the simpler oracle construction cannot give this separation because Simon’s algorithm can be implemented in BPPQNC0.Source: G Separating NISQ and BPPQNC from BQP · pp. 46–47
  • Solving d-SSP with constant advantage requires NISQλ algorithms to make exp(Ω(n · min(1/2, λd))) oracle queries.The section presents this as its main NISQλ lower bound for the shuffling Simon problem.Source: G Separating NISQ and BPPQNC from BQP · p. 47
  • For strings separated by at least qn in Hamming distance, independently flipping each bit with probability λ/2 makes the probability of landing in that set at most exp(−Ω(λn)).The stated range is 3/10 ≤ q < 1/2.Source: G Separating NISQ and BPPQNC from BQP · p. 48
  • After local noise, the output distributions of a noisy circuit using the shuffling oracle for any two functions f and f′ differ by at most exp(−Ω(λdn)) in total variation distance.This bound supports the reduction used in the proof of the query lower bound.Source: G Separating NISQ and BPPQNC from BQP · pp. 49–50

H Deferred Proofs

The deferred proofs establish a mutual-information contraction under depolarizing noise and relate a projected state’s trace to a probability over noisy bit strings.

H.1 Proof of Lemma D.15

  • Depolarizing noise contracts the mutual information by a factor of at most 1 − λ.The proof uses a representation of the noise as averaging over restrictions to randomly selected subsystems.Source: §H.1 · p. 51

H.2 Proof of Lemma C.21

  • The trace of the projected state equals the probability that the noisy sampled string lands in the subset Ω.The proof identifies the trace with Pr[ã ∈ Ω].Source: §H.2 · p. 51

I Simon’s Problem and Noisy Parity

The section sketches how noisy Simon samples can be treated as noisy-parity instances and gives a conditional route to separating NISQ from BPP on a restricted Simon oracle.

I Simon’s Problem and Noisy Parity

  • Noisy parity asks for recovery of an unknown string from uniformly sampled inputs whose parity labels are independently flipped with probability η.With the unknown string restricted to the first O(log n · log log n) bits, the cited algorithm has runtime and sample complexity poly(n) · (1−2η)⁻√log n.Source: I Simon’s Problem and Noisy Parity · p. 52
  • The restricted Simon period is supported on the first O(log n · log log n) bits and has Hamming weight at most log n, making the classical problem super-polynomial in n.Source: I Simon’s Problem and Noisy Parity · p. 52
  • Repeated noisy Simon circuits yield noisy-parity samples with 1−2η ≥ 1/poly(n), enabling efficient solution if the stronger noisy-parity runtime bound holds.The sampled string satisfies the parity condition whenever no qubit corresponding to a nonzero period bit is decohered.Source: I Simon’s Problem and Noisy Parity · p. 52
  • If noisy parity admits runtime poly(n, (1−2η)⁻¹) under the stated support promise, then BPP^O ⊊ NISQ^O for the restricted Simon oracle.The Simon period must be supported on the first O(log n · log log n) bits and have Hamming weight at most log n.Source: I Simon’s Problem and Noisy Parity · p. 52
Loading 2210.07234v1…