PaperlayerView exact revision on arXiv

Source-linked AI summary

Accelerated search for global extrema in structured quantum signals

Sachin S. Bharadwaj, Katepalli R. Sreenivasan

arXiv:2610.04024v1quant-phcs.CEphysics.app-phphysics.comp-ph

TL;DR

An efficient quantum subroutine alone does not establish useful scientific quantum advantage; state generation, observable extraction, and classical verification must also be addressed. This work applies a bounded nonlinear transformation to unknown amplitudes, and under sufficient extreme-tail probability compresses global-extremum search to O(log N) candidates while retaining the true best candidate.

  • Problem

    A useful scientific quantum advantage requires more than an asymptotically efficient subroutine: state generation, observable extraction without reconstructing the full solution, and efficient classical verification must also be addressed.

    Source: B. End-to-end and verifiable quantum… · p. 11

  • Method

    A Chebyshev-walk primitive applies a bounded nonlinear function to unknown amplitudes using the state-preparation circuit and its coherent inverse, without first estimating individual amplitudes.

    Source: §V · p. 10

  • Results

    With sufficient normalized probability in the extreme-event tail, the global stage compresses the search to O(log N) candidates, and global completeness ensures the true best candidate is not discarded.

    Source: §II · p. 4, §V · p. 10

  • Takeaways & Limitations

    The results suggest that physical dynamics concentrating relevant information into a small but sufficiently probable portion of a quantum state can make physical structure a computational resource.

    Source: §VI · p. 13

Abstract

from arXiv · show

Extreme values of a physical system are rare by definition, yet they can govern some of its most consequential and anomalous behavior. Their sparsity makes them particularly costly to identify in large data sets. Quantum computation offers a potential way to reduce this cost. The challenge is that quantum amplitudes cannot simply be read, copied, compared, or marked using conventional search oracles. Here we introduce an algorithm for searching amplitude-encoded quantum signals that exploits their underlying structure. Through a nonlinear amplitude transformation, the algorithm identifies and certifies a global extremum while exponentially reducing the effective search space for structured signals. We establish a polylogarithmic query complexity in the data size $N$, together with global completeness, efficient classical verification, and a measurable criterion for quantifying exploitable structure. We demonstrate the framework using computational turbulence data. Applied to line cuts of velocity gradients from a $1024^3$ simulation containing more than one billion grid points, the algorithm consistently isolates the extreme tail and reduces the median search space to $O(\log N)$. The clustered structure characteristic of turbulence further accelerates the search. These results establish a direct connection between physical structure and quantum advantage in extreme-value search. For accessibility, the main text emphasizes the central ideas and results, while the theoretical derivations are provided in the Appendices.

I. PROBLEM STATEMENT

The section frames extrema search over real-valued data encoded as normalized quantum amplitudes and sets out a structure-conditioned route to globally certified, polylogarithmic search.

I. PROBLEM STATEMENT

  • The structure factor S_in measures the extremal amplitude's separation from the typical signal scale and frames the retained-mass conditions for efficient certified search.The objectives include deriving the retained-mass requirement in terms of S_in and comparing query complexity with classical scanning and GDH.Source: §I · pp. 2–3
  • The canonical task is to find the largest-magnitude entry; signed maximum, signed minimum, and smallest-magnitude tasks reduce to it under preparation conditions.Smallest-magnitude search additionally requires efficient subtraction of a background with the same tail properties; sign is determined by interference rather than a sign oracle.Source: §I · pp. 2–3
  • The primary objective is a polylogarithmic-in-N search returning an extremal address, value, and sign certified globally, with failure probability δ.The returned address must satisfy the stated extremum condition.Source: §I · p. 3
  • The practical objective is to test these requirements on intermittent velocity-gradient signals from homogeneous isotropic turbulence, including state-preparation, extraction, verification, finite-resource, and Reynolds-number costs.The stated objectives include efficient preparation for the nonlinear PDE, extrema extraction, and classical verification.Source: §I · p. 3

II. MAIN RESULTS

The main results give a certified extrema search for amplitude-encoded signals: a bounded Chebyshev filter compresses candidates, while candidate count and retained probability mass govern efficiency. The paper also establishes global completeness and classical verification.

