In classical computing, a single bit can only encode a 1 or 0 value. Qubits, the equivalent of a bit in quantum computing, can encode more information. How these link together determines how the circuit delivers the various quantum computations. The research paper shows that these can be linked in two dimensions and at a constant “depth” for any number of inputs. The “depth” indicates how many connections each computation traverses.
“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.
Our work gives an unconditional proof of a computational quantum advantage and simultaneously pinpoints its origin: It is a consequence of quantum nonlocality. The proposed quantum algorithm is a suitable candidate for near-future experimental realizations, as it requires only constant-depth quantum circuits with nearest-neighbour gates on a two-dimensional grid of qubits (quantum bits).” – Sergey Bravyi, David Gosset and Robert König.
In the case of the theoretical problem, the researchers showed that it was possible to create a fixed-size circuit which could deal with any number of potential inputs and that the computation would take a fixed amount of time. Compared with classical computing, there would be an increase in circuit depth, and deeper circuits also take longer to calculate a response.
A mesh of qubits configured in less than three dimensions keeps things simple. Similarly, having short depth networks to solve the problem is important. This is because currently, qubits are not the most stable of things. Qubits can only support a number of operations before they lose coherence (the network becomes unstable). Individual qubits are also subject to an error rate. Both factors limit current quantum computers performance.
IBM’s research platform is a 20-qubit environment. This is available via their Network Q Experience to other researchers. (You can hear the sounds of a quantum computer in a video here). They also demonstrated a 50 qubit system last year.