PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Approximation Complexity of Classical Optimization Problems

Stuart Hadfield

arXiv:2610.09584v1quant-phcs.CC

TL;DR

The paper studies approximation guarantees for uniform quantum algorithms on classical optimization problems, including the target of exceeding randomized classical hardness thresholds for unrestricted MaxCut and MaxSAT. It defines bounded-error quantum approximation classes and proves conditional hierarchy and quantum–classical separations using number-theoretic problems. Certified Maximum Order and Discrete-Logarithm Fitting yield such separations, while the unrestricted MaxCut/MaxSAT gap remains open.

  • Problem

    For unrestricted MaxCut and MaxSAT, the target is a uniform quantum output ratio above the randomized classical hardness threshold on the same explicit-input problem.

    Source: C. Broader problem families · p. 9

  • Method

    The paper defines bounded-error quantum approximation classes and uses reductions involving factoring and discrete-logarithm search to establish conditional separations.

    Source: §I · p. 2, §II · p. 3

  • Results

    Assuming NP ⊈ BQP, the quantum classes form a strict hierarchy; Certified Maximum Order and Discrete-Logarithm Fitting also yield conditional quantum–classical approximation separations.

    Source: §I · pp. 1–2

  • Takeaways & Limitations

    Conditional separations are established for Certified Maximum Order and Discrete-Logarithm Fitting under factoring and safe-prime discrete-logarithm assumptions.

    Source: §I · p. 2

    A quantum–classical gap for unrestricted MaxCut and MaxSAT remains open.

    Source: C. Broader problem families · p. 9

Abstract

from arXiv · show

Classical approximation complexity asks what solution quality can be guaranteed with polynomial-time computation. The classes APX, PTAS, and FPTAS distinguish a fixed approximation ratio, approximation to any fixed accuracy, and approximation schemes whose running time is also polynomial in inverse accuracy. Their randomized counterparts are R-APX, R-PTAS, and R-FPTAS. We define bounded-error quantum counterparts BQ-APX, BQ-PTAS, and BQ-FPTAS. Membership requires a uniform quantum algorithm that, on every input, returns a feasible classical solution achieving at least the claimed approximation ratio with probability at least 2/3. Scores (objective values) must be efficiently classically computable. Running time includes parameter selection, preparation, measurement, decoding, and repetition. Many quantum optimization methods are used heuristically, and high benchmark scores alone do not establish these guarantees. We further establish a conditional hierarchy for logarithmic, polynomial, and exponential approximation factors. Assuming NP $\subsetneq$ BQP, the quantum classes form a strict hierarchy. Problems based on prime factorization and discrete logarithms give conditional quantum-classical separations. Certified Maximum Order has an exact quantum algorithm, while any randomized polynomial-time algorithm guaranteeing at least an inverse-polynomial approximation ratio on every input would yield efficient factoring. Discrete-Logarithm Fitting has an exact quantum algorithm and a deterministic one-half approximation, but any fixed improvement over one half would give a randomized polynomial-time algorithm for the safe-prime discrete logarithm problem. Our results show, under explicit complexity assumptions, that quantum computation can improve worst-case approximation guarantees. A quantum-classical gap for common problems such as MaxCut or MaxSAT remains open.

I. INTRODUCTION

The paper formalizes worst-case approximation guarantees for quantum algorithms that output classical solutions, addressing the gap between strong benchmark scores and guarantees across all inputs. It establishes conditional quantum-class separation results and identifies unrestricted MaxCut and MaxSAT as open cases.