II. MAIN RESULTS

  • A bounded Chebyshev-walk transformation applies a nonlinear function directly to unknown amplitudes, suppressing the background while retaining extreme-event candidates.The filter exposes candidates without resolving the ordering of nearby amplitudes; high-precision comparison follows compression.Source: §II · p. 3
  • Efficient search requires both a small candidate set and sufficient probability mass in the safely retained tail.The filter transition width Γ is a design parameter, and the interval between λ and λ + Γ remains unresolved.Source: §II · p. 3
  • Polylogarithmic query complexity in N holds under the stated structure and accuracy conditions, versus O(N) GDH and classical database-size dependencies.The theorem requires controlled filter leakage relative to the safely retained mass.Source: §II · pp. 3–4
  • When filter leakage is O(PR), Mglob = O[K log(1/δglob)] successful measurements recover a true global-extremum address with controlled failure probability.Candidate compression preserves global completeness rather than merely finding the largest event among sampled candidates.Source: §II · p. 4
  • Classical verification is available under trusted execution through the filtered-state certificate, or for an untrusted device through the protocol of ref..The untrusted-device verifier is polylogarithmic in N when the verified circuit size and security parameter are polylogarithmic in N.Source: §II · p. 4
  • Under the stated assumptions, the fluid-dynamics state-preparation query cost QS is polylogarithmic in N.The preparation module uses the quantum homotopy solver and, when required, a derived-field operation.Source: §II · pp. 4–5

III. HOW THE ALGORITHM WORKS

The algorithm first isolates a short tail of extreme-event candidates, then compares those candidates at high precision. Optional refinements can enhance local contrast or localize a dominant candidate before certification.

III. HOW THE ALGORITHM WORKS

  • Coarse statistics set a threshold and transition width before QG1 filters the amplitude-encoded signal.The filtered-state measurements return candidate addresses, reducing the original N-point problem to O(log N) relevant addresses.Source: §III · p. 5
  • QG2 optionally enhances peaks or troughs relative to their neighborhoods before filtering, or localizes a dominant candidate afterward through the binary address tree.High-precision comparison is reserved for recovered candidates, and global-completeness and verification tests check that no better candidate was missed.Source: §III · p. 5

A. Quantum Gadget 1: Chebyshev-walk amplitude filtering

QG1 applies a bounded polynomial directly to the signal amplitudes, suppressing background while retaining the extreme-event tail. A Chebyshev walk makes the amplitudes available for this transformation without measuring them individually.

A. Quantum Gadget 1: Chebyshev-walk amplitude filtering

  • QG1 transforms the input amplitude state to suppress the broad background and retain extreme amplitudes without measuring or estimating individual values.The polynomial is chosen to be near zero below the candidate threshold and near one in the safely retained tail.Source: A. Quantum Gadget 1: Chebyshev-walk… · pp. 5–6
  • The amplitude observable makes each unknown amplitude u_i an eigenvalue associated with |i⟩, without a numerical value register or amplitude measurement.The construction uses a computational-basis copy followed by U†.Source: A. Quantum Gadget 1: Chebyshev-walk… · p. 6
  • The Chebyshev walk maps repeated rotations in each index subspace to T_l(u_i), exposing a Chebyshev basis without learning individual amplitudes.Writing u_i = cos θ_i, ℓ walk applications produce cos(ℓθ_i) = T_ℓ(u_i).Source: A. Quantum Gadget 1: Chebyshev-walk… · p. 6
  • QG1 coherently combines polynomial terms using a history register and coefficient weights, leaving the filtered state after auxiliary-register postselection.Amplitudes below threshold are suppressed while those safely beyond the transition region retain approximately their original weight; the filter does not rank survivors.Source: A. Quantum Gadget 1: Chebyshev-walk… · p. 6
  • Amplitude amplification prepares the successful filtered branch at a cost controlled by retained probability mass rather than a prescribed logarithmic form.The retained-mass guarantee bounds the branch probability through P_e ≥ (1 − η_filt)^2 P_R.Source: A. Quantum Gadget 1: Chebyshev-walk… · p. 6
  • For turbulence, Γ = (log2 N)^−3/2 gives polynomial degree d = O[(log2 N)^3/2 log(1/η_filt)], set by transition width rather than top-two spacing.The fine spacing matters only after QG1 has compressed the signal to the candidate set.Source: A. Quantum Gadget 1: Chebyshev-walk… · p. 6

B. Quantum Gadget 2: optional contrast and localization

QG2 offers optional refinements around QG1: local contrast before filtering and binary-tree localization after filtering. These operations have distinct scopes, and QG1 remains the rigorous fallback.

