Computational complexity and computability

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

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

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

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