I. INTRODUCTION

  • Quantum optimization methods can score highly on test instances without establishing a worst-case ratio or bounding the full cost of parameter search and sampling.The paper therefore requires uniformly specified algorithms, guaranteed solution quality, and a bound on total computational cost.Source: §I · p. 1
  • The paper defines bounded-error quantum approximation classes for classical-output algorithms, requiring feasible solutions to meet the claimed ratio with probability at least 2/3 on every input.All algorithmic steps, including preparation, measurement, decoding, and repetition, count toward running time.Source: §I · p. 1
  • Under NP ⊈BQP, Max-E3SAT and Planar Vertex Cover witness strict inclusions among the quantum approximation classes, without separating quantum classes from their randomized counterparts.Max-E3SAT has a deterministic constant-ratio algorithm but no quantum PTAS; Planar Vertex Cover has a deterministic PTAS but no quantum FPTAS.Source: §I · pp. 1–2
  • If Factor /∈FBPP, Certified Maximum Order lies in BQ-FPTAS but outside R-POLY-APX, since any polynomial-factor randomized approximation would yield randomized polynomial-time factoring.A quantum algorithm using factoring and period finding constructs an exact optimum.Source: §I · p. 2
  • If safe-prime discrete logarithm is not in FBPP, Discrete-Logarithm Fitting lies in R-APX ∩ BQ-FPTAS but outside R-PTAS.Predicting the more common label gives a deterministic 1/2-approximation, while quantum discrete logarithm finds a perfect fit; any fixed randomized improvement over 1/2 would solve the search problem.Source: §I · p. 2
  • Theorem 8 constructs a two-score optimization problem where a feasible dummy scores one and any efficiently verifiable witness scores two, making every fixed improvement over 1/2 recover a witness.If quantum polynomial time finds the witnesses but randomized classical polynomial time cannot, the problem lies in R-APX ∩ BQ-FPTAS \ R-PTAS.Source: §I · p. 2
  • For unrestricted MaxCut and MaxSAT, the open target is a uniform quantum output ratio above the randomized classical hardness threshold on the same explicit-input problem.The paper also identifies bounding solution quality and production cost for QAOA and compressed encodings as further tasks.Source: §I · p. 2

II. CLASSICAL-OUTPUT QUANTUM APPROXIMATION CLASSES

This section defines quantum approximation classes for algorithms that return feasible classical solutions, and specifies the uniformity, success, and runtime requirements for membership. It then establishes containments, hierarchy results, and conventions for reductions and amplification.

II. CLASSICAL-OUTPUT QUANTUM APPROXIMATION CLASSES

  • For a maximization NPO problem, a feasible solution has a nonnegative, efficiently computable score and achieves ratio v(x, y)/OPT(x), with OPT(x) > 0.Candidate strings have polynomially bounded length, and feasibility is recognizable in deterministic polynomial time.Source: §II · p. 3
  • A bounded-error approximation algorithm must return a feasible solution meeting its claimed ratio with probability at least 2/3 on every input.An invalid output is a failure, and the same output convention applies to randomized classical and quantum algorithms.Source: §II · p. 3
  • Quantum runtime includes circuit generation, classical parameter search, preparation, measurement, decoding, verification, repetitions, and output selection.Algorithms are uniformly specified, may use intermediate measurements, and receive no quantum advice.Source: §II · p. 3
  • Replacing randomized computation with uniform bounded-error quantum computation defines BQ-APX, BQ-PTAS, and BQ-FPTAS with the corresponding approximation guarantees and time bounds.The FPTAS runtime accounts for input length, inverse accuracy, and the encoding length of the supplied accuracy.Source: §II · p. 3
  • Deterministic classes are contained in their randomized counterparts, which in turn are contained in the corresponding bounded-error quantum classes.The latter containments are R-APX ⊆ BQ-APX, R-PTAS ⊆ BQ-PTAS, and R-FPTAS ⊆ BQ-FPTAS.Source: §II · p. 3
  • Membership transfers backward through an explicit ratio-preserving solution reduction, and polynomial input/output overhead preserves the corresponding approximation-class time bounds.Under Factor /∈FBPP, no classical APX problem can be BQ-APX-complete under these reductions, since such a reduction would give CMO a classical constant-factor algorithm.Source: §II · p. 3
  • If NP ⊈BQP, Max-E3SAT, Planar Vertex Cover, and MaxCut witness strict inclusions among the bounded-error quantum classes.MaxCut has a deterministic 1/2-approximation but no quantum PTAS under this assumption; bipartite MaxCut, by contrast, is exactly solvable.Source: §II · p. 4
  • Fixed-probability success thresholds can be changed by repetition, but a uniform PTAS requires an effective generator for its fixed-accuracy algorithm family.Amplifying success to at least 1 − ξ takes O(log(1/ξ)) repetitions when the encoding cost is charged; the section also introduces logarithmic, polynomial, and exponential approximation factors in input length.Source: §II · p. 4

III. DECODED MEAN AND CLASSICAL OUTPUT

The section connects expected decoded scores to guarantees for returned classical solutions, including bounded-error approximation classes. It applies this transfer to fixed-depth MaxCut and relates decoded-mean and output-class formulations under uniformity and runtime conditions.