B. Quantum Gadget 2: optional contrast and localization

  • QG2a enhances events large relative to their local surroundings before filtering, while QG2b localizes a dominant candidate after filtering.Neither refinement is required for Theorem 1.Source: B. Quantum Gadget 2: optional contrast… · p. 6
  • Local contrast subtracts a neighborhood average, leaving an isolated peak or trough prominent when the signal varies slowly nearby.The neighborhood width m controls the spatial scale of the contrast.Source: B. Quantum Gadget 2: optional contrast… · p. 7
  • Local contrast need not preserve the original amplitude ordering, so it is suited to neighborhood-relative extrema rather than the canonical global-extremum problem.The canonical problem uses A_0 := I.Source: B. Quantum Gadget 2: optional contrast… · p. 7
  • QG2b uses binary blocks to compare filtered probability and records favored orientations to localize a candidate address.It relies on a hierarchy condition; measurements of a candidate address can be reused at each binary level, and undoing recorded sorting recovers the original index.Source: B. Quantum Gadget 2: optional contrast… · pp. 7–8
  • QG2b is an optional localization procedure, not an independent asymptotic speedup; without the hierarchy condition, explicit candidate enumeration remains the rigorous fallback.A prescribed width set for QG2a can include m = 0 during calibration.Source: B. Quantum Gadget 2: optional contrast… · pp. 7–8

IV. NUMERICAL VALIDATION ON TURBULENT VELOCITY GRADIENTS

Across 576 turbulent-gradient signals, filtering reduced the median candidate set to five and increased the true maximum’s sampling probability nearly eightfold. The validation uses 1024-point line cuts from a 1024^3 simulation and compares finite-resource costs under matched value-estimation models.

IV. NUMERICAL VALIDATION ON TURBULENT VELOCITY GRADIENTS

  • QG2b recursively compares probability in binary prefix blocks, follows a favored child when evidence suffices, and retains both branches when it does not.Under Proposition 3’s path-bias condition, it recovers the full log2 N-bit address with logarithmic confidence overhead.Source: Figure 3 · p. 8
  • When gradients are supplied classically, brute-force state preparation can require O(N) operations and does not yield an end-to-end quantum advantage when counted.The stated quantum advantage applies when the input state is generated quantumly; this validation is an independent test of the search algorithm.Source: §IV · p. 8
  • QG1 suppresses the broad signal background while retaining amplitudes beyond a finite transition region, and QG2a subtracts a slowly varying local background in a synthetic illustration.The QG2a example compares each value with the average of neighboring values, using m = 10.Source: Figure 4 · p. 9, §IV · p. 9
  • The 576 signals were 1024-point periodic line cuts extracted from a 1024^3 direct numerical simulation of homogeneous isotropic turbulence.The cuts came from nine velocity-gradient tensor components at 64 equally spaced locations.Source: §IV · p. 9
  • 576 signals yielded a median of five QG1 candidates and a 7.8677-fold increase in the probability of observing the true maximum.The leading-candidate mass exceeded the inverse-logarithmic target; QG1 concentrated 0.89282 of filtered probability on those candidates.Source: §IV · p. 9, Table I · p. 10
  • The matched QAE-based comparison reports median estimated costs of 2063.6 for the method and 2693.2 for GDH, with a median signal-wise ratio of 1.5201.The comparison excludes the repeated-state factor and is not against GDH with a cost-free comparison oracle.Source: §IV · pp. 9–10

V. DISCUSSION OF RESULTS

The discussion separates coarse candidate isolation from exact value and sign determination: a bounded nonlinear amplitude transformation compresses the search before precise comparisons. Global completeness preserves the extremum, while optional refinements complement a rigorous QG1 fallback.

V. DISCUSSION OF RESULTS

  • The global stage resolves only the designed transition width and compresses the search to O(log N) candidates before fine value and sign information are obtained.Global completeness guarantees that this compression has not discarded the best candidate.Source: §V · p. 10
  • The Chebyshev-walk primitive applies a bounded nonlinear function directly to unknown amplitudes using state preparation and its coherent inverse.The paper uses this primitive for extrema filtering, while identifying it as a general nonlinear-processing primitive for amplitude-encoded data.Source: §V · p. 10
  • QG2 offers optional local-background subtraction and hierarchical localization, while QG1 and explicit enumeration remain rigorous fallbacks.The construction covers largest magnitude, largest positive, and most negative extrema; smallest magnitude additionally requires preparation of a background-subtracted magnitude state.Source: §V · p. 10

