Quantum Algorithm

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

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

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 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 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 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 Gaussian permanent estimation task \(\#\mathrm P\)-hard under randomized polynomial-time oracle 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 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

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

Is every two-qudit gate in every level \(k\geq4\) of the Clifford hierarchy semi-Clifford when the local dimension is an odd prime?

• Quantum Algorithm
• Clifford hierarchy

Does every fixed non-Gaussian polynomial Hamiltonian become universal when all Gaussian controls are available?

• Quantum Algorithm
• Quantum circuit complexity
• Hamiltonian simulation

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

Can the exact quantum Fourier transform on \(n\) qubits be implemented with \(O(n)\) one- and two-qubit gates?

• Quantum Algorithm
• Quantum circuit complexity

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

Do normalized one-dimensional Chen–Kastoryano–Gilyén Gibbs samplers have a positive modified log-Sobolev constant uniformly in system size at every fixed finite temperature?

• Quantum Resource Theory
• Quantum Algorithm
• Quantum thermodynamics
• Quantum state preparation
• Quantum relative entropy

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

Is the exact Haar-mixing spectral gap of uniformly random Pauli rotations equal to \(2^n(2^n-3)/(8(4^n-1))\) for every \(n\geq4\)?

• Quantum Algorithm
• Random circuit sampling
• Quantum circuit complexity

What is the minimax copy complexity of identity testing two unknown \(k\)-local Gibbs states using only measurements on individual copies?

• Quantum Metrology
• Quantum Algorithm
• Quantum hypothesis testing
• One-shot and finite-blocklength bounds
• Quantum thermodynamics

What is the exact CNOT-count and depth frontier for ancilla-free Clifford preparation of the logical zero state of the \([[23,1,7]]_2\) quantum Golay code?

• Quantum Error Correction
• Quantum Algorithm
• Quantum coding theory
• Quantum state preparation
• Quantum circuit complexity

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

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

What is the smallest number of qubits on which the third level of the Clifford hierarchy contains a gate that is not semi-Clifford?

• Quantum Algorithm
• Clifford hierarchy

Does some family of asymptotically good qubit CSS LDPC codes admit unitary encoding circuits with linearly many gates and logarithmic depth?

• Quantum Error Correction
• Quantum Algorithm
• Quantum LDPC codes
• Quantum circuit complexity

What is the highest Clifford-hierarchy level that a controlled gate can reach when its target lies in a given level \(k\geq3\) and has a given Pauli periodicity, and is that level bounded independently of the number of target qubits?

• Quantum Algorithm
• Clifford hierarchy

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

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

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