III. DECODED MEAN AND CLASSICAL OUTPUT

  • For maximization, bounded scores let an expected decoded score imply a probability guarantee for returning a solution above a chosen threshold.The section states that the bound is tight for each fixed (µ, τ), with equality attained by a two-point distribution supported at τ and 1.Source: §III · pp. 4–5
  • A decoded score observable G has expectation equal to the expected score of the classical candidate returned by its decoder.For a different surrogate Hamiltonian H, a separate argument relating H to G is needed before applying the corollary.Source: §III · pp. 4–5
  • Decoded-mean and bounded-error output versions of BQ-APX, BQ-PTAS, and BQ-FPTAS coincide up to constant or ε-rescaling under the stated uniformity and runtime conditions.The output algorithm may repeat the decoder and retain the best valid candidate.Source: §III · p. 5
  • For always-feasible minimization decoders, an expected cost at most (1 + ϵ′) OPT bounds the probability of exceeding (1 + ϵ) OPT by ϵ′/ϵ.Setting ϵ′ = ϵ/3 gives success probability at least 2/3; the zero-score-on-failure convention does not apply to minimization.Source: §III · p. 5
  • For p = 1 QAOA on unweighted 3-regular graphs, expected cut value is at least 0.6924 OPT; the best of 14 measured cuts exceeds (2/3) OPT with probability above 2/3.The per-run probability bound used for repetition is 0.0772; the section also notes that one run suffices for sufficiently large graphs by a variance bound.Source: §III · p. 5
  • The section contrasts the 0.7559 p = 2 QAOA mean-ratio bound on unweighted 3-regular MaxCut with a quoted 0.9326 classical guarantee for unweighted graphs of maximum degree three.The p = 17 result gives an expected cut fraction of approximately 0.8971 on unweighted 3-regular graphs of girth at least 36 and does not improve the quoted classical ratio guarantee.Source: §III · pp. 5–6

IV. SEARCH PADDING AND CERTIFIED MAXIMUM ORDER

This section presents conditional quantum–classical approximation gaps. Certified Maximum Order has graded element-order scores, and even a polynomial-factor randomized approximation would yield a factoring algorithm.

IV. SEARCH PADDING AND CERTIFIED MAXIMUM ORDER

  • Certified Maximum Order scores feasible solutions by element order, and even a polynomial-factor randomized approximation would yield a factoring algorithm.The passage identifies this as the section’s strongest conditional quantum–classical separation.Source: §IV · p. 6

A. The generic search threshold

Search padding turns a classically checkable witness search task into an NPO maximization problem with a one-half approximation threshold. Above that threshold, approximation recovers a witness; quantum-solvable but classically hard search therefore yields a conditional class separation.

A. The generic search threshold

B. Certified Maximum Order

Certified Maximum Order (CMO) optimizes a verifiable multiplicative-order certificate, with an exact quantum solution and a conditional barrier to randomized classical approximation. Its graded objective makes even polynomial-factor approximation sufficient to recover a factorization.

B. Certified Maximum Order

  • A CMO instance is N ≥ 3, and a feasible certificate gives a unit a modulo N together with its multiplicative order r, which is the score.The optimum is λ(N), the largest order of a unit modulo N.Source: B. Certified Maximum Order · p. 6
  • The verifier checks that the listed prime powers certify the exact order; checking only a^r ≡ 1 (mod N) would admit the trivial certificate (1, N).The certificate is polynomially balanced and checked using primality testing, gcds, and modular exponentiation.Source: B. Certified Maximum Order · pp. 6–7
  • The fallback ratio 1/λ(N) > 2^-n places CMO in R-EXP-APX unconditionally, while finer classical placement depends on factoring.Source: B. Certified Maximum Order · p. 7
  • An earlier quantum algorithm computes λ(N) exactly, but CMO also requires an attaining element and a prime factorization of its order for the classical certificate.The paper’s construction factors N and component group orders, then uses the Chinese remainder theorem to build a maximum-order element.Source: B. Certified Maximum Order · p. 7
  • CMO has an exact bounded-error quantum optimizer, while any randomized polynomial-time polynomial-factor approximation yields randomized polynomial-time factoring; if Factor ∉ FBPP, CMO ∈ BQ-FPTAS \ R-POLY-APX.The converse follows by enumerating possible missing multipliers of a certified order before applying the factoring reduction.Source: B. Certified Maximum Order · p. 7
  • A certified order r divides λ(N), so recovering a missing multiplier can turn a polynomial-factor approximation into a factoring algorithm.The reduction enumerates multipliers up to the approximation factor and then applies the factoring-from-an-exponent lemma.Source: B. Certified Maximum Order · p. 7
  • For a factor guarantee ρ(n) ≤ B(n), the reduction runs in B(n) poly(n + log B(n)) time; this quantitative implication alone does not exclude such approximations.For example, a 2⌈n^1/4⌉-factor algorithm would imply factoring in 2^O(n^1/4) randomized time.Source: B. Certified Maximum Order · p. 7

