{"id":3417,"date":"2019-10-16T08:00:28","date_gmt":"2019-10-16T15:00:28","guid":{"rendered":""},"modified":"2024-10-10T09:11:11","modified_gmt":"2024-10-10T16:11:11","slug":"microsoft-quantum-proves-shallow-quantum-circuits-provide-an-exponential-advantage","status":"publish","type":"post","link":"https:\/\/azure.microsoft.com\/en-us\/blog\/quantum\/2019\/10\/16\/microsoft-quantum-proves-shallow-quantum-circuits-provide-an-exponential-advantage\/","title":{"rendered":"Microsoft Quantum and collaborators prove shallow quantum circuits provide an exponential advantage"},"content":{"rendered":"

We know that Shor\u2019s algorithm can factor integers on a quantum computer exponentially faster than any known classical algorithm, and that there are problems, such as the simulation of physical systems as posed by Richard Feynman in the 1980s, that quantum computers can solve that would take classical computers more than the lifetime of the universe to calculate.<\/p>\n

But can we prove<\/em><\/strong> that a quantum computer can solve a problem exponentially faster than a classical computer?<\/p>\n

In 2018, work by Sergey Bravyi (IBM Research), David Gosset (University of Waterloo), and Robert Koenig (Technische Universit\u00e4t M\u00fcnchen) described a problem that could be solved by a shallow quantum circuit but provably <\/em>could not be solved by a shallow classical bounded circuit. (More on shallow bounded and unbounded circuits below.)<\/p>\n

The primary question left open in their work was: Can shallow quantum circuits solve a problem that even a shallow classical unbounded<\/em> circuit could not?<\/p>\n

The answer is yes.<\/p>\n

Robin Kothari, a Senior Researcher at Microsoft Quantum, Luke Schaeffer (University of Waterloo and former intern at Microsoft Quantum), and collaborators Adam Bene Watts (MIT) and Avishay Tal (UC Berkeley) recently showed that: shallow quantum circuits can solve problems that cannot be solved by shallow classical unbounded circuits, unless they use exponentially many gates<\/em>.<\/strong><\/p>\n

These breakthrough results were presented by Luke Schaeffer at the Annual Conference on Quantum Information Processing (QIP), the largest quantum computing conference in the world, and at the Annual ACM SIGACT Symposium on Theory of Computing (STOC). Their findings are outlined here<\/a>.<\/p>\n

Motivated by the constraints of near-term quantum computing hardware, we compared the power of today\u2019s depth-restricted quantum computers with depth-restricted classical computers.<\/p>\n

Using today\u2019s quantum computing hardware, we can study the power of quantum computers that run \u201cshallow\u201d quantum algorithms, whose run time is very small compared to the size of the problem being solved.<\/p>\n

But first, some quantum basics.<\/p>\n

An idealized quantum computer consists of some number of quantum bits, or \u201cqubits.\u201d There is a small set of quantum operations called quantum gates<\/em><\/strong> that act on two qubits at a time and can be applied to any pair of qubits. In a single time step, we allow these gates to be applied to pairs of qubits that do not overlap. For example, in one time step we can apply a quantum gate to qubits 1 and 2, and apply a potentially different quantum gate to qubits 3 and 4, and yet another quantum gate to qubits 5 and 6.<\/p>\n