Evidence in recent months has made headway in proving the anticipated supremacy of quantum computers over classical computers. Recently, Google"s Sycamore, a 53-qubit quantum computer, achieved "quantum supremacy" after it was able to perform a calculation in three minutes and 20 seconds that would have taken the most advanced classical computers today over 10,000 years to work out.
Now, we have yet another major finding, courtesy of the researchers at Microsoft Quantum, that proves that quantum computers provide significant improvements to the time complexity of computational problems. In a paper titled "Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits", the team of researchers collaborating with Microsoft proved that shallow quantum circuits can solve problems that are unsolvable in the domain of shallow classical unbounded circuits unless exponentially many gates are used.
The team composed of Robin Kothari, a Senior Researcher at Microsoft Quantum, Luke Schaeffer from the University of Waterloo, who also interned at Microsoft Quantum, Adam Bene Watts from the Massachusetts Institute of Technology, and Avishay Tal from the University of California at Berkeley. The team"s findings were presented by Luke Schaeffer at the largest quantum computing conference in the world—the Annual Conference on Quantum Information Processing (QIP), and can be observed in the video below.
To understand the team"s findings better, we first need some background on quantum computing in general. Unlike traditional computers that work on bits that work on two states, 0 and 1, quantum computers work on qubits which can be in a quantum superposition of two states at any given instant. For quantum computers to perform as needed, we have to apply certain operations to them with the help of quantum gates. For simplicity, think of these as ordinary logic gates like AND, OR, NOT.
Combinations of ordinary logic gates create classical circuits while combinations of quantum gates create quantum circuits. A special type of quantum circuit, the shallow quantum circuit, had previously been proven to be superior to shallow classical bounded circuits after the former was able to solve a problem unsolvable by the latter.
In the latest research, shallow quantum circuits were sized up against the superior rendition of classical circuits, the shallow unbounded circuit. The team proved that:
...shallow quantum circuits can solve problems that cannot be solved by shallow classical unbounded circuits, unless they use exponentially many gates.
The new advancement, Microsoft hopes will inspire others to venture into the realm of quantum computers and find solutions to real-world problems with their help. For more information on the specifics of the research and quantum circuits in general, you can refer to the blog post. You can also study the paper where the team published its findings here.