Quantum algorithm

Does the polynomial-factor approximate Shortest Vector Problem admit a polynomial-time quantum algorithm?

• Quantum algorithm
• Computational complexity and computability

Is every promise problem verifiable by a quantum Merlin-Arthur protocol with two unentangled witnesses also verifiable by a protocol with a single arbitrary witness, that is, is \(\mathsf{QMA}(2) = \mathsf{QMA}\) in the standard, unrelativized setting?

• Quantum algorithm
• Computational complexity and computability
• Quantum separability

Does the exact stabilizer rank of the tensor powers of the single-qubit magic state \(|T\rangle\) grow polynomially in the number of copies, or is it not polynomially bounded?

• Quantum algorithm
• Quantum magic
• Quantum circuit complexity
• Computational complexity and computability

Does the Learning With Errors problem in its standard worst-case-hard parameter regime admit a polynomial-time quantum algorithm?

• Quantum algorithm
• Computational complexity and computability

Can polynomial-size constant-depth \(\mathsf{QAC}^0\) circuits compute the parity function, or equivalently, is \(\mathrm{PARITY}\notin\mathsf{QAC}^0\)?

• Quantum algorithm
• Quantum circuit complexity

Does the Dihedral Hidden Subgroup Problem admit a quantum algorithm whose running time is polynomial in the input length?

• Quantum algorithm
• Computational complexity and computability

Is the following bipartite Quantum Max-Cut promise problem in \(\mathrm{BPP}\)?

• Quantum algorithm
• Computational complexity and computability
• Hamiltonian complexity
• Quantum Max-Cut

Is it \(\#\mathrm{P}\)-hard to approximate \(|Z_R|^2\) to relative multiplicative error \(a+o(1)\) on a \(b\) fraction of random Ising instances?

• Quantum algorithm
• Computational complexity and computability
• Quantum supremacy
• IQP sampling

Is it \(\#\mathrm{P}\)-hard to approximate \(\operatorname{ngap}(f)^2\) to relative multiplicative error \(a+o(1)\) on a \(b\) fraction of uniformly random degree-3 polynomials over \(\mathbb{F}_2\)?

• Quantum algorithm
• Computational complexity and computability
• Quantum supremacy
• IQP sampling

Does there exist a fixed family of \(n\)-qubit circuit layouts with \(m=\operatorname{poly}(n)\) one- and two-qubit gates for which the following task is \(\#\mathrm{P}\)-hard?

• Quantum algorithm
• Computational complexity and computability
• Quantum supremacy
• Random circuit sampling

Is the following estimation task \(\#\mathrm{P}\)-hard under randomized polynomial-time Turing reductions?

• Quantum algorithm
• Computational complexity and computability
• Quantum supremacy
• Boson sampling

What is the bounded-error quantum query complexity of finding a triangle in an \(n\)-vertex graph given oracle access to its adjacency matrix?

• Quantum algorithm
• Computational complexity and computability

Does the Graph Isomorphism problem admit a polynomial-time quantum algorithm?

• Quantum algorithm
• Computational complexity and computability

What is the optimal quasiprobability overhead of implementing the complex conjugate of an unknown quantum channel from \(n\) queries?

• Quantum algorithm
• Quantum Resource Theory
• Channel simulation
• Superchannels and quantum combs
• Quantum error mitigation

Can classically simulable operations purify an unknown depolarized pure state from any number of copies?

• Quantum Resource Theory
• Quantum algorithm
• Quantum magic
• Resource conversion
• Quantum state preparation

Can Holevo–Schumacher–Westmoreland codebooks operating at every rate below their ensemble Holevo information be chosen so that their square-root, or pretty-good, measurements have uniform quantum implementations whose cost is polynomial in the blocklength and…

• Quantum algorithm
• Quantum Communication
• Decoding algorithms
• Classical capacity
• Quantum state discrimination

Is the ordinary unassisted quantum capacity a computable function of a finite description of a finite-dimensional quantum channel?

• Quantum Communication
• Quantum algorithm
• Quantum capacity
• Computational complexity and computability

Is the constant-relative-gap local Hamiltonian problem QMA-hard?

• Quantum algorithm
• Hamiltonian complexity
• Computational complexity and computability

Does every language \(L\in\mathsf{BQP}\) admit a single-prover interactive proof with a fully classical verifier, an efficient quantum honest prover, and information-theoretic soundness?

• Quantum algorithm
• Verification of quantum computation
• Computational complexity and computability

Determine the asymptotic weighted circuit cost of preparing tensor powers of a known pure state, and characterize when collective preparation is cheaper per copy than independent preparation.

• Quantum algorithm
• Quantum state preparation
• Quantum circuit complexity
• Additivity and regularization

What is the computational complexity of testing bipartite separability with a constant trace-distance promise gap?

• Quantum algorithm
• Quantum Resource Theory
• Quantum separability
• Computational complexity and computability