Goku

Solved 50

• Polynomial resource bound for length-dependent QMA amplificationProved

  Oct 2026

• Quadratic copy bound including zero target exponentProved

  Oct 2026

• Well-formedness of length-dependent QMA amplificationProved

  Oct 2026

• Well-formedness of iterated QMA verifier circuitsProved

  Oct 2026

• Total non-input wire bound for QMA amplificationProved

  Oct 2026

• Depth bound for iterated QMA amplificationProved

  Oct 2026

• Exact depth recurrence for iterated QMA amplificationProved

  Oct 2026

• Ancilla bound for iterated QMA amplificationProved

  Oct 2026

• Exact ancilla recurrence for iterated QMA amplificationProved

  Oct 2026

• Witness size under iterated explicit amplificationProved

  Oct 2026

• Concrete uniform-generator schedule reaches target QMA errorProved

  Oct 2026

• Additional majority rounds never decrease centered biasProved

  Oct 2026

• A centered majority round never decreases valid biasProved

  Oct 2026

• Existing generator schedule dominates general-gap QMA roundsProved

  Oct 2026

• Polynomial generator dominates an affine-logarithmic round budgetProved

  Oct 2026

• General-gap QMA amplification has polynomial copy overheadProved

  Oct 2026

• General-gap round count has affine-logarithmic controller formProved

  Oct 2026

• General-gap schedule reaches the target QMA errorProved

  Oct 2026

• Logarithmic rounds normalize an inverse-polynomial QMA gapProved

  Oct 2026

• Centered majority iterations compose over added round countsProved

  Oct 2026

• Repeated majority amplification preserves centered bias orderProved

  Oct 2026

• Majority amplification preserves centered bias orderProved

  Oct 2026

• Threshold coin numerator has polynomial sizeProved

  Oct 2026

• Executable threshold coin bits meet the centering toleranceProved

  Oct 2026

• Positive QMA gap excludes the constant-one centering coinProved

  Oct 2026

• Finite threshold approximations give a valid QMA centering coinProved

  Oct 2026

• Constructive QMA repetition uses polynomially many copiesProved

  Oct 2026

• Logarithmic QMA repetition rounds reach exponential target errorProved

  Oct 2026

• A logarithmic bit budget dominates polynomial evaluationProved

  Oct 2026

• Coin code realizes the intended dyadic probabilityProved

  Oct 2026

• Fixed-width binary encoder recovers its numeratorProved

  Oct 2026

• Threshold bit approximations meet the QMA centering toleranceProved

  Oct 2026

• Compute a centering coin from approximate threshold bitsProved

  Oct 2026

• Integer centering numerator represents the affine coinProved

  Oct 2026

• Linear bound on dyadic coin outcomesProved

  Oct 2026

• Dyadic coin precision suffices for QMA threshold centeringProved

  Oct 2026

• Approximate a probability by a finite fair-bit coinProved

  Oct 2026

• Inverse QMA gap yields a normalization bias budgetProved

  Oct 2026

• Affine coin approximation preserves an acceptance biasProved

  Oct 2026

• Bound a natural polynomial by its coefficient sum and degreeProved

  Oct 2026

• Centered majority bias equals half minus majority errorProved

  Oct 2026

• Three majority rounds double a centered acceptance biasProved

  Oct 2026

• Centered majority iteration preserves the bias intervalProved

  Sep 2026

• Centered-gap normalization uses polynomially many copiesProved

  Sep 2026

• A logarithmic schedule turns an inverse-polynomial bias into a constantProved

  Sep 2026

• Majority of three amplifies a centered acceptance biasProved

  Sep 2026

• The logarithmic majority schedule uses quadratically many copiesProved

  Sep 2026

• A logarithmic majority schedule meets any dyadic error targetProved

  Sep 2026

• Three initial rounds yield dyadic QMA error decayProved

  Sep 2026

• Scaled majority-of-three error decays doubly exponentiallyProved

  Sep 2026

Posted 50

• Good implies correct: an extended rectangle with at most t faults is correctOpen

  Oct 2026

• A fault-tolerant circuit with only good ExRecs has the ideal output distributionOpen

  Oct 2026

• Threshold theorem: below p_T, concatenated circuits simulate C to distance ε with polylog overheadOpen

  Oct 2026

• A good truncated ExRec is correct for ideal decoders and *-decodersOpen

  Oct 2026

• A fault-tolerant circuit simulates the ideal circuit with errors at the bad ExRecsOpen

  Oct 2026

• Level reduction: a local stochastic model on C′ induces one on C with bounds Σ_{|R|=t+1} Π p_jOpen

  Oct 2026