V. INTERPRETING SAME-PROBLEM SEPARATIONS

A quantum-classical separation for the same optimization problem must compare guaranteed output quality under a fixed model, not merely class membership. The paper distinguishes such ratio improvements from strict class inclusions and identifies the remaining question for familiar problems.

V. INTERPRETING SAME-PROBLEM SEPARATIONS

  • CMO separates exact quantum optimization from randomized classical polynomial-factor approximation conditionally, whereas DLog-Fit separates exact quantum optimization from randomized PTAS under its discrete-log assumption.Source: §V · p. 7
  • MaxCut and MaxSAT cannot witness BQ-APX \ R-APX because they already lie in APX, which supplies a deterministic fixed-ratio approximation.Source: §V · p. 7
  • For MaxCut or MaxSAT, the open comparison is whether a uniform quantum algorithm guarantees a ratio above a classical hardness threshold, even if both models remain in APX.Source: §V · p. 7

A. Decoded quantum interferometry

Decoded quantum interferometry (DQI) is assessed through classically scoreable outputs and worst-case guarantees, with its separation claims depending on the input family and access model. The cited results include explicit-input analysis, folded-OPI oracle thresholds, and distinct streaming-space gaps.

A. Decoded quantum interferometry

  • Earlier DQI work reported higher expected satisfied fraction than known polynomial-time classical methods in its regime, while later MaxCut analyses ruled out quantum advantage in the regimes studied.Source: A. Decoded quantum interferometry · p. 8
  • A uniform polynomial-time quantum algorithm for an explicitly represented OPI family gives a bounded-error τ-approximation for every fixed τ < µ when its decoded mean is at least µ OPT on every input.The guarantee uses independent repetition; a quantum-classical gap also requires randomized classical hardness at the same τ.Source: A. Decoded quantum interferometry · p. 8
  • For balanced folded OPI, DQI’s decoded-mean threshold αQ(R) exceeds the sampled-oracle classical threshold αC(R), yielding verified outputs above any fixed threshold between them.Exceeding αC(R) by a fixed amount with constant probability over sampled oracles requires superpolynomially many classical membership queries, even with unlimited between-query computation.Source: A. Decoded quantum interferometry · p. 8
  • Separate streaming results establish space gaps for OPI and Hermite OPI, but concern different resources from explicit-input time classes.Source: A. Decoded quantum interferometry · p. 8

B. Quantum optimizers and encoded readout

Quantum optimizers and encoded-readout methods qualify for approximation classes only when decoded classical outputs meet a proved ratio within the full runtime. The section distinguishes uniform algorithms from advice-dependent resource models and encoded energy from classical solution quality.

B. Quantum optimizers and encoded readout

  • Finite-time annealing, adiabatic optimization, dissipative or measurement-driven preparation, and recursive hybrids are candidates only when final outputs have a proved ratio and control and feedback costs are included.Source: B. Quantum optimizers and encoded… · p. 8
  • For ordinary MaxCut QAOA, a uniform worst-case bound on the measured cost gives a bounded-error output ratio; constrained variants need feasible decoding or repair.Efficient repair is one way to return a feasible candidate or declare failure.Source: B. Quantum optimizers and encoded… · p. 8
  • Instance-specific warm starts or controls without an efficient generator do not establish class membership, while relaxations and incumbents computed within the algorithm are allowed with their costs charged.Source: B. Quantum optimizers and encoded… · p. 8
  • A better-of-sampler-and-deterministic-cut strategy retains a 1/2 guarantee, but a mean upper bound without a tail bound does not rule out rare high-scoring outputs found by repetition.Source: B. Quantum optimizers and encoded… · p. 8
  • Encoded energy is not itself classical cut quality: QRAC/QRAO energy promises may be QMA-complete, while a local decoder transfers standard QRAC packing energy gain to mean cut gain by 1/d^2.A mean-gain identity still needs a ratio bound and efficient repetition; small PCE expectation margins can increase measurement needs.Source: B. Quantum optimizers and encoded… · pp. 8–9

