18 entries matching the current filters. Sorted by recently added.
Does every BQP decision problem admit an interactive proof with one polynomial-time honest quantum prover and a probabilistic polynomial-time classical verifier, using polynomially many rounds of classical messages,…
For explicitly budgeted spatially/temporally correlated or adversarial noise, establish fault-tolerance thresholds and space-time overhead bounds for two- or three-dimensional local architectures. Specify local…
Given a full classical description of an arbitrary reference state sigma and copies of an unknown N -qubit state rho , determine the optimal copy complexity of testing rho= sigma versus | rho- sigma | 1 ge varepsilon ,…
Determine the quantum running-time frontier for search and decision LWE with explicitly specified dimension n , modulus q , error distribution and sample access, and for SVP/CVP with stated approximation factor. A focal…
Does graph isomorphism on n -vertex graphs admit a uniform polynomial-time bounded-error quantum algorithm?
Consider n qubits on a square grid, with n^3 layers cycling through the four horizontal/vertical even/odd matchings and independent Haar-random two-qubit gates. Prove that a polynomial-time classical sampler within…
Prove average-case approximate hardness for complex-Gaussian permanents, together with a robust reduction strong enough to rule out polynomial-time classical sampling within inverse-polynomial total-variation error for…
Do universal constants c,C 0 exist such that every multilinear p: -1,1 ^ n to[0,1] of degree d ge1 and positive variance has some variable i with operatorname Inf i(p) ge c( operatorname Var (p)/d)^C ? Use the uniform…
Can a polynomial-time quantum algorithm, with polynomially many coherent queries to a QMA-complete decision oracle, prepare an accepting witness for every yes-instance of a given QMA verifier? Require bounded overall…
Determine whether mathsf StoqMA = mathsf MA . A central route is to establish general completeness-and-soundness error amplification for StoqMA while preserving the verifier model.
For every fixed locality k and local dimension d , is the commuting-projector local-Hamiltonian promise problem in mathsf NP ? The input has polynomially many commuting k -local projectors with finite rational/algebraic…
Construct stabilizer quantum locally testable codes with constant rate, linear distance, constant check weight and degree, and constant soundness s 0 . For m checks on n qubits, require $| operatorname syn (E)|/m ge s ,…
For H=m^ -1 sum i=1 ^ m h i , with fixed locality and local dimension and 0 le h i le I , prove or disprove that distinguishing lambda min (H) le a from lambda min (H) ge b is mathsf QMA -hard for some constant promise…
Determine whether mathsf QMA (2)= mathsf QMA , or whether two polynomial-size witnesses promised to be unentangled increase verification power.
In the finite-register circuit model with Hadamard, T and CNOT gates and computational-basis initialization/measurement, determine whether mathsf QMA 1= mathsf QMA . Here mathsf QMA 1 requires acceptance probability…
Determine whether quantum witnesses increase the power of polynomial-time quantum verification: mathsf QMA stackrel ? = mathsf QCMA , without an oracle.
Determine whether mathsf NP subseteq mathsf BQP ; equivalently, whether an NP-complete decision problem has a polynomial-time bounded-error quantum algorithm.
Determine whether mathsf BPP = mathsf BQP , or prove that efficient bounded-error quantum computation is strictly more powerful than efficient randomized classical computation.