Quantum Computing Now Proven to be Faster than Classical Computers

An international team of researchers has definitively proven that quantum computers can hold a significant computational advantage over classical semiconductor-based computers.

Although quantum computing elements have been available in D-Wave Systems‘ series of computers for over a decade, there has been a great deal of controversy over whether or not the performance increases demonstrated by these computers are actually due to quantum processes, and not simply efficiencies hidden in the computer’s code or hardware.

This new study made use of a specially-designed quantum circuit that was able to solve an algebraic math problem that would have been impossible for a computer based on classical architecture to crunch, given the same parameters.

"Our work shows that quantum circuits are computationally more powerful than classical ones of the same structure," explains Robert König, a complexity theorist at the Technical University of Munich, and the study’s lead author. "We are not saying that the problem cannot be solved classically. It can, though this requires more resources."

Classical computers measure their data in binary digits — better known as "bits" — that are physically represented by the microscopic switches on a computer chip: the switch is either on or off, signaling a one or zero in computer code. Quantum computers rely instead on quantum bits, more typically referred to as "qubits", that can not only be in a state of either on or off, but due to the effect of quantum superposition can also be simultaneously on AND off, theoretically allowing individual qubits to operate much faster and more efficiently than their classical counterparts.

Although this makes it sound like quantum circuits should be able to steamroll our trusty solid-state computers, the computational power of quantum devices has been limited by the comparative vulnerability of the states of the qubits: the more qubits that are included on a quantum chip, the more likely the individual qubits are to loose coherence and produce errors while performing their computational tasks.

This produces a catch-22, where adding more qubits to a circuit decreases the amount of operations that one can safely run on that circuit. To address this, researchers have traditionally kept the number of operations each circuit can crunch at any given time low, to limit the amount of errors that can creep into each operation. The effect means that increasing the power of a quantum computer also has the effect of slowing it down, a problem that makes comparing the speed of quantum computers to traditional ones problematic.

König’s team took a different approach, instead running several simple quantum circuits, referred to as having a "shallow" depth of the number of operations it can perform, running in parallel, that took advantage of the effect of quantum nonlocality to enhance the computational power of the entire assembly. This effectively enabled the assembly to run as a single, more powerful unit due to Einstein’s so-called "spooky action at a distance", enabling it to solve an algebra problem that, due to the limited number of operations each individual circuit was forced to operate under, would have been mathematically impossible for a classical computer to have performed.

"We show that parallel quantum algorithms running in a constant time period are strictly more powerful than their classical counterparts; they are provably better at solving certain linear algebra problems associated with binary quadratic forms," the study asserts. "Our work gives an unconditional proof of a computational quantum advantage and simultaneously pinpoints its origin: It is a consequence of quantum nonlocality."