C. Broader problem families

For unrestricted MaxCut and MaxSAT, the target is a uniform quantum output ratio above a randomized-classical hardness threshold on the same explicit-input problem. The section also identifies restricted-family results, score-normalization choices, and other candidate objectives.

C. Broader problem families

  • Unrestricted MaxCut and MaxSAT need a uniform quantum output ratio above a randomized-classical hardness threshold on the same explicit-input problem; known NP-hard gaps constrain possible ratios if NP ⊈ BQP.Restricted families can have different ratios when their definitions and input-access costs are explicit.Source: C. Broader problem families · p. 9
  • For high-girth regular Max-k-Cut families, analyzed QAOA at depth p ≥9 and girth at least 20 exceeds an improved classical local-vector cut-fraction guarantee [70] [71].This comparison is against one classical algorithm on a restricted graph family, not an unrestricted randomized-classical hardness threshold.Source: C. Broader problem families · p. 9
  • Adding a constant to an objective can improve its multiplicative approximation ratio without changing the optimizer, so these problems fix scores in their NPO definitions.Baseline-relative gain is useful when affine invariance is intended, but defines a different taxonomy [19, Sec. II].Source: C. Broader problem families · p. 9
  • Folded-OPI extends an oracle exact-search separation to a graded objective [50] [72], while QAOA mappings identify MaxSAT, Set Cover, Graph Coloring, TSP, and other candidate output-guarantee objectives [10, App. A].The compendium also collects then-known approximation algorithms and hardness results for many of these problems.Source: C. Broader problem families · p. 9

D. Outlook

The outlook distinguishes established conditional quantum approximation separations from the still-open explicit-input time analogue for familiar problems such as MaxCut and MaxSAT. The glossary specifies the approximation classes and the uniformity, success, and runtime conventions used to state them.

D. Outlook

  • The bounded-error quantum hierarchy is strict under NP ⊈ BQP, while CMO and DLog-Fit give conditional quantum–randomized-classical gaps; decoded-mean analyses connect expectation results to output classes when decoder costs meet their definitions.Further growing-factor distinctions are given in Appendix C.Source: D. Outlook · p. 9
  • For familiar APX problems such as MaxCut and MaxSAT, an explicit-input time analogue or unrestricted ratio gap remains open, despite classical-output gaps for OPI membership queries and streaming space [50] [51] [52].QAOA, DQI, and compressed encodings are settings for pursuing guarantees on final decoded solutions.Source: D. Outlook · p. 9

Appendix A: Glossary of complexity classes

  • Approximation classes concern classical-input NPO problems with classically checkable outputs; bounded error requires a feasible ratio-meeting output with probability at least 2/3 on every input.A uniform scheme takes binary-encoded rational accuracy ϵ, and runtime includes its encoding length ℓ(ϵ).Source: Appendix A · p. 12
  • P, NP, BPP, BQP, and QMA denote deterministic polynomial-time decision, polynomially verifiable classical certificates, randomized polynomial-time decision, bounded-error quantum decision, and quantum-witness verification classes, respectively.Source: Appendix A · p. 12
  • NPO requires polynomial-size feasible solutions, polynomial-time instance and feasibility tests, computable objectives, nonempty feasible sets, and positive optima; FBPP denotes randomized polynomial-time search with checkable valid answers on each stated input.APX is NPO with a deterministic polynomial-time approximation at some fixed constant ratio.Source: Appendix A · p. 12
  • PTAS permits polynomial instance-length time for each fixed accuracy, while FPTAS requires time polynomial jointly in instance length, 1/ϵ, and ℓ(ϵ); R-PTAS and R-FPTAS add randomized success probability at least 2/3.R-APX is the randomized polynomial-time version of the fixed-constant APX guarantee.Source: Appendix A · p. 12
  • BQ-APX, BQ-PTAS, and BQ-FPTAS use uniform bounded-error quantum algorithms returning feasible classical solutions, with the scheme runtimes matching their classical class definitions.Source: Appendix A · p. 13
  • The logarithmic, polynomial, and exponential approximation classes each have randomized-classical and bounded-error quantum versions, with the quantum definitions retaining feasible classical output.The logarithmic factor is O(log(2 + N)) for full input length N; the exponential-factor algorithm still runs in polynomial time.Source: Appendix A · p. 13