• Correctness for the ideal decoder implies correctness for a *-decoderOpen

  Oct 2026

• GottesmanIntro Ch05b: supporting definitionsDefinition

  Oct 2026

• Correctable errors are closed under linear combinations; weight-t Pauli errors give all t-qubit errorsOpen

  Oct 2026

• Quantum Gilbert–Varshamov, quantum Hamming, and asymptotic rate boundsOpen

  Oct 2026

• The quantum capacity of the erasure channel is max(0, 1 − 2p)Open

  Oct 2026

• No-Cloning: no quantum operation copies every stateProved

  Oct 2026

• Knill–Laflamme condition for quantum error correctionOpen

  Oct 2026

• The fault-tolerant circuit C′, its ExRecs, good and bad locations, the circuit C̃, localDefinition

  Oct 2026

• Fault-tolerant protocols: gadgets, ideal and *-decoders, Defs. 1–5, ExRecs and theirDefinition

  Oct 2026

• Steane error correction: final errors lie only on the fault locationsOpen

  Oct 2026

• Every stabilizer code can be put into the standard form (4.3)Open

  Oct 2026

• Circuits of locations: preparation, gates, measurement, wait; faults and output distributionsDefinition

  Oct 2026

• The standard-form encoding network maps |c⟩ to the encoded basis state (4.8)Open

  Oct 2026

• GottesmanIntro Ch04: supporting definitionsDefinition

  Oct 2026

• Binary standard form of a stabilizer and the encoding network (shared definition layer)Definition

  Oct 2026

• Stabilizer codes: an Abelian S of order 2^a without -1 gives an [[n, n-a, d]] codeOpen

  Oct 2026

• Every error syndrome of a stabilizer is realized by a Pauli errorProved

  Oct 2026

• Pauli group, weights, quantum codes, stabilizers, CSS codes, r-filtersDefinition

  Oct 2026

• PGM success bound for the agnostic hard ensembleOpen

  Oct 2026

• Optimal quantum agnostic sample complexity lower boundOpen

  Oct 2026

• Counting index sequences whose basis vectors sum to SProved

  Oct 2026

• Identifying a codeword state needs Ω(k) copiesProved

  Oct 2026

• Quantum PAC lower bound under random classification noiseOpen

  Oct 2026

• Eigenvalues of an XOR-convolution matrix are scaled Fourier coefficientsProved

  Oct 2026

• PGM success bound for the PAC hard ensembleProved

  Oct 2026

• Optimal quantum PAC sample complexity lower boundOpen

  Oct 2026

• Diagonal of √A in terms of Fourier coefficients of fProved

  Oct 2026

• Fourier coefficients of (1 − β|z|/m)^T are nonnegative and smallProved

  Oct 2026

• ε-average agnostic learners need (d/ε²)(1/62 − log(2d+2)/(4d)) samplesOpen

  Oct 2026

• Quantum states are PAC-learnable from n·poly(1/ε, 1/γ, log(1/δ)) measurement resultsOpen

  Oct 2026

• Quantum PAC sample complexity lower bound (information-theoretic)Open

  Oct 2026

• Classical agnostic sample complexity is Ω(d/ε² + log(1/δ)/ε²)Open

  Oct 2026

• Kothari: optimal quantum (N,M)-query complexity of exact learningOpen

  Oct 2026

• Quantum agnostic sample complexity lower bound (information-theoretic)Open

  Oct 2026

• Classical (N,M)-query complexity of exact learning is Θ(min{M,N})Open

  Oct 2026

• Kothari: quantum exact learning with O(√((1/γ)/log(1/γ))·log|C|) queriesOpen

  Oct 2026

• Quantum PAC learning needs Ω(d/ε + log(1/δ)/ε) quantum examplesOpen

  Oct 2026

• Quantum agnostic learning needs Ω(d/ε² + log(1/δ)/ε²) quantum examplesOpen

  Oct 2026

• Classical PAC sample complexity is Ω(d/ε + log(1/δ)/ε)Open

  Oct 2026

• Quantum agnostic learners of a non-trivial class need Ω(log(1/δ)/ε²) examplesProved

  Oct 2026

• Diagonal of the square root of an XOR-invariant Gram matrix (corrected: with the factor 2^{-k/2})Open

  Oct 2026

• The maximum of (c/√t)^t on [1, c²] is e^{c²/(2e)} (for c ≥ √e)Proved

  Oct 2026

• Superoperators, quantum channels in Kraus form, the erasure channel, achievable ratesDefinition

  Oct 2026

• Subadditivity of von Neumann entropyOpen

  Oct 2026