The Complexity of Sampling from a Weak Quantum Computer
Saeed Mehraban
MIT CSAIL
Add to Calendar
2019-05-28 10:00:00
2019-05-28 11:00:00
America/New_York
The Complexity of Sampling from a Weak Quantum Computer
Abstract: This is an exciting time for quantum computing. Over the next few years, intermediate-scale quantum computers with ~50-100 qubits are expected to become practical. These computers are too small to do error correction and they may not even capture the full power of a universal quantum computer. A major theoretical challenge is to understand the capabilities and limitations of these devices. In order to approach this challenge, quantum supremacy experiments have been proposed as a near-term milestone. The objective of quantum supremacy is to find computational problems that are feasible on a small-scale quantum computer but are hard to simulate classically. Even though a quantum supremacy experiment may not have practical applications, achieving it will demonstrate that quantum computers can outperform classical ones on, at least, artificially designed computational problems. Among other proposals, over the recent years, two sampling based quantum supremacy experiments have been proposed:(1) The first one is based on sampling from the output of a random circuit applied to a square grid of qubits. The Google quantum AI group is planning to implement this task on a processor composed of a few (~50-100) superconducting qubits. In order to argue that this sampling task is hard, building on previous works of Aaronson, Arkhipov, and others, they conjectured that the output distribution of a low-depth (scaling asymptotically as the square root of the number of qubits) circuit is anti-concentrated meaning that it has nearly maximal entropy. This is known as the “anti-concentration” conjecture.(2) The second proposal, known as Boson Sampling (Aaronson Arkhipov ’10), is based on linear optical experiments. A baseline conjecture of Boson Sampling is that it is #P-hard to approximate the permanent of a Gaussian matrix with zero mean and unit variance with high probability. This is known as the permanent of Gaussians conjecture.The first part of this thesis proves the anti-concentration conjecture for random quantum circuits. The proof is an immediate consequence of our main result which settles a conjecture of Brandão-Harrow-Horodecki ’12 that short-depth random circuits are pseudo-random. These pseudo-random quantum processes have many applications in algorithms, communication, cryptography as well as theoretical physics e.g. the so-called black hole information problem. This result is based on joint work with Aram Harrow (QIP 2018).The second part of this thesis makes progress towards the permanent of Gaussians conjecture and shows that the permanent of Gaussian matrices can indeed be approximated in quasi-polynomial time with high probability if instead of zero mean one considers a nonzero but vanishing mean (~1/polyloglog in the size of the matrix). This result finds, to the best of our knowledge, the first example of a natural counting problem that is #P-hard to compute exactly on average and #P-hard to approximate in the worst case but becomes easy only when approximation and average case are combined. This result is based on joint work with Lior Eldar (FOCS 2018).Thesis Committee: Scott Aaronson, Ryan Williams, Aram Harrow.
32-G575
Belfer
sarah_donahue@hks.harvard.edu