A. Structure as a quantum computational resource √

The algorithm’s acceleration depends on extreme events being few yet carrying enough probability mass to be isolated. Turbulence signals exhibit this structure, while increasing Reynolds number both enlarges the search space and strengthens intermittency.

A. Structure as a quantum computational resource √

  • The acceleration requires extreme events to be few yet carry enough normalized probability; rarity alone is insufficient.This concentration supplies part of the information a marking oracle would otherwise provide externally.Source: A. Structure as a quantum… · p. 10
  • Across 576 signals, QG1 reduced each 1024-point signal to five candidates at the median and raised true-maximum observation probability nearly eightfold.The median filtered candidate concentration was qK = 0.89282.Source: A. Structure as a quantum… · p. 10, Figure 5 · p. 11
  • Increasing Reynolds number enlarges the resolved search space while strengthening the intermittency that can make candidate isolation efficient.The certified-search scalings and nominal crossover estimates are summarized in Table II.Source: A. Structure as a quantum… · p. 11
  • Present homotopy calculations reach nonlinear flow regimes of order O(10^2), also the order of the nominal preparation-dominated crossover for an equivalent three-dimensional resolved volume.Higher-Reynolds-number JHTDB is treated separately as a stress test of the extrema-search stage.Source: A. Structure as a quantum… · p. 11

B. End-to-end and verifiable quantum advantage

A useful scientific quantum advantage requires connecting efficient state generation, extremum extraction, and classical verification. The paper presents these as one workflow, with polylogarithmic dependence under the combined algorithmic assumptions.

B. End-to-end and verifiable quantum advantage

  • The proposed workflow connects nonlinear physical-state preparation, coherent generation of derived quantities such as velocity gradients, extrema extraction, and classical verification.The fluid-dynamics pipeline uses the quantum homotopy algorithm [19] and compact LCU operations.Source: B. End-to-end and verifiable quantum… · p. 11
  • Under the combined assumptions of the preparation and search algorithms, the full workflow retains logarithmic or polylogarithmic dependence on resolved problem size.The stated assumptions include physical sparsity, convergence, conditioning, and postselection.Source: B. End-to-end and verifiable quantum… · p. 11
  • Table II compares preparation-dominated scaling only; its nominal crossovers exclude the repeated candidate-state factor Mglob required for complete recovery.The table presents asymptotic guideposts, not total certified-search crossover claims.Source: Table II · p. 12
  • Global completeness supports recovery of the true extremum with controlled failure probability, and Level I provides an O(log N) classical check.At Level II, the computation becomes a bounded-error decision problem with a classical verification protocol.Source: B. End-to-end and verifiable quantum… · p. 12

VI. CONCLUSIONS

The conclusions frame physical structure as a resource for converting quantum computation into algorithmic advantage. The framework connects global-extremum search and verification, and applies beyond turbulence when relevant events are sufficiently concentrated in an efficiently prepared state.

VI. CONCLUSIONS

  • The paper presents a complete path from nonlinear quantum-state generation to a globally certified, classically verifiable physical observable.Its advances include bounded nonlinear amplitude transformation, amplitude-only certified search, a measurable structure criterion, and validation on turbulent Navier–Stokes data.Source: §VI · p. 12
  • The framework applies beyond turbulence when events of interest occupy a sufficiently concentrated portion of an efficiently prepared quantum state.Potential settings include wave phenomena, imaging, geophysics, and coherently generated scientific data.Source: §VI · p. 12
  • The paper identifies conversion of physical structure into algorithmic advantage as a computational resource beyond problem size alone.The relevant information must be concentrated into a small but sufficiently probable portion of the quantum state.Source: §VI · p. 13

DATA AVAILABILITY

This section describes the access, state-preparation, and filtering methods used to search amplitude-encoded signals, including the costs and conditions for producing and certifying candidates. It also addresses threshold calibration and practical data and code availability.

DATA AVAILABILITY

  • All data is included in the manuscript, and the authors will provide the code upon reasonable request.Source: DATA AVAILABILITY · p. 13

