Quantum advantage is when quantum computers can outperform classical computers.One of the first largescale demonstrations of quantum advantage was recently done by Google running random multi-qubit quantum circuits.While Google's quantum computer took 200 seconds, calculations show that the then-fastest classical supercomputer would have taken 10000 years.Since then, different groups have claimed quantum advantage through other quantum systems.This paper will cover why quantum computers can be faster than classical computers by covering the primary differences between classical computing and quantum computing.Then, we will investigate the Deutsch-Jozsa quantum algorithm and Google's claim of quantum advantage.We will review current research regarding "quantum advantage," tying these events to the use cases covered.Additionally, different quantum algorithms that are theoretically faster than any current quantum algorithms will be analyzed, and we will delve into why this is the case.The covered examples will show methods used to improve quantum computers to provide a significant time difference to achieve a quantum advantage.After that, we make predictions concerning two critical quantum hardware limitations.Finally, we will investigate what the future of quantum advantage entails and some future cases of quantum advantage.
We present a classical algorithm that, for any 3D geometrically-local, constant-depth quantum circuit
C, and any bit string
x∈{0,1}n, can compute the quantity
∣∣2 to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is
#P-hard to compute this same quantity to within
2−n2 additive error [Mov20]. The previous best known algorithm for this problem used
O(2n1/3poly(1/ϵ)) time to compute probabilities to within additive error
ϵ [BGM20]. Notably, the [BGM20] paper included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach:
Our algorithm has a Divide-and-Conquer structure, constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings, each creating a 3D-local circuit on at most half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from the entanglement that may exist between the different circuit pieces produced this way.
We present a classical algorithm that, for any 3D geometrically-local, polylogarithmic-depth quantum circuit
C, and any bit string
x∈{0,1}n, can compute the quantity
∣⟨x∣C∣0⊗n⟩∣2to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is
#P-hard to compute this same quantity to within
2−n2additive error [1], [2], and worst-case hardness results for this task date back to [3]. The previous best known algorithm for this problem used
O(2n1/3poly(1/ϵ))time to compute probabilities to within additive error
ϵ[4]. Notably, that paper, [4], included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach: constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings. To our knowledge this is the first use of the block-encoding technique in a purely classical algorithm. Our algorithm has a Divide-and-Conquer structure, demonstrating how to approximate the desired quantity via several instantiations of the same problem type, each involving 3D-local circuits on about half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted sum of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from entanglement that may exist between the different circuit “pieces” produced this way. We believe that the division step, which makes a novel use of block-encodings [5], together with an Inclusion-Exclusion argument to reduce error in each recursive approximation, may be of independent interest.11The full version of this paper is available at arXiv:2012.05460. We refer the reader to the full text for proofs of all Lemmas and Theorems.