Menu

Quantum-computing related developments

On this page we post about interesting quantum-computing related research and news which we are following.

How many qubits are needed for quantum computational supremacy?

How many qubits are needed for quantum computational supremacy?

Quantum Advantage

Quantum computational supremacy (QCS) arguments have been provided to demonstrate that quantum computers will soon outperform classical computers in a variety of algorithms. However, in order to truly prove supremacy, several strict measures need to be taken: an appropriate algorithm must be selected, a quantum device to run the algorithm must be designed, the ability to verify the results of the calculations must be considered and a complexity theory that supports the claim that a classical computer would be unable to run such an algorithm should be provided. Quantum circuits running on quantum computing chips that are currently experimentally realized might still be able to be simulated in highly parallelized state-of-the-art classical supercomputers, therefore one can only make conjectures about QCS at the moment. Typically, classical simulation of certain families of quantum circuits require scaling that is worse than any polynomial in the size of the circuit, which prevents us from calculating exactly the number of qubits these quantum circuits must have for their classical simulation to be intractable on modern classical supercomputers.

In this paper, three refined fine-grained conjectures about quantum supremacy are provided and it is calculated that 208 qubits and 500 gates for Instantaneous Quantum Polynomial-Time (IQP) circuits, 420 qubits and 500 constraints for Approximate Optimization Algorithm (QAOA) circuits and 98 photons and 500 optical elements are sufficient. Although noise in current quantum devices cannot be fully approximated, a lower bound on the runtime of all three algorithms for any multiplicative-error classical simulation is provided.

This paper provides a concrete estimation on the number of qubits required for three algorithms that have gained a lot of attention during the NISQ era. While the orginal work stems from 2018,  the number of qubits required has been recalculated in the newest version of this paper, which provides a good indication of how fidelity of quantum chips has been improved in the last two years, as well as the latest understanding in complexity and the on-going evolution in classical competition.

Quantum-hype during COVID-19

Quantum-hype during COVID-19

Quantum Advantage

At Qu&Co we always restrained ourselves from reacting to exaggerated claims about the short-term potential of quantum-computing. Rather we focused on our scientifically rigorous work to advance the field of quantum as we strongly believe in its long-term potential. However, we draw the line at quantum being pushed as a short-term solution for researchers working on COVID, like this WSJ article in which a quantum hardware manufacturer offers free hardware access to researchers studying COVID, stating ‘we have a fairly unique system that could add value’. Although this offer could be a misplaced April-fools joke, we want to stress that, although quantum has strong long-term potential, there is zero chance it will provide any short-term value for COVID research. Therefore, no serious researchers working on the current pandemic should be distracted by this offer. If you are determined to use novel methods to solve today’s combinatorial optimisation problems, perhaps try simulated annealing on a purpose-built classical processor. And of course, if your time horizon is >2 years and you want to work on collaborative quantum-algorithm R&D, without distracting scarce COVID R&D staff, we are here to help. Stay safe and focused!

Scott Aaronson’s quantum supremacy FAQ

Scott Aaronson’s quantum supremacy FAQ

Quantum Advantage

Recently some contributors to a paper describing a quantum-supremacy experiment inadvertently posted an older version of this paper online, which was quickly picked-up by the popular press resulting in a flurry of (in many cases) unfounded claims about the progress of quantum-computing. We believe that it is important for people interested in this topic to inform themselves through reading a balanced opinion from someone who is an expert in this field. Therefore we kindly refer to Scott Aaronson's excellent blogpost on this matter.