Aram Harrow

Aram Harrowaram

May 17 2018 14:08 UTC
May 17 2018 12:53 UTC
May 17 2018 12:52 UTC
May 16 2018 02:06 UTC
Aram Harrow scited Entanglement Breaking Rank
May 16 2018 02:05 UTC
May 15 2018 02:00 UTC
Quantum computational supremacy arguments, which describe a way for a quantum computer to perform a task that cannot also be done by a classical computer, require some sort of computational assumption related to the limitations of classical computation. One common assumption is that the polynomial hierarchy (PH) does not collapse, a stronger version of the statement that P $\neq$ NP, which leads to the conclusion that any classical simulation of certain families of quantum circuits requires more than polynomial time in the size of the circuits. However, the asymptotic nature of this conclusion prevents us from calculating exactly how many qubits these quantum circuits must have for their classical simulation to be intractable on modern classical supercomputers. We refine these quantum computational supremacy arguments and perform such a calculation by imposing a fine-grained version of the non-collapse assumption, which we argue is still plausible. Under the fine-grained assumption, we conclude that Instantaneous Quantum Polynomial-Time (IQP) circuits with 90 qubits, Quantum Approximate Optimization Algorithm (QAOA) circuits with 180 qubits, or boson sampling circuits (i.e. linear optical networks) with 90 photons, are large enough for the task of producing samples from their output distributions up to constant multiplicative error to be intractable on current technology.
May 11 2018 13:38 UTC
May 09 2018 13:07 UTC
May 07 2018 18:41 UTC
May 07 2018 18:40 UTC
May 07 2018 18:40 UTC
May 04 2018 17:45 UTC