Appendix B: Access model

  • The algorithm assumes state-preparation access, not QRAM or a coherent value/comparison oracle; Grover–Dürr–Høyer search assumes a coherent comparison oracle [9, 10].State preparation exposes the vector coherently but not as a numerical lookup table; amplitude estimation for a singleton estimates |ui|^2, not its sign.Source: Appendix B · p. 14, Appendix A · p. 14, §3 · p. 16

a. Homotopy linearization and nonlinear PDE state preparation

  • The primary PDE-solver route prepares the nonlinear solution state with near-optimal logarithmic or polylogarithmic dependence on problem size, time steps, and accuracy [19].For Burgers flow, the reported homotopy window is TH = O(Re^-1), compared with TC = O(Re^-5/2) for the physically rescaled Carleman comparison; demonstrations reach RH = O(102) [19].Source: §1 · p. 14, a. Homotopy linearization and… · pp. 14–15

b. Coherent sensor preparation

  • A coherent sensor can encode a field into amplitudes without measuring and reloading N classical values, provided its response preserves or enhances the extreme tail.The sensor preparation must be repeatable and provide coherent global or multimode access; sequentially interrogating N locations costs Θ(N), eliminating end-to-end asymptotic advantage.Source: b. Coherent sensor preparation · p. 15

2. Near-optimal iterative matrix–vector operations

  • The compact LCU construction implements repeated matrix actions and inverse actions using a convergent truncated Neumann expansion, with sparsity, error, and conditioning factors in its cost.For fixed-order sparse discretizations, s = O(1), and the dependence on matrix–iteration size Ngτ is near optimal up to the stated logarithmic and conditioning factors.Source: §2 · p. 16

3. Amplitude estimation and measurement

  • Quantum amplitude estimation can estimate singleton probabilities, but it does not reveal real-amplitude signs; sign determination is deferred until after candidate localization.The sign protocol is described in Appendix H.Source: §3 · p. 16

1. State Discrimination Cost

  • Exact extrema search cannot be gap-independent for arbitrary amplitude states; the algorithm instead isolates a structured candidate tail before resolving fine value precision.The construction targets an inverse-logarithmic-mass tail across a wider fuzzy band, then compresses it to O(log N) addresses before fine precision is needed.Source: §1 · p. 17

2. Mean and variance statistics for threshold selection

  • Coarse mean and variance estimates can place a scalar threshold, but retained candidate mass remains a physical structure condition and calibration need not resolve the top-two amplitude spacing.The chosen lower edge can enforce the logarithmic candidate-count condition; the theorem requires a selected threshold satisfying both candidate-count and retained-mass conditions.Source: §2 · p. 17
  • Mean and variance statistics set only the fuzzy-transition location, with one-time cost separate from QG1 and certification; threshold error ετ < ΓN/4 leaves usable width ΓN − 2ετ.Source: §2 · p. 17

Appendix D: Bounded polynomial filtering with a finite transition width

  • With ΓN = (log2 N)^−3/2, the filter degree is O[(log2 N)3/2 log(1/ηfilt)], independent of top-amplitude spacing; its fixed-accuracy transition-width scaling is optimal.The finite transition interval leaves amplitudes within [λ, λ + ΓN] unresolved for later certification.Source: Appendix D · pp. 18–19

Appendix E: Amplitude block encoding and all-degree Chebyshev walk

  • A Hermitianized amplitude block encoding exposes each ui as an eigenvalue without measuring it, and projected Chebyshev-walk powers implement Tℓ(ui).The walk’s projected powers provide the Chebyshev basis required by the polynomial filter.Source: Appendix E · p. 20

Appendix F: Coefficient synthesis, success probability, and proof of Theorem 1

  • Appendix F combines Chebyshev walk powers with coefficients and accounts for transformed-state success, candidate recovery, and final certification costs.Source: Appendix F · p. 21

1. Coefficient-weighted synthesis

  • The coefficient-weighted walk realizes the nonlinear amplitude transformation; polylogarithmic degree makes Cd polylogarithmic in N, with damped-Chebyshev realizations having Cd = O(log d).Source: §1 · p. 21

B. Retained mass and success probability

  • Retained candidate mass PR controls preparation success, while ηfilt^2/PR controls normalized leakage outside the candidate set.For every i in RΓ, the filter satisfies |pd(ui)| ≥ 1 − ηfilt.Source: B. Retained mass and success probability · p. 21

C. Cost of preparing a filtered candidate state

D. Proof of Theorem 1 and polylogarithmic specialization

