quantum

A Quick Note on Quantum Computers and NP-Hard Problems

In the early days of quantum computing, Charles H. Bennett, Ethan Bernstein, Gilles Brassard and Umesh Vazirani showed that a quantum computer needs to make exponential queries (specifically, $$O(2^{\frac{n}{2}})$$ which Grover’s algorithm achieves) […]

Two Quasi-Non-Trivial Questions in Quantum Complexity


Question 1: Can you always parallelize the quantum part of a quantum computation; more precisely, is there even a relativised world where $$\BPP^{\BQNC} \neq \BQP$$? […]