Gates, Circuits And What Quantum Computers Will And Will Not Be Good For

Quantum computing is often described as if it will make every computer faster. It will not. A quantum computer is a specialised machine with a different instruction set, and it only beats a classical computer on problems whose structure suits that instruction set. Knowing which problems those are is the most useful thing a non-specialist can learn about the field.

This article explains how quantum programs are put together from gates and circuits, then walks through the problems where a speed-up is known, the ones where it is modest and the large class of work where quantum offers nothing. It assumes you have read the articles on qubits and interference.

From Logic Gates To Quantum Gates

Classical computers are built from logic gates such as AND, OR and NOT. An AND gate takes two bits in and gives one bit out. That loses information: if the output is 0, you cannot tell whether the inputs were 00, 01 or 10. Most classical logic throws information away in this manner, and nobody minds.

Quantum gates work differently. Each gate is a mathematical operation on the amplitudes of the qubits, and the rules of quantum mechanics require it to be what mathematicians call unitary. A unitary operation always has an exact inverse, so every quantum gate can be undone and no information is lost along the way.¹ Common single-qubit examples include the Hadamard gate, which creates an equal superposition from a plain 0 or 1, and the T gate, which shifts the phase of the 1 part of a qubit’s state.¹ The phase is a property of an amplitude that decides how it combines with others during interference; changing it does not alter the odds of reading 0 or 1 straight away, but it changes what later gates produce. The best-known two-qubit gate is CNOT (controlled-NOT), which flips a target qubit when a control qubit is 1.²

A quantum program is a circuit: a sequence of these gates applied to a register of qubits, followed by measurement. In practice, a circuit is run many times, because each run gives one random sample and the answer is read from the pattern across runs. Every quantum algorithm you may have heard of, including Shor’s and Grover’s, is written in this circuit model.

Where A Large Speed-Up Is Known

The clearest case is Shor’s algorithm. In 1994 Peter Shor showed that a quantum computer could factor large integers and compute discrete logarithms in a number of steps that grows only polynomially with the size of the number, meaning the work rises like a fixed power of the number of digits instead of exploding exponentially.³ The best known classical methods are far slower. Those two problems are exactly what makes RSA and elliptic curve cryptography hard to break, so a large, error-corrected quantum computer running Shor’s algorithm would break them.

How large is large is an active research question. In May 2025 Craig Gidney of Google estimated, in a preprint, that 2048-bit RSA could be factored in under a week by a machine with fewer than a million noisy qubits, down from his 2019 estimate of 20 million.⁴ Preprints in 2026 have gone lower still, to under 100,000 physical qubits for one design built on a different family of error-correcting codes, at the cost of a run of about a month.⁵ No machine of that size exists, and the Quantum Threat section explains what the estimate means for security planning.

The second promising area is simulating nature itself. Molecules and materials obey quantum mechanics, and describing them exactly on a classical computer becomes rapidly harder as they grow. NIST’s explainer names the simulation of molecules for drug discovery and materials science among the main hoped-for uses of quantum computers.⁶ Google’s October 2025 experiment with UC Berkeley, which used its quantum hardware alongside nuclear magnetic resonance measurements to learn about molecular structure, is an early step in that direction. Google states plainly that this molecular demonstration is not yet beyond what classical computers can do.⁷

Where The Speed-Up Is Modest Or Unknown

Grover’s algorithm searches an unstructured list of N items in roughly the square root of N steps, where a classical search needs about N.⁸ That is a real gain, but it is quadratic, not exponential. Searching a million items drops to around a thousand steps. Scott Aaronson describes such a speed-up as turning an exponential cost into “a smaller exponential”, not into an easy problem.⁹

The same caution applies to the NP-complete problems. These are the hardest problems in NP, the class of problems whose proposed answers are quick to check, and they include many scheduling and routing tasks. No efficient quantum algorithm for them is known. Aaronson argues that any such algorithm would have to exploit the structure of these problems in ways far beyond current techniques, since treating them as a blind search gives only Grover’s modest gain.⁹ Optimisation is often listed as a quantum use case, and NIST includes it,⁶ but for most practical optimisation problems the size of any quantum advantage is still an open research question.

What Quantum Computers Will Not Do

Most computing is moving and transforming ordinary data: serving web pages, running databases, processing payments, editing documents. None of the algorithms described above applies to them, because these tasks lack the kind of mathematical structure that interference can exploit. NIST’s explainer says quantum computers will not replace classical ones but work alongside them, and notes that many experts expect them to live in computing centres, national laboratories and universities rather than on desks.⁶

For security teams this narrowness cuts both ways. It means quantum computing is no general threat to all of IT. It also means the one area where the speed-up is dramatic, factoring and discrete logarithms, happens to sit underneath almost all of today’s public-key cryptography. The replacement algorithms are covered in Post-Quantum Cryptography.