Topic
Quantum circuit complexity
13 records: 12 unsolved, 1 solved. Filter the catalog by this topic →
-
Linear-size exact quantum Fourier transform
Can the exact quantum Fourier transform on \(n\) qubits be implemented with \(O(n)\) one- and two-qubit gates?
Unsolved -
Subquadratic total quantum gate complexity of RSA factoring
Can every balanced RSA semiprime be factored with polynomially subquadratic total quantum gate complexity?
Unsolved -
Sublinear logical quantum space for RSA factoring
Can every balanced RSA semiprime be factored in polynomial time using sublinear logical quantum space?
Unsolved -
Pseudorandom unitaries from ordinary random two-qubit circuits
Does a polynomial-length random walk generated by ordinary two-qubit gates form a pseudorandom-unitary ensemble?
Unsolved -
Exact spectral gap of random Pauli rotations
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\)?
Unsolved -
CNOT-count and depth frontier for quantum Golay state preparation
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?
Unsolved -
Scalable pseudorandom unitaries with an independent security parameter
Can pseudorandom-unitary security scale independently of Hilbert-space dimension while construction uses only polynomially many oracle queries?
Unsolved -
Asymptotic growth of the stabilizer rank of T-state tensor powers
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?
Unsolved -
Linear-size logarithmic-depth encoders for good quantum LDPC codes
Does some family of asymptotically good qubit CSS LDPC codes admit unitary encoding circuits with linearly many gates and logarithmic depth?
Unsolved -
Universality of arbitrary self-adjoint polynomial Hamiltonians
Can every physical bosonic unitary be approximated by a single self-adjoint polynomial Hamiltonian evolution at any finite input energy?
Solved -
Universality of every fixed non-Gaussian polynomial generator
Does every fixed non-Gaussian polynomial Hamiltonian become universal when all Gaussian controls are available?
Unsolved -
Parity is not in QAC0
Can polynomial-size constant-depth \(\mathsf{QAC}^0\) circuits compute the parity function, or equivalently, is \(\mathrm{PARITY}\notin\mathsf{QAC}^0\)?
Unsolved -
Collective cost of tensor-power state preparation
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.
Unsolved