Appendix B: Proof of the conditional hierarchy

Appendix B develops proofs for the conditional approximation hierarchy, including exclusions and witnesses for fixed- and growing-factor classes, factoring and Certified Maximum Order arguments, and repetition guarantees for fixed-depth MaxCut QAOA. It also presents Discrete-Logarithm Fitting as a thin encoding of discrete-logarithm search, with a PTAS at ε = 1/4 contradicting the theorem, which makes no claim about o(1)-size improvements.

Appendix B: Proof of the conditional hierarchy

  • Under NP ⊄ BQP, Max-E3SAT is not in BQ-PTAS and Planar Vertex Cover is not in BQ-FPTAS, by gap-threshold and integrality arguments.For Planar Vertex Cover, an FPTAS run with ϵ = 1/(2n) must return an optimal cover because cover sizes are integral and 1 ≤ OPT ≤ n.Source: Appendix B · p. 13

1. Beyond fixed ratios

  • Growing-factor classes use O(log(2 + N)), polynomial, or exponential approximation factors with polynomial-time algorithms; randomized classes are contained in their quantum counterparts.Here N is the full input bit length, and EXP refers to the approximation factor, not the algorithm’s running time.Source: §1 · pp. 13–14

2. Proofs

  • Set Cover lies in R-LOG-APX but not BQ-APX, while Max Clique lies in R-POLY-APX but not BQ-LOG-APX, assuming NP ⊈ BQP.Their exclusions follow from logarithmic-gap hardness for Set Cover and an n^1/2 hardness gap for Max Clique.Source: §2 · p. 14
  • Positive-Weight TSP lies in R-EXP-APX but not BQ-POLY-APX; Bin Packing lies in R-APTAS ∩ R-APX but not BQ-PTAS; Rectilinear TSP lies in R-PTAS but not BQ-FPTAS.The TSP and Bin Packing exclusions use decision gaps, while integral rectilinear tour costs turn a sufficiently accurate FPTAS output into an exact optimum.Source: §2 · pp. 14–15, §1 · p. 14

Factoring from an exponent

  • For exponent multiples of λ(N), the gcd-and-squaring routine immediately factors nonunits and has conditional success probability at least 1/2 on units.When component orders differ, the squaring sequence yields a nontrivial square root of one and hence a verified nontrivial factor.Source: Factoring from an exponent · p. 15

Certified Maximum Order

  • Certified Maximum Order has a bounded-error quantum algorithm returning an optimum, while any polynomial-factor approximation would yield efficient factoring.The quantum construction outputs the optimum with probability at least 2/3; the converse tests polynomially many multiples of the returned certified order.Source: Certified Maximum Order · p. 16

Appendix E: Repetition counts for fixed-depth MaxCut QAOA

  • For fixed-depth MaxCut QAOA, independent cuts can be repeated so that the best cut exceeds τ OPT with probability at least 2/3 when the family-wide mean ratio exceeds τ.The passage bounds the probability that all k cuts miss the threshold by ((1 − µp)/(1 − τ))^k; one run suffices when µp = 1.Source: Appendix E · p. 16

Appendix F: Discrete-Logarithm Fitting as a search-padding example

  • Discrete-Logarithm Fitting has a deterministic 1/2-approximation and a bounded-error quantum optimum; any fixed randomized improvement over 1/2 yields an FBPP safe-prime discrete-log algorithm.On the stated promise family, R-PTAS and R-FPTAS membership are equivalent, and both hold exactly when DiscreteLog ∈ FBPP.Source: Appendix F · p. 17
  • A PTAS called at ε = 1/4 contradicts the theorem, and OPT = 1 on valid instances.Every labeled feature can be generated from (g, h).Source: Appendix F · p. 17
  • The construction is a thin optimization encoding of discrete-logarithm search, related to cryptographic learning arguments but with a different task and access model.Source: Appendix F · p. 17
  • The theorem makes no claim about improvements of size o(1).Source: Appendix F · p. 17
Loading 2610.09584v1…