What Quantum Computers Can and Can't Do

“A quantum computer tries every answer at once.” It’s the most repeated sentence in the field, and it is misleading. If it were true, quantum computers would be fast at everything. They aren’t. They are fast at a few carefully structured problems, and understanding why tells you a great deal about what quantum computing really is.

Qubits and superposition

A classical bit is 0 or 1. A qubit is described by two complex numbers, called amplitudes, one for each outcome. A register of n qubits needs 2 to the power of n amplitudes to describe, which is why simulating even modest quantum systems overwhelms classical memory.

But there is a catch that the “tries everything” slogan hides. When you measure, you get just n classical bits, chosen at random with probabilities given by the squared magnitudes of the amplitudes. All that exponentially large state collapses into a single answer.

The real resource: interference

Amplitudes can be positive, negative or complex, so they can cancel as well as add. A quantum algorithm is a choreography that arranges for the amplitudes of wrong answers to cancel and those of right answers to reinforce, so that measuring at the end is likely to give a correct result.

That is a strong constraint. You can’t simply load in all the possibilities and read off the best one; you need a problem with enough structure that interference can be steered toward the answer.

Where quantum algorithms win

Factoring: Shor’s algorithm

In 1994 Peter Shor showed that a quantum computer can factor large integers in polynomial time, where the best known classical algorithms are super-polynomial. The trick is to turn factoring into period finding, which the quantum Fourier transform handles efficiently through interference. This is why quantum computers threaten widely used public-key cryptography such as RSA, and why the industry is migrating to post-quantum cryptography.

Unstructured search: Grover’s algorithm

Searching N unsorted items takes about N steps classically. Grover’s algorithm needs roughly the square root of N. That is a real but modest quadratic speedup, and it is provably the best possible for unstructured search.

Simulating nature

Richard Feynman’s original motivation: simulating quantum systems, such as molecules and materials, is naturally suited to quantum hardware. This may prove the most valuable application, in chemistry and materials science.

# The classical cost of storing an n-qubit state vector
for n in (10, 30, 50):
    amplitudes = 2 ** n
    gigabytes = amplitudes * 16 / 1e9     # 16 bytes per complex number
    print(f"{n} qubits -> {gigabytes:,.1f} GB")

What they won’t do

• They won’t speed up everything. For most everyday tasks, classical computers remain faster and far cheaper.
• They are not known to solve NP-complete problems efficiently, and most researchers believe they can’t.
• They won’t make your laptop faster. Quantum machines are expected to be specialised accelerators.

The engineering challenge

Qubits are fragile. Stray interaction with the environment destroys their quantum behaviour, a process called decoherence, and gates are imperfect. Useful algorithms need far more reliable qubits than any raw hardware provides, so the plan is quantum error correction: encode one reliable logical qubit across many physical ones, and keep correcting.

Quantum advantage claims

Several experiments have claimed to outperform classical supercomputers on contrived tasks. These claims are routinely challenged when improved classical algorithms close the gap. Healthy skepticism is warranted: the bar that matters is a useful problem solved faster than the best classical method.

The honest summary

Quantum computing is real science with a short list of proven, important speedups and an engineering road still being built. The sensible position sits between hype and dismissal: it will matter a great deal for specific problems, and be irrelevant for most others.