Quantum Computing Relatable — Part 4

After the first three parts, the promise should sound more specific.

Quantum computers are not replacements for laptops. They are not automatically faster at every calculation. Their opportunity comes from a smaller set of algorithms that can use quantum states, interference and entanglement to expose structure that is difficult to reach classically.

The hard question is not whether quantum mechanics is powerful. It is whether we can build a reliable machine and find a useful problem for which the complete workflow beats the best classical alternative.

Factoring and cryptography

Shor's algorithm is the clearest famous example.

Multiplying two known prime numbers is easy. Recovering those primes from a sufficiently large product is believed to be difficult for classical computers. Many public-key cryptography systems are built around related mathematical problems.

Shor's algorithm connects factoring to finding a repeating pattern in a modular function. Its quantum part uses interference to extract information about that period. Classical calculations then use the result to recover possible factors.

The algorithm is theoretically important, but running it against modern cryptographic keys requires a large fault-tolerant machine. A small demonstration that factors 15 does not mean that today's hardware can break internet encryption.

The future risk is still serious enough that migration has started. Post-quantum cryptography replaces vulnerable constructions with algorithms intended to resist both classical and quantum attacks. NIST recommends beginning that transition because encrypted data can be collected now and decrypted later if the protection eventually fails. NIST explains that “harvest now, decrypt later” risk here.

Chemistry and materials

Nature is quantum mechanical. Electrons in a molecule do not become classical just because we want to simulate them on a computer.

Classical methods can approximate molecular behaviour, but the state space grows quickly as the system becomes more complicated. A quantum processor can represent some of that structure more naturally. In practice, the quantum and classical computers would work together: the quantum processor prepares and samples states, while the classical computer chooses parameters, processes measurements and estimates energies.

This is one of the most credible long-term application areas. It is also a difficult benchmark. Better chemistry predictions require accurate circuits, many measurements and enough error correction to distinguish a useful signal from hardware noise. IBM describes a hybrid approach to molecular simulation.

Search and optimization

Grover's algorithm gives a quadratic speedup for a particular abstract search problem. That does not mean that every database query, route-planning task or scheduling problem receives the same benefit.

Optimization is even more complicated. There are many proposed quantum optimization algorithms, but a proposal is not the same as a demonstrated advantage over a strong classical solver. A fair comparison has to include the cost of loading the data, translating the problem into a circuit, running the circuit many times and correcting errors.

The same caution applies to machine learning. A quantum circuit can be part of a learning system, but that does not make the whole system faster or more intelligent by default.

And what about NP and SAT?

SAT asks whether there is an assignment of variables that satisfies a collection of logical clauses. It is a useful problem because many planning, verification and scheduling tasks can be translated into it.

A quantum computer can encode candidate assignments and evaluate clauses. That is not the same as having a fast general solution to SAT. No established result says that quantum computers efficiently solve all NP-complete problems.

There may be useful speedups for restricted instances, heuristics or special structure. Those are worth studying. They are also very different from the claim that quantum computing dissolves computational complexity.

Behind the hype

When I see a quantum-computing headline now, I want to ask four questions:

• What exact problem is being solved?
• What is the best classical baseline?
• Is the claimed advantage theoretical, simulated, or measured on hardware?
• Are the resources logical qubits, physical qubits, circuit depth, runtime, or something else?

A new record for a qubit count can be a meaningful engineering result without being a useful application. A small experiment can demonstrate a quantum effect without beating a classical computer. A theoretical algorithm can change cryptography without being runnable on current hardware.

These statements can all be true at the same time. The hype begins when they are collapsed into one sentence: “Quantum computers are here and they will solve everything.”

One recent technical example shows why the details matter. A paper on the quantum risks to elliptic-curve cryptocurrencies estimates the resources future attacks might require under specified hardware assumptions. It is a serious warning about migration timelines, not evidence that somebody has already broken a blockchain. Read the paper here.

I still have not solved my own problem. I can now separate a qubit from a covered coin, an algorithm from a diagram, and a hardware count from a useful logical computation. That is progress, but it is not understanding the whole field.

The next articles will go deeper into the topics that are easiest to flatten into slogans: entanglement, quantum gates, and whether a carefully chosen SAT instance can reveal anything about quantum advantage.