This section proves global recovery under structured-family conditions and specializes the tail-search construction to four extrema objectives, establishing polylogarithmic complexity when the required structural and certification conditions hold. It also describes optional preprocessing, localization, and candidate-localized sign-estimation refinements, with explicit fallbacks or objective-specific conditions where applicable.

D. Proof of Theorem 1 and polylogarithmic specialization

  • For the structured family, L = log2 N, ΓN = L^-3/2, PR ≥ cP L^-a (fixed a > 0), and ηfilt² ≤ ξPR (0 < ξ < 1) imply Mglob = O(L log(1/δglob)).The bounds also give Pe ≥ (1 − ηfilt)²PR.Source: D. Proof of Theorem 1 and… · p. 22

Appendix G: Quantum Gadget 2: local contrast, fuzzy search, and greedy sort

  • QG2 offers optional local-excess preprocessing and fuzzy-search/greedy-sort localization; neither is required for Theorem 1, and raw input with explicit candidate enumeration remains a fallback.The refinements aim respectively to enhance neighborhood-relative exceptions and expose an extremal address after candidate preparation.Source: Appendix G · p. 22

1. Local-excess operator

  • The local-excess operator subtracts a neighborhood average, suppressing smooth backgrounds while retaining localized peaks, troughs, or curvature; its width sets the comparison scale.It behaves as a high-pass transformation at small wave number, but is optional when the objective is an extremum of the original signal.Source: §1 · p. 22

2. LCU implementation and combined useful mass

  • LCU residual preprocessing must account for both residual-state preparation and subsequent QG1 filtering, since normalization can make a low-energy residual look concentrated without making it cheap to obtain.The neighborhood width does not appear linearly in the stated query cost, but implementation-dependent overhead must be included if coherent preparation and shifts are not polylogarithmic.Source: §2 · p. 23

3. Proof of Proposition 2: guarded local-excess preprocessing

  • Guarded preprocessing chooses among admissible widths using calibrated production cost, cannot be worse than verified raw-QG1, and adds at most polylog N calibration work when |M| ≤ polylog N.A nonzero width is accepted only when improved candidate contrast and useful filtered mass compensate for residual-state preparation cost.Source: §3 · p. 23

4. Proof of Proposition 3: fuzzy search and greedy sort

  • Fuzzy search makes coarse child-probability decisions across L address levels and reuses the same measured candidate addresses throughout, so depth adds a confidence factor rather than an L-fold preparation cost.The guarantee requires a hierarchy in which the correct-path prefixes have sufficient probability and child bias; without it, QG2b is not invoked.Source: §4 · pp. 23–24

1. Enumeration fallback

  • When the hierarchy promise is unavailable, enumeration is the rigorous fallback: if qmin = Ω(L^-1), Menum = O(L log(L/δenum)) measurements suffice.The appendix frames this stage as recovering and comparing the surviving addresses to certify an extremum.Source: §1 · p. 25, Appendix H · p. 25

2. Value certification; 3. Sign estimation after candidate localization

  • After compression to K = O(L) candidates, exact digital values need K−1 comparisons, while real-amplitude signs require controlled access to a fixed US because ordinary measurements reveal only squared amplitudes.The sign procedure is applied only after QG1/QG2 localization; copies of an unknown state alone cannot distinguish |Ψ⟩ from −|Ψ⟩.Source: §2 · p. 25, §3 · pp. 25–26

3. Sign estimation after candidate localization

  • After candidate localization, sign estimation adds constant overhead for Ω(1) selected-sign mass and inverse-polylogarithmic overhead for inverse-polylogarithmic mass; without U|u|, candidate-first interference remains the default.Source: §3 · p. 26

4. Four extrema objectives

  • Largest-magnitude, largest-positive, and most-negative searches are the same amplitude-tail problem: use both tails, the upper tail, or a reflected lower tail, with no new state representation.Source: §4 · pp. 26–27
  • Smallest-magnitude search subtracts a common index-independent background and reflects the resulting negative tail; position-dependent backgrounds change the objective, and state preparation is an extra access requirement.The original magnitudes are used for final certification, so background subtraction does not change the reported physical objective.Source: §4 · p. 27
  • Polylog N queries solve all four structured extrema when candidate count and mass, transition width, recovery yield, and certification precision meet Theorem 1 conditions; minimum magnitude additionally requires efficient background-state preparation.Source: §4 · p. 27

Appendix I: Proof of global completeness

The proof shows that the global maximum belongs to the candidate set and bounds the repeated sampling needed to recover it. It then separates the costs governed by retained mass and candidate count.

Appendix I: Proof of global completeness

  • The global maximum lies in the safely retained region and therefore in the candidate set.The safely retained set is nonempty when its probability mass is positive.Source: Appendix I · p. 28
  • After recovering a global-extremum address, the final value-certification step fails with probability at most δcert.Source: Appendix I · p. 28
  • When the filtered mass is at most ξPR, q* = Ω(L^-1) and Mglob = O[L log(1/δglob)]; retained-mass exponent sets per-state preparation cost, while candidate count sets required successful samples.The bound concerns the inverse-polylogarithmic specialization described in the passage.Source: Appendix I · p. 28

Appendix J: Proof of the two levels of classical verification

The appendices distinguish checking the reported extremum under faithful execution from verifying an untrusted quantum computation. They also connect the search guarantees to physical structure, end-to-end PDE preparation, and verification of the composite computation.

1. Level I: verification of the reported extremum

  • Level I checks that the reported candidate is globally maximal, assuming faithful quantum execution.The classical check uses a missing-probability bound to rule out any unobserved address with a larger amplitude; checking the final certificate takes O(log N) arithmetic operations.Source: §1 · pp. 28–29

2. Level II: verification of an untrusted quantum computer output

  • Level II turns a proposed extremal address into a bounded-error decision computation that can be checked without trusting the quantum device.When Tcirc and κsec are polylogarithmic in N, the classical-verifier complexity TV is also polylogarithmic.Source: §2 · p. 29

Appendix K: Structure factor, Reynolds-number scaling, and crossover estimates

  • The physical structure condition requires safely retained events to carry sufficient intensity relative to the rms background.The database-size exponent depends on the physical problem and data dimensionality; the crossover estimates are asymptotic guideposts, not finite-N predictions, and omit the repeated-state factor for complete recovery.Source: Appendix K · pp. 29–30

Appendix L: End-to-end nonlinear-PDE-to-extremum complexity

  • Under the stated solver and compact-LCU assumptions, coherent PDE preparation, optional gradient construction, and extrema search retain polylogarithmic query complexity when Ng = Θ(N).The pipeline does not reconstruct the Ng-component field classically between stages.Source: Appendix L · p. 30

1. Compatibility of the nonlinear regimes

  • The reported Burgers preparation reaches RH = O(10^2), while the three-dimensional volume-search crossover is Re ≃ 1.38 × 10^2; these are distinct Reynolds quantities.The Reλ ≃ 433 JHTDB data stress-test the search stage and are not claimed to be the identical state prepared by the homotopy calculation.Source: §1 · p. 31

2. Verification of the composite computation

  • When the preparation, derived-field, and search circuits have efficient classical descriptions, Ref. can externally verify the composite PDE-to-extremum computation.This verification layer supplements the algorithm's internal global-extremum certificate.Source: §2 · p. 31

Appendix M: Numerical definitions and data-processing pipeline

The appendix specifies how the turbulence line signals are tested, filtered, and diagnosed. It distinguishes filtered-state concentration from circuit success and qualifies the finite-size resource comparison.

Appendix M: Numerical definitions and data-processing pipeline

  • The numerical study uses 576 real velocity-gradient line signals, each containing N = 1024 samples.The signals come from the forced-isotropic Johns Hopkins Turbulence Database simulation.Source: Appendix M · p. 31
  • A threshold scan selects a candidate tail, then Jackson-damped Chebyshev filters are tested; dmin is the smallest tested degree meeting the adopted retained-mass and concentration conditions.Source: Appendix M · p. 31
  • PK measures input mass in the original tail, Pe mass retained by the polynomial, psucc success probability of the coefficient-weighted QG1 branch, and qK filtered-state concentration on the diagnostic leading set.Kfuzzy counts amplitudes above the calibrated lower candidate threshold; leakage is 1 − qK.Source: Appendix M · p. 31
  • The concentration ratio measures the increase in conditional probability of observing the true maximum after successful filtering, not the full circuit success probability psucc.Source: Appendix M · p. 31
  • The finite-size resource comparison estimates values only after candidate compression and is not a comparison with ideal GDH using a cost-free exact value-comparison oracle.Source: Appendix M · p. 31

Related papers

Loading 2610.04024v1…