Computational complexity and computability

Does every unrestricted quantum collision-finding algorithm satisfy \(T^2S=\Omega(N\log N)\)?

• Quantum Algorithm
• Computational complexity and computability

Can every balanced RSA semiprime be factored with polynomially subquadratic total quantum gate complexity?

• Quantum Algorithm
• Computational complexity and computability
• Quantum circuit complexity

Can every polynomially sparse Hamiltonian be learned with Heisenberg-limited total evolution time when every oracle call has a fixed minimum duration?

• Quantum Metrology
• Quantum Algorithm
• Quantum estimation
• Computational complexity and computability

Can every balanced RSA semiprime be factored in polynomial time using sublinear logical quantum space?

• Quantum Algorithm
• Computational complexity and computability
• Quantum circuit complexity

Can weak final-layer depolarizing noise make constant-depth two-dimensional Haar-random circuits classically samplable to inverse-polynomial total-variation error?

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

Does sparse-oracle quantum linear-system solving require \(\Omega(\kappa\sqrt{s}\log(1/\varepsilon))\) queries in the worst case?

• Quantum Algorithm
• Quantum linear algebra
• Computational complexity and computability

Do computational-basis outputs of one-dimensional Haar-random circuits with fixed amplitude damping have conditional mutual information that decays exponentially with separation, uniformly in circuit depth?

• Quantum Algorithm
• Random circuit sampling
• Computational complexity and computability

Can every bounded-degree local Hamiltonian with unknown interaction support be learned efficiently from copies of its Gibbs state at any fixed inverse temperature?

• Quantum Metrology
• Quantum Algorithm
• Quantum estimation
• Computational complexity and computability
• Quantum thermodynamics

Does a polynomial-length random walk generated by ordinary two-qubit gates form a pseudorandom-unitary ensemble?

• Quantum Cryptography
• Quantum Algorithm
• Quantum circuit complexity
• Computational complexity and computability

Does the Montanaro–Osborne \(L^2\) quantum KKL inequality hold for every Boolean quantum observable?

• Quantum Algorithm
• Computational complexity and computability
• Matrix and entropy inequalities

Do private-architecture Hamiltonian phase states yield a one-way state generator for explicit polynomial parameters?

• Quantum Cryptography
• Computational complexity and computability
• Quantum state preparation

Can pseudorandom-unitary security scale independently of Hilbert-space dimension while construction uses only polynomially many oracle queries?

• Quantum Cryptography
• Computational complexity and computability
• Quantum circuit complexity

Must every bounded low-degree real polynomial on the Boolean cube with non-negligible variance have a variable of inverse-polynomial influence?

• Quantum Algorithm
• Computational complexity and computability

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

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 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

For each fixed degree bound \(d\geq2\), is there a deterministic polynomial-time algorithm that computes the Clifford-hierarchy level of an \(n\)-qubit permutation gate from degree-at-most-\(d\) algebraic normal forms of the permutation and its inverse, or reports…

• Quantum Algorithm
• Clifford hierarchy
• Computational complexity and computability

Does Geelen’s simulation conjecture hold for every nonempty proper class \(\mathcal C\subsetneq\mathcal G_{\mathrm{fin}}\) of finite simple graphs that is closed under isomorphism, local complementation, and vertex deletion?

• Quantum Algorithm
• Computational complexity and computability

Does there exist an absolute constant \(C>0\) and a deterministic algorithm that, for each integer \(k\geq2\) supplied in unary, runs in time \(k^{O(1)}\) and outputs a \(k\)-vertex-minor-universal graph with at most \(Ck^2\) vertices?

• Quantum Resource Theory
• Quantum Algorithm
• Quantum state preparation
• Resource conversion
• Computational complexity and computability

Is the following Gaussian permanent estimation task \(\#\mathrm P\)-hard under randomized polynomial-time oracle reductions?

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

Do independent complex Gaussian hafnians satisfy a polynomial lower-tail bound at their root-mean-square scale?

• Quantum Algorithm
• Boson sampling
• Computational complexity and computability

Is additive estimation of squared complex Gaussian hafnians \(\#\mathrm P\)-hard under randomized polynomial-time oracle reductions?

• Quantum Algorithm
• Boson sampling
• Computational complexity and computability

For every fixed rational transmission \(0<\eta<1\), is boson sampling with independent photon loss classically samplable in fully polynomial time?

• Quantum Algorithm
• Boson sampling
• Computational complexity and computability

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

• Quantum Algorithm
• Computational complexity and computability

What is the tight precision dependence of worst-case query complexity for low-energy simulation in the regime (2)?

• Quantum Algorithm
• Hamiltonian simulation
• Computational complexity and computability

Can one quantum linear-system algorithm attain both query bounds in (2) simultaneously?

• Quantum Algorithm
• Quantum linear algebra
• Computational complexity and computability

Does a deterministic classical algorithm running in \(n^{O(1)}\) time decide local-unitary equivalence of arbitrary graph states on \(n\) labelled qubits?

• Quantum Algorithm
• Quantum Resource Theory
• Local unitary equivalence
• Computational complexity and computability

Does finding an explicit ENTRANCE-to-EXIT path in the standard Welded Tree oracle problem require exponentially many quantum queries?

• Quantum Algorithm
• Computational complexity and computability

Does the polynomial-factor approximate Shortest Vector Problem 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 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

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

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

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

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