This Proof Demonstrates a Quantum Advantage, Even for Noisy Quantum Computers
By Ryan F. Mandelbaum, Senior Technical Writer, Qiskit
Among the most important ongoing tasks in the early days of quantum computing is identifying the problems that today’s quantum devices can solve better than classical computers can. A new paper has proven that under the right circumstances, there are situations where even noisy quantum computers prone to unexpected changes in their qubit values can beat a classical computer — on a circuit you can run yourself.
Today’s quantum computers are limited by their errors, by their number of qubits, by which qubits can interact with one another, and by the fact that they can only run circuits with a limited number of discrete steps before they lose their quantum-ness. Two years ago, a team of international researchers including IBM’s Sergey Bravyi proved that quantum effects allowed these limited quantum computers to outperform classical computers for a certain selection of problems, so long as the classical computers were constrained to running constant-depth circuits — circuits with an upper bound to the number of discrete steps they could run. Bravyi’s team has now published a proof of an algorithm where quantum computers hampered by noise, like the ones that exist today, can beat a classical computer running constant-depth circuits.
Why should one get excited about a quantum computer beating a limited classical computer? Well, asking whether or not a quantum computer running shallow-depth circuits can beat any classical algorithm is a little too hard. What if there’s just some classical algorithm we haven’t thought of yet? Plus, such a comparison is sort of like a potato sack race where the classical computer doesn’t need to use a sack — pitting constant-depth quantum circuits against constant-depth classical circuits is perhaps a more appropriate way to demonstrate the advantages that computing with qubits has over computing with classical bits, especially as the number of and quality of qubits in quantum computers increases. This new paper is more of an apples-to-apples comparison between the two different computing methods, and a rigorous proof of quantum bits, even noisy quantum bits, outperforming classical bits in the same race.
Or, in Bravyi’s words: “From the complexity theory perspective, this result constitutes the first rigorous separation between the computational power of noisy constant-depth quantum circuits and noiseless constant-depth classical circuits.”
The researchers tackled the Mermin-Peres magic square game, discussed in 1990 papers by physicists Asher Peres and N. David Mermin. Alice and Bob are shown a three-by-three square. A referee asks Alice to assign 0s and 1s to the three boxes in one of the columns such that there are an odd number of 1s, and asks Bob to do the same for one of the rows such that there are an even number of 1s, all without communicating to one another. They win if they assign the same value to the box where the column and row intersect, and lose otherwise. No guessing-based strategy will let Alice and Bob win more than eight out of nine times, because the overall number of 1s in the grid must be either even or odd — so, if Alice and Bob were to fill the entire grid based on their respective even and odd constraints, one square is guaranteed to be different between their two fills. However, if they’re allowed to generate and share a pair of entangled qubits prior to filling in their column or row, and if they can bring along a portable quantum computer (or perhaps their cell phone accessing a quantum computer on the cloud), they can win the game every time, even if they don’t talk to one another.
You could represent the quantum solution to the magic square game on a quantum circuit as follows in (a). Note that the U and V gate here don’t refer to Qiskit’s general U gates, but classically-controlled gates that take in a pair of bits, denoted by the table in (b):
Here, gamma represents the binary form of column 1, 2, and 3 (01, 10, and 11), while alpha and beta denote the row or column that Alice and Bob choose, respectively. Measuring this circuit produces two x bits for Alice, x1 and x2, and she sets the third bit equal to x1+x2+1 modulo 2. Bob calculates two y bits, y1 and y2, and sets his third bit equal to y1+y2 modulo 2. Alice and Bob use these three bits to fill their column/row, and voila, they’ve won.
For the proof, published this week in Nature Physics, the team produced a more generalized form of the problem to test against the constant-depth classical circuits. You can think of as involving more players in the fun, where two players are Alice and Bob and the rest of the players are tasked with assisting them in entangling their qubits over a longer range.
Why does the quantum computer beat the constrained classical computer? Well, the quantum computer can calculate the answer to this problem with the same number of steps, regardless of the problem size. But according to the proof, if you required the constant-depth classical solution to be right for nine out of ten problem instances, then the amount of time it would take to solve the problem would grow logarithmically with the size of the input. In order to prove that this works for even noisy quantum computers, the researchers model a noisy gate by including a random Pauli gate, that’s the X, Y, and Z gates, that will act with some probability P after each ideal gate. The mathematical proof demonstrates that even a quantum computer including these errors can find the answer to the magic square problem more than 99% of the time if it incorporates an error correction strategy into its solution. The team didn’t attempt to calculate the noisiest possible quantum computer that would win, so “noisy” might still refer to a computer where an error only occurs for one in every 10¹⁰ or even one in every 10¹⁰⁰ gates, Bravyi said. But he expected the noisiest possible winning quantum computer might experience an error for one in every 100 or 1000 gates, or approximately the error rates of today’s quantum devices.
Upcoming generations of quantum computers may actually be able to run this circuit with the help of these error correction strategies, which introduce redundant qubits in order to avoid errors. Some gates require a lot of redundant qubits for error corection, but this algorithm relies solely on the Clifford gates, a group essentially made from combinations of the four Pauli gates (I, X, Y, Z), the controlled Pauli gates, and the Hadamard gate, on which error correction can be implemented with fewer redundant qubits. The proof uses the surface code method of error correction (which probably deserves its own blog entirely), where each qubit is coupled to a few other qubits that prevent its bit value from flipping or its phase from changing. In short, a near-future quantum computer with surface code error correction strategies implemented may successfully solve the magic square problem 99% of the time.
Running the magic square problem isn’t outside the realm of an IBM device with Qiskit, either. Here’s some code for you to try out and modify yourself:
These papers do not represent quantum computers utterly crushing classical computers, nor do they represent algorithms with obvious applications. But think of them as foundation building; each place where scientists unequivocally prove a speedup of a quantum computer over some element of classical computation helps us better understand these devices, and could act as signposts toward quantum applications in the future.
Update 3/19/2021: David Drexlin made some modifications and extended the code written above to display the complete solution on four qubits. Please note that the code above had an issue with gate order that I have since fixed. You can check out David’s version here, alongside some other fun quantum projects hosted by Jan-Rainer Lahmann here.
Trying to find quantum advantages of your own is a great excuse to learn how to program with Qiskit! Learn about the Qiskit Global Summer School and sign up here before July 10th and begin your quantum journey.
