Quantum circuit complexity

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

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

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