How Does a Quantum Computer Calculate? From Gates to Algorithms
How a Quantum Computer Actually Computes
Classical computers process information using the rules of classical physics, and the logic built on top of those rules is rigid and familiar. Feed a 0 into a NOT gate, and you get a 1 out. Feed in a 1, you get a 0. Simple, one operation, one answer.
Now ask: “what happens if you feed that same NOT gate a qubit that’s in superposition simultaneously 0 and 1?”
The gate flips both at once. The qubit that was leaning toward 0 now leans toward 1, and vice versa . The probabilities swap places, in a single operation, applied to both possibilities simultaneously.
Scale this up, and the effect compounds fast. Feed the same kind of operation two qubits in superposition, and you’re implicitly touching all four possible combinations , 00, 01, 10, 11, in one single pass. Three qubits, eight combinations. Four qubits, sixteen. The pattern doubles with every qubit you add, and critically, the operation itself doesn’t get any slower or more complicated to run. One gate, one pass, no matter how many possibilities are riding along inside the superposition.
This is quantum parallelism, and it’s the core reason quantum computers can, for certain problems, blow past what any classical computer could ever achieve, not by being faster at doing one thing at a time, but by doing an exponential number of things in a single step.
A problem worth throwing this at
Here’s a classic kind of problem where this matters: finding the roots of a function, the values of x where the function equals zero. Some functions are simple enough to solve with algebra directly. But plenty aren’t. For those, there’s no clever formula, the only option is brute force: try one value of x, check it, try the next, check it, and keep going until you land on zero.
Classical computers are extraordinarily good at this kind of brute-force grinding, modern chips run billions of these operations per second, and smarter search strategies can trim down how many guesses you need. But for a sufficiently hard problem, the number of guesses required can be so enormous that even that speed isn’t enough. A problem requiring somewhere in the neighborhood of 10²⁵⁶ operations would take even the fastest supercomputers on Earth something on the order of 10²³⁰ years to brute-force through. For comparison, the universe is about 1.4 x 10¹⁰ years old. That’s not a long wait. That’s a number with no meaningful relationship to “wait.”
Where quantum parallelism changes the math
Now hand that same problem to a quantum computer. Feed in a string of qubits in superposition, and that single string simultaneously represents every possible value of x that string of bits could encode. Run your function-check operation once, and in that one operation the machine checks whether the equation holds true for every one of those values at once.
Here’s the catch, and it’s the same catch we ran into with superposition in article 3: getting that answer doesn’t mean you can just look at it. Measure the system, and it collapses to a superposition of results , the correct answer buried among a huge pile of incorrect ones, like a single marked card lost inside a full shuffled deck.
This is the real heart of quantum algorithm design. In classical computing, an algorithm’s job is to find the answer. In quantum computing, the answer is already sitting there, hidden inside the superposition the moment you run the operation, the algorithm’s job is to pull it out. Specifically, to manipulate the probabilities so that the correct answer becomes overwhelmingly more likely to be the one you get when you finally measure, while the wrong answers get pushed toward vanishing.
Done well, this trick doesn’t just help, it changes the shape of the problem entirely. Instead of needing roughly 2ⁿ operations, a well-designed quantum algorithm might only need something closer to n². That’s not a small speedup. For large enough n, it’s the difference between “impossible” and “solvable.”
Why we don’t have this running on your laptop yet
Two big practical walls stand between this idea and a working machine.
The first is raw qubit count. Solving a real, practical problem in a single pass, the way described above needs roughly as many qubits as there are digits in the number you’re working with. For genuinely useful problems, that means numbers with hundreds of digits, which means processors with hundreds of working qubits at minimum. Factor in the extra qubits needed just to keep the whole system stable, error correction mainly, and the real number balloons into the thousands. Nobody has reliably built a processor at that scale yet.
The second wall is what’s called a quantum oracle, the actual physical component that computes your function, according to the rules of quantum mechanics, in that single operation. We’ve learned how to build oracles for specific, individual problems. What we haven’t figured out is how to build one general-purpose oracle the way a classical processor can run more or less any calculation you throw at it. Right now, every new problem needs its own custom-built oracle. That’s a real, unresolved engineering gap, not a small one.
And one last thing worth flagging before we move on: superposition isn’t the whole story of where quantum computers get their power. Two other properties we’ve already met, entanglement, and a third one we haven’t fully unpacked yet, interference contribute just as much, arguably more.
What Is a Quantum Algorithm?
At its simplest, an algorithm is just a recipe, a sequence of steps that solves a problem, where each step is something a computer can actually carry out.
By that definition, a quantum algorithm is exactly the same thing, just running on a quantum computer instead of a classical one. And here’s a detail that might surprise you: you can, in principle, run any classical algorithm on a quantum computer. A quantum machine doesn’t lose the ability to do ordinary computing.
So what actually earns an algorithm the label “quantum”? Not the hardware it happens to run on, the ingredients it uses. We reserve the term “quantum algorithm” for algorithms where at least one step genuinely depends on something distinctly quantum, superposition, entanglement, or interference rather than just doing classical-style computing on quantum hardware.
Quantum Circuits and Gates
One question comes up more than almost any other: how does a quantum computer actually work, mechanically? It’s a fair question, and it deserves a real answer.
Here’s something that might surprise you: both classical and quantum computers are built out of the same basic idea, gates. A gate is just an instruction that changes the state of some piece of information. Classical gates flip bits around according to fixed rules. Quantum gates do the same job, just to qubits instead and because qubits can hold superposition and entanglement, quantum gates can do things classical gates never could.
Let’s meet a few of the key ones.
The Hadamard gate, the superposition-maker
The first gate worth knowing is the Hadamard gate. Its whole job is to take a qubit sitting in a plain, definite state, a normal 0 and put it into superposition: a 50/50 blend of 0 and 1, with genuinely equal odds of measuring either one.
That’s it. One gate, one operation, and a qubit that was perfectly ordinary a moment ago is now holding two possibilities at once. This is the literal, physical starting point for everything we talked about in the last two sections, superposition isn’t some abstract idea, it’s something you switch on with a single, simple instruction.
The CNOT gate, the entangler
The second gate is where things get properly strange: the CNOT gate (short for “controlled-NOT”). Unlike the Hadamard gate, which works on just one qubit, CNOT needs two qubits to do its job, a “control” qubit and a “target” qubit. Its rule is simple: if the control qubit is a 1, flip the target qubit. If the control qubit is a 0, leave the target alone.
On its own, that sounds almost boring. But apply a Hadamard gate first (putting one qubit into superposition), and then apply CNOT and something remarkable happens. The two qubits become entangled. Measure one, and you instantly know the state of the other, no matter how far apart they are. Just two gates, applied in sequence, and you’ve built one of the most famous objects in all of physics: a Bell state, the exact configuration John Bell used to show that quantum mechanics can’t obey local realism. One of two things has to give: either particles don’t have definite properties until measured, or something is happening faster than light. As we covered last time, physicists overwhelmingly landed on the first option.
It’s worth sitting with that for a second: two of the strangest ideas in this entire series, superposition and entanglement, boil down, mechanically, to just two simple gates applied one after another.
The twist: this still isn’t enough
Here’s where it gets interesting. The Hadamard gate and the CNOT gate both belong to a family of gates called the Clifford group. They feel deeply, unmistakably quantum, they create superposition, they create entanglement. Surely that’s enough to leave classical computers in the dust?
It isn’t. There’s a result called the Gottesman–Knill theorem that proves something almost paradoxical: any circuit built purely out of Clifford-group gates, no matter how much superposition or entanglement it uses can still be efficiently simulated by an ordinary classical computer. All that quantum weirdness, and a classical machine can still keep up.
So what’s actually missing? The answer is something almost embarrassingly small: phase. Specifically, a gate called the T-gate.
The T-gate barely does anything, at first glance. It doesn’t touch probabilities. It doesn’t change what you’d measure directly. All it does is nudge a qubit’s internal phase by a small, precise rotation. That’s the entire operation.
But that tiny nudge changes everything. Once you add T-gates into the mix, quantum states become genuinely, provably harder to compress and track the cost of simulating them classically explodes exponentially, and classical computers lose the ability to keep pace. Add the T-gate to the Clifford group, and you get what’s called universality: the ability to approximate any quantum computation nature allows.
That small, unassuming phase shift is the actual crack in the wall between classical and quantum computing. Superposition and entanglement get all the attention, but it’s phase, quiet, easy to overlook, that’s doing the real work of taking us somewhere a classical computer can never follow.
The Power of Quantum Algorithms
Not everything gets easier with a quantum computer. Problems that are truly unsolvable, the ones mathematicians call undecidable stay unsolvable, quantum or not. What quantum algorithms actually offer is narrower and more specific: for a select set of problems, they can find the answer dramatically faster than any classical algorithm ever could. Two examples, more than any others, put that power on the map: Shor’s algorithm and Grover’s algorithm.
Shor’s Algorithm: The One That Worried the NSA
Shor’s algorithm solves a deceptively simple-sounding problem: given a large number, find its prime factors. For small numbers, this is trivial, but for very large numbers, factoring becomes so difficult that modern encryption (RSA, the system protecting much of the internet) leans on that difficulty as its entire foundation. Shor’s algorithm can factor large numbers exponentially faster than the best classical method, fast enough that, on a sufficiently powerful quantum computer, it could threaten to break RSA encryption entirely.
Here’s how it actually came to exist, and it’s a story worth telling properly.
In 1992, mathematician Umesh Vazirani gave a talk at Bell Labs on work he’d done with Ethan Bernstein, putting quantum computation on rigorous mathematical footing for the first time. Around the same time, Daniel Simon devised a problem (now known as Simon’s problem) that a quantum computer could solve dramatically faster than any classical one. Peter Shor, a mathematician working at Bell Labs, had actually seen Simon’s paper earlier, while serving on a conference program committee and the committee had rejected it. Before it was even published, Shor realized he could build on Simon’s idea. He called Simon directly, got a copy of the paper to work from properly, and used it to solve a related and even harder question: the discrete logarithm problem.
Get Thanos Tatsios’s stories in your inbox
Join Medium for free to get updates from this writer.
Shor gave a talk on that result at Bell Labs , known, by his own account, for having one of the toughest, most relentlessly questioning audiences in the field. It went well. And then, within days, he pushed the same idea further and solved something bigger: factoring.
Word spread almost immediately and, as word does, it distorted a little along the way. Shor had only told a couple of people about the factoring result, but within five days, the rumor had outrun the truth: physicist Umesh Vazirani called him having already heard “you can factor on a quantum computer” and asked how it worked. Shor talked through the algorithm with cryptographer Charlie Bennett at a theory conference in New York that spring, then presented it formally at the Cornell Algorithmic Number Theory Symposium. Someone from the NSA was in the audience.
It’s not hard to see why. An algorithm that could factor large numbers efficiently wasn’t just an elegant piece of math it was a direct threat to the cryptographic backbone of the internet. Requests for the paper poured in. Shor was fielding interview requests from magazines before the ink was dry.
That’s the origin of Shor’s algorithm: not a slow, deliberate research program, but a handful of frantic days built on another mathematician’s rejected paper and it remains, more than three decades later, one of the strongest arguments anyone has ever made for why quantum computers matter.
Grover’s Algorithm: Finding a Needle in a Digital Haystack
Imagine searching a database with billions of unsorted entries and finding exactly what you’re looking for almost instantly. That’s the promise of Grover’s algorithm, developed by Lov Grover in 1996.
Here’s the classical baseline: if you’re searching an unsorted database with N entries, nothing to sort by, no shortcuts, just checking one by one, a classical computer needs, on average, roughly N operations. Grover’s algorithm cuts that down to roughly the square root of N. That might sound like a modest improvement, but at scale, billions or trillions of entries, the square root of a number is dramatically smaller than the number itself. This is what’s called a quadratic speedup, and it’s a genuine, provable advantage over anything classical.
Here’s roughly how it works, broken into steps:
- Initialization. The algorithm starts by putting every qubit into superposition using Hadamard gates. If you’re searching a database of N entries, this creates a superposition where every single entry starts out equally likely.
- The oracle. A component called the oracle (the same kind of oracle we ran into earlier) identifies the correct entry by flipping the phase of its amplitude. This marks the right answer without revealing it outright, setting up the next step to find it.
- The Grover diffusion operator. This step reflects all the amplitudes around their average, which has the effect of boosting the marked (correct) answer’s probability while shrinking everyone else’s.
- Repeat, then measure. Steps 2 and 3 get repeated roughly (π/4)√N times, after which measuring the system gives you the correct answer with very high probability, often close to certainty, for large N.
Why this matters beyond the theory
One of the most talked-about implications is in cryptography. Classically, brute-forcing an encryption key is an O(N) problem. Grover’s algorithm brings that down to O(√N) which, translated into practical terms, means it effectively halves the security strength of symmetric encryption keys. A 128-bit key, which would take 2¹²⁸ operations to brute-force classically, would only take roughly 2⁶⁴ operations under Grover’s algorithm. That’s still an enormous number 2⁶⁴ is far beyond what any quantum computer can realistically attempt today but it’s a meaningful enough reduction that cryptographers already design newer standards with it in mind.
Beyond cryptography, Grover’s algorithm has real potential in data mining, optimization, and search-heavy tasks generally, anywhere you’re hunting for a specific answer inside a genuinely unstructured pile of data. It’s worth being honest about the limits, though: Grover’s algorithm only helps with unstructured search. If your data is already organized, sorted, indexed, structured, classical algorithms like binary search are often just as good or better, and quantum offers no advantage there.
It’s also worth being upfront about where we actually are: running Grover’s algorithm at a scale that matters commercially requires far more qubits, and far better error rates and coherence times, than today’s quantum hardware provides. This is an area of real, active progress, but “practical, large-scale Grover search” is still a future milestone, not a present-day reality.
Two more names worth knowing
Two other algorithms come up constantly once you start reading about quantum computing, so it’s worth having quick definitions on hand:
- Variational Quantum Eigensolver (VQE) a hybrid approach that combines a quantum computer with a classical optimizer, mainly used to simulate molecules and find their lowest-energy configurations. This is exactly the kind of tool that could eventually help with the battery chemistry problem we opened article 2 with.
- Quantum Phase Estimation (QPE) estimates a specific mathematical property (an eigenvalue) of a quantum operation. It’s a supporting building block used inside both Shor’s algorithm and many quantum chemistry simulations.
How to Measure the Performance of a Quantum Computer
If someone tells you a quantum computer has “1,000 qubits,” how impressed should you actually be? The honest answer: it depends, qubit count alone doesn’t tell you nearly as much as it sounds like it should. Quantum hardware performance really comes down to three separate dimensions: scale, quality, and speed. A processor can lead in one and lag in the others, so understanding all three is the only way to actually compare systems fairly.
Scale: how many qubits can you actually use?
Not every qubit on a chip is available for you to program directly. Many exist purely to support the ones doing the actual computing helping connect qubits to each other, holding error-correction information, or assisting with control and readout. The number that actually matters for scale is programmable qubits: the ones you can prepare in a specific state, manipulate with high-precision operations, and measure as part of an algorithm. The total number of qubits on a chip, programmable ones plus all their supporting infrastructure, is a separate, larger number, and as hardware matures, the gap between “total qubits” and “usable qubits” tends to grow, not shrink.
Quality: how much can the system actually do before errors take over?
Every quantum operation introduces a small chance of error, and those errors compound the longer and more complex a computation gets. Quality is a measure of how many of the hardest operations, specifically, operations that entangle two qubits together, a system can reliably chain together before noise overwhelms the result. A processor with more usable qubits than another, but far weaker error rates, might actually be able to run less sophisticated algorithms in practice. This is why qubit count by itself is a genuinely misleading headline number.
Speed: how much useful work can the system do per second?
The third axis is throughput, how many quantum circuits a system can run and measure per second. This matters more than it might sound like at first: a slower system doesn’t just take longer, it costs more per unit of useful computation, since quantum computing time is generally billed by usage. A faster system lets researchers test more ideas, explore larger parameter spaces, and get more value out of the same hardware in the same amount of time.
Looking ahead: T-gates as the next quality metric
As quantum hardware matures toward full fault tolerance, computers robust enough to correct their own errors as they go the way we measure “quality” is expected to shift. Right now, two-qubit operations are the standard proxy for difficulty, because they’re the most common bottleneck in today’s noisy hardware. But not all operations are created equal: some, called Clifford gates, can actually be simulated efficiently by classical computers (this should sound familiar it’s the same idea behind the Gottesman–Knill theorem we covered a few sections ago). The genuinely hard, genuinely “quantum” operations are non-Clifford gates and the T-gate, the same small phase-shifting gate that unlocked universality earlier in this article, is the most demanding of them to implement reliably. As fault-tolerant systems come online, expect T-gate count to become the new standard measure of a quantum computer’s real computational muscle.
The takeaway
Whenever you hear a headline qubit number, it’s worth asking three quieter questions instead:
- How many of those qubits can actually be programmed?
- How many demanding operations can the system chain together before errors take over?
- And how many of those computations can it run per second?
Those three numbers, together, tell you far more about what a quantum computer can genuinely do than any single qubit count ever will.
Next Stop: Writing Quantum Code
We’ve now covered a lot of ground, superposition and entanglement as physical phenomena, the gates that create them, the algorithms that put them to work, and even the metrics used to judge whether a quantum computer is any good. That’s the theory, and it’s real, tested, and (mostly) proven.
But there’s a question we haven’t touched yet: what does it actually look like to write something for a quantum computer? Not the physics, not the math on a whiteboard, the actual code.
That’s where we’re headed next. We’ll get hands-on with Qiskit, IBM’s open-source framework for building and running real quantum circuits, the same Hadamard gates, CNOT gates, and superposition states we’ve spent this whole article talking about, but now as a few lines of Python you can actually run.
Theory is one thing. Watching a qubit you programmed yourself collapse into a real, measured answer is another. See you there!
References
- Feynman, R. P. (1982). “Simulating Physics with Computers.” International Journal of Theoretical Physics, 21(6/7). Based on his 1981 keynote at MIT’s First Conference on the Physics of Computation.
- IBM Quantum Learning. “Quantum Computing Fundamentals” course. IBM Quantum Platform.
- Terra Physica. “How Does a Quantum Computer Calculate? The Simplest Explanation!”
- Shor, P. Oral history interview recounting the discovery of Shor’s algorithm, including the influence of Daniel R. Simon’s work and Ethan Bernstein and Umesh Vazirani’s foundational paper on quantum complexity theory.
- Shor, P. W. (1997). “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.” SIAM Journal on Computing, 26(5).
- Grover, L. K. (1996). “A Fast Quantum Mechanical Algorithm for Database Search.” Proceedings of the 28th Annual ACM Symposium on Theory of Computing.
- Gottesman, D. (1998). “The Heisenberg Representation of Quantum Computers.” foundational work behind the Gottesman–Knill theorem.
- Preskill, J. (2025). “Beyond NISQ: The Megaquop Machine.” arXiv:2502.17368.
- IBM Research. Blog post on quantum hardware performance metrics scale, quality, and speed (programmable qubits, qubit operations, circuit throughput).
- Wikipedia contributors. “Quantum algorithm.” Wikipedia, The Free Encyclopedia.
