Tag: Quantum Series

Quantum Computing: A Complete Learning Path

QUANTUM SERIES 2026
The complete learning path, from a single qubit to Grover’s algorithm.

This is the index to the Techucation Quantum Series: a sequence of hands-on posts that build quantum computing from the ground up. Each one stands on its own, but together they form a single arc, from what a qubit actually is, through the rules that make quantum mechanics strange, to the algorithms that turn those rules into a real speedup. The order below is a learning path from first principles to algorithms, not the order the posts were written.

New to the topic? Read top to bottom. Already comfortable with qubits and gates? Skip ahead to the algorithms in Section 4.
1  ·  Start Here: Qubits and Superposition
1
Introduction to Quantum Computing: Qubits, Hadamard Gates, and Superposition
First principles: what a qubit is, how the Hadamard gate builds superposition, and why tensor products scale the state space.
2  ·  The Hadamard Toolkit
2
The Quantum Fourier Transform of a Single Qubit is the Hadamard Transform
The one-qubit QFT turns out to be exactly the Hadamard gate, a small result that anchors the bigger picture.
3
The Walsh-Hadamard Matrix: Backbone of Grover’s Diffusion Operator
How the Hadamard sign table generalises to n qubits and powers Grover’s diffusion step.
3  ·  The Rules of the Quantum World
4
Reversible Computation in Quantum Computing
Why every quantum gate must be reversible, and how ancilla bits turn irreversible logic into unitary logic.
5
The Cost of Garbage in Quantum Computing
Leftover junk qubits destroy interference; uncomputation cleans them up to protect the speedup.
6
The No-Cloning Theorem: Why You Cannot Copy a Qubit
A short proof that an unknown quantum state cannot be duplicated, and what that impossibility makes possible.
7
Quantum Teleportation, and Why It Is Not Cloning
Moving an unknown qubit from one place to another without ever copying it, using entanglement and two classical bits.
4  ·  Algorithms
8
Understanding Phase Kickback
The mechanism where the target qubit flips the control’s phase, the trick underneath Deutsch’s, Grover’s, and Shor’s.
9
Deutsch’s Algorithm: The Four Cases
The four one-bit Boolean functions, the reversible oracle, and the single query that beats the classical two.
10
Deutsch Revisited: Quantum vs Classical in Qiskit
The same algorithm in running Qiskit code: two classical queries against one quantum query.
11
Grover’s Algorithm: Inversion About the Mean
A full three-qubit walkthrough of the oracle and the amplitude amplification that surfaces the marked item.
5  ·  Entanglement and Bell’s Inequality
12
The CHSH Game Simulator and Bell’s Inequality
An interactive game where quantum entanglement beats the classical 75 percent ceiling and violates Bell’s inequality.

Quantum Series 2026  ·  Built with Qiskit 1.x

✦ This article was generated with the assistance of Claude by Anthropic ✦

Quantum Teleportation in Quantum Computing, and Why It Isn’t Cloning

QUANTUM SERIES 2026
Moving a qubit you are forbidden to copy.

Teleportation is the most over-sold word in quantum computing. It conjures Star Trek transporters and faster-than-light messaging, and almost every popular account quietly implies you end up with a copy of the original. You do not. Quantum teleportation moves an unknown quantum state from one qubit to another while destroying the original, and that destruction is not an incidental detail. It is the mechanism that keeps the protocol on the right side of the no-cloning theorem.

1  ·  A quick word on no-cloning

This whole protocol is haunted by the no-cloning theorem: there is no operation that copies an arbitrary unknown quantum state. That proof and its consequences are covered in a recent post, The No-Cloning Theorem in Quantum Computing: Why You Can’t Copy a Qubit, and are not re-derived here.

The single fact needed going forward: you cannot deterministically duplicate an unknown qubit. The qualifiers matter, because teleportation lives in the gaps between them. The theorem forbids copying unknown states (a known state you can re-prepare at will), it forbids deterministic, perfect copies, and it is a statement about unitary operations — and measurement, which teleportation leans on at the decisive moment, is not unitary.

2  ·  Why teleportation is not cloning

Here is the distinction in one sentence: cloning would leave |ψ⟩ in two places; teleportation leaves it in exactly one.

Partway through the protocol, Alice’s message qubit is measured. Measurement collapses it into a classical basis state — a plain |0⟩ or |1⟩ carrying none of the original amplitudes. By the time Bob’s qubit holds |ψ⟩, Alice’s qubit demonstrably does not. The state was relocated, and the accounting is exact: one copy in, one copy out. No moment ever exists where two qubits both carry |ψ⟩, so there is nothing for the no-cloning theorem to object to.

This also kills the faster-than-light fantasy. The protocol forces Alice to send Bob two ordinary classical bits. Until they arrive, Bob’s qubit is information-free, as the algebra below shows.

3  ·  The complete circuit

Here is the whole protocol in a single circuit. Read it left to right; the amber dashed dividers mark the three stages. The message qubit q0 starts in the unknown state |ψ⟩, while q1 and q2 both start in |0⟩.

1. Bell pair2. Alice measures3. Bob corrects
q0:HM
q1:H+M
q2:+XZ

Stage 1 — Bell pair. Alice and Bob share an entangled pair: an H on q1 followed by a CNOT from q1 onto q2 prepares (|00⟩ + |11⟩)/√2 across the two halves.

Stage 2 — Alice measures. Alice folds her message into the pair (a CNOT from q0 onto q1, then an H on q0) and measures both of her qubits, collapsing them to two classical bits.

Stage 3 — Bob corrects. Depending on those two bits, Bob applies an X and/or a Z to q2 — the X controlled by Alice’s q1 bit, the Z by her q0 bit — and q2 emerges as |ψ⟩. The next section is the algebra that fixes exactly which correction each outcome needs.

4  ·  The protocol in bra-ket and tensor form

Now the algebra behind that circuit. Three qubits: q0 carries |ψ⟩ = α|0⟩ + β|1⟩ (Alice), q1 is Alice’s half of the Bell pair, and q2 is Bob’s half. They pre-share |Φ+⟩ = (|00⟩ + |11⟩)/√2 on q1 q2.

Step 1 — the starting state. Tensor the message against the Bell pair:

|ψ⟩ = α|0⟩ + β|1⟩            (the unknown message on q0)

|ψ⟩ ⊗ |Φ+⟩ = (α|0⟩ + β|1⟩) ⊗ (|00⟩ + |11⟩)/√2
           = (1/√2) [ α|000⟩ + α|011⟩ + β|100⟩ + β|111⟩ ]

Step 2 — Alice’s CNOT (control q0, target q1):

CNOT (control q0, target q1)  flips q1 wherever q0 = 1:

= (1/√2) [ α|000⟩ + α|011⟩ + β|110⟩ + β|101⟩ ]

Step 3 — Alice’s Hadamard on q0. Substitute |0⟩ → (|0⟩+|1⟩)/√2 and |1⟩ → (|0⟩−|1⟩)/√2, then collect by the value of (q0 q1):

H on q0, then collect by the pair Alice will measure (q0 q1):

= (1/2) [ |00⟩ (α|0⟩ + β|1⟩)    ← case A
        + |01⟩ (α|1⟩ + β|0⟩)    ← case B
        + |10⟩ (α|0⟩ − β|1⟩)    ← case C
        + |11⟩ (α|1⟩ − β|0⟩) ]  ← case D

Each bracketed q2 state is the original |ψ⟩ acted on by a known Pauli. Alice measures, gets one of four outcomes (each with probability 1/4), sends the two bits to Bob, and Bob undoes the Pauli. The Case column ties each row back to the matching line in Step 3:

Case
Alice measures (q0 q1)
Bob holds on q2
Relation to |ψ⟩
Bob applies
A
00
α|0⟩ + β|1⟩
I |ψ⟩
nothing
B
01
α|1⟩ + β|0⟩
X |ψ⟩
X
C
10
α|0⟩ − β|1⟩
Z |ψ⟩
Z
D
11
α|1⟩ − β|0⟩
ZX |ψ⟩
X then Z

Bob applies Zm0 Xm1 — an X if m1 = 1, then a Z if m0 = 1 — and every branch lands back on α|0⟩ + β|1⟩ = |ψ⟩.

5  ·  Qiskit — classical feed-forward

This version measures mid-circuit and uses real classical conditioning via if_test, the honest picture of the protocol. The verification trick: rather than read out Bob’s state, apply the inverse of the preparation to q2. If teleportation worked, that must collapse q2 to |0⟩ on every shot.

import numpy as np
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister, transpile
from qiskit.circuit.library import StatePreparation
from qiskit.quantum_info import random_statevector
from qiskit_aer import AerSimulator

# Unknown state to teleport (StatePreparation is unitary -> invertible)
psi  = random_statevector(2)
prep = StatePreparation(psi)

q   = QuantumRegister(3, “q”)     # q0 message, q1 Alice, q2 Bob
mz  = ClassicalRegister(1, “mz”)  # q0 result -> drives Z
mx  = ClassicalRegister(1, “mx”)  # q1 result -> drives X
out = ClassicalRegister(1, “out”) # verification bit
qc  = QuantumCircuit(q, mz, mx, out)

qc.append(prep, [0]); qc.barrier()        # 1. load |ψ⟩ onto q0
qc.h(1); qc.cx(1, 2); qc.barrier()        # 2. Bell pair on (q1,q2)
qc.cx(0, 1); qc.h(0)                      # 3. Alice’s basis change
qc.measure(0, mz); qc.measure(1, mx); qc.barrier()

with qc.if_test((mx, 1)):                 # 4. Bob’s corrections
    qc.x(2)
with qc.if_test((mz, 1)):
    qc.z(2)
qc.barrier()

qc.append(prep.inverse(), [2])            # 5. un-prepare on Bob: must read 0
qc.measure(2, out)

counts = AerSimulator().run(transpile(qc, AerSimulator()), shots=4000).result().get_counts()
clean  = all(k.split()[0] == “0” for k in counts)   # leftmost bit = out
print(counts); print(“Teleportation verified:”, clean)
The out bit comes back 0 on 100% of shots regardless of the random (mx, mz) branch — exactly the claim that Bob reconstructs |ψ⟩ in every case.

6  ·  No faster-than-light, and the takeaway

Before Bob learns (m0, m1), his qubit is an equal mixture of the four branch states. Averaging the four projectors gives the Pauli twirl:

ρ_Bob = (1/4)( |ψ⟩⟨ψ| + X|ψ⟩⟨ψ|X
              + Z|ψ⟩⟨ψ|Z + XZ|ψ⟩⟨ψ|ZX )  =  I/2   for every |ψ⟩

for any |ψ⟩. Bob’s local state is identical no matter what Alice sent, so no information has reached him yet. The classical bits are not a formality — they are the only thing that carries the state across, and they travel no faster than light.

Takeaway. No-cloning forbids duplicating an unknown qubit (proof here). Teleportation never attempts a copy: it entangles the message with a shared Bell pair, measures the original out of existence, and ships two classical bits naming which of four Pauli corrections rebuilds the state on the other end. Exactly one copy before, exactly one after. No-cloning is not a bug the protocol works around — it is the reason the protocol has to look the way it does.

Quantum Series 2026  ·  Built with Qiskit 1.x

✦ This article was generated with the assistance of Claude by Anthropic ✦

The No-Cloning Theorem in Quantum Computing: Why You Can’t Copy a Qubit

QUANTUM SERIES 2026
The no-cloning theorem: why an unknown quantum state cannot be copied, and what that buys us.

Copying is so ordinary in classical computing that we never think about it. Every assignment, every memory write, every Ctrl+C duplicates a bit string perfectly and at will. Quantum mechanics flatly refuses to do the same for an unknown state. There is no machine, no clever circuit, no sequence of gates that takes an arbitrary qubit and hands you back two identical copies of it. This is the no-cloning theorem, and far from being a limitation we tolerate, it is the structural reason quantum key distribution is secure, the reason entanglement cannot be used to signal faster than light, and the reason quantum error correction had to be reinvented from scratch.

The proof is short. It falls out of two properties we have already relied on throughout this series: linearity of quantum evolution, and unitarity. Below we prove it both ways, clear up the very common confusion about CNOT “copying” a qubit, walk through the consequences, and then watch a cloning attempt fail in Qiskit.

1  ·  What “cloning” would actually mean

A cloning machine would be a single fixed unitary U together with a standard blank register |e⟩, such that for every possible input state |ψ⟩ it produces:

U  ( |ψ⟩ ⊗ |e⟩ )  =  |ψ⟩ ⊗ |ψ⟩

Three pieces of that statement deserve unpacking, because the whole theorem turns on them.

What |e⟩ is, and what “blank” means. The register |e⟩ is simply the second slot, the one that will end up holding the copy. We call it “blank” by analogy with an empty sheet of paper or an uninitialised memory cell: before the operation it carries no information whatsoever about the input |ψ⟩. The conventional choice is |0⟩, or |0…0⟩ when the copy needs several qubits, but |e⟩ does not have to be the zero vector specifically. Any fixed pure state works equally well for the theorem. The property that actually matters is not its literal value but that it is independent of the unknown input. A register that already secretly equalled |ψ⟩ would not be blank, and you would not have copied anything, you would have been handed the answer.

What “fixed” means, for both U and |e⟩. Fixed means chosen in advance and identical on every run, never allowed to depend on which |ψ⟩ happens to come in. This is the condition that keeps the problem honest. If you were permitted to pick |e⟩ or U based on the input, you would first have to know what |ψ⟩ is, and at that point there is nothing left to clone: you could just prepare a second copy yourself. So the cloner gets one unitary and one starting register, and they must work for an arbitrary, unknown input. The claim of the theorem is that no such pair (U, |e⟩) exists.

Why cloning a known state is allowed, and how you do it. The theorem forbids copying an unknown arbitrary state. It says nothing about states you already understand, and there are two everyday ways such a state can be “known”:

You know… How you get two copies
The preparation recipe (the amplitudes, or the circuit that builds it) Just run the preparation twice on two fresh |0⟩ qubits. You are re-preparing from a known description, not copying an unknown state.
That the state is one of a known orthogonal set Measure in the basis that distinguishes the set. Orthogonal states are eigenstates of that measurement, so they survive it undisturbed. Read off the label, then re-prepare as many copies as you like.

As a concrete example of the first route, if you are told the state is |ψ⟩ = Ry(θ)|0⟩ for a known angle θ, you simply apply Ry(θ) to two separate qubits. No universal device is involved, and no rule is broken. The contradiction in the next two sections appears only when no such side information exists, that is, when the same machine must handle a continuum of unknown inputs at once.

The one-line distinction: you can always re-prepare a state you know how to build, and you can copy states that act like classical labels. What you cannot do is build one fixed machine that duplicates an arbitrary, unknown state handed to you blind.

2  ·  Proof I: linearity forbids it

Assume, for contradiction, that a universal cloner U exists. Pick two arbitrary states |ψ⟩ and |φ⟩. By assumption U clones both of them:

U |ψ⟩|e⟩  =  |ψ⟩|ψ⟩
U |φ⟩|e⟩  =  |φ⟩|φ⟩

Now feed the machine a superposition of the two inputs, |χ⟩ = (1/√2)(|ψ⟩ + |φ⟩). Quantum evolution is linear, so U acts term by term on the input:

U |χ⟩|e⟩  =  (1/√2) ( U|ψ⟩|e⟩  +  U|φ⟩|e⟩ )
         =  (1/√2) ( |ψ⟩|ψ⟩  +  |φ⟩|φ⟩ )

But if U is genuinely a cloner, then by definition it must also clone |χ⟩ itself, producing |χ⟩|χ⟩. Expanding that out:

|χ⟩|χ⟩  =  (1/2) ( |ψ⟩ + |φ⟩ )( |ψ⟩ + |φ⟩ )
      =  (1/2) ( |ψ⟩|ψ⟩ + |ψ⟩|φ⟩ + |φ⟩|ψ⟩ + |φ⟩|φ⟩ )

The two results disagree. Linearity gave us only the “diagonal” terms |ψ⟩|ψ⟩ and |φ⟩|φ⟩, whereas true cloning of |χ⟩ demands the cross terms |ψ⟩|φ⟩ and |φ⟩|ψ⟩ as well. They can only match if the cross terms vanish, which happens precisely when |ψ⟩ and |φ⟩ are identical or orthogonal. For general, non-orthogonal states the equality is impossible. The cloner cannot exist.

The contradiction is the same one that powers most quantum no-go results: a device defined by its action on a basis is forced, by linearity, into a behaviour on superpositions that contradicts the original specification.

3  ·  Proof II: unitarity forbids it

The linearity argument shows cloning fails for superpositions. A second proof, often considered the cleaner one, uses the fact that unitary operations preserve inner products. Suppose again that U clones two states:

U |ψ⟩|e⟩  =  |ψ⟩|ψ⟩
U |φ⟩|e⟩  =  |φ⟩|φ⟩

The inner product is taken over the full two-register states that U acts on, not over |ψ⟩ and |φ⟩ on their own. Label the two inputs and their images under U:

Input A   = |ψ⟩|e⟩        Output UA  = |ψ⟩|ψ⟩
Input B   = |φ⟩|e⟩        Output UB  = |φ⟩|φ⟩

If U is unitary, then   ⟨A|B⟩  =  ⟨UA|UB⟩

That identity, ⟨A|B⟩ = ⟨UA|UB⟩, is the definition of a unitary: it preserves inner products. U never acts on the inner product itself, which is only a number; it acts on the states, and unitarity says doing so cannot change their overlap. Now evaluate both sides, using the tensor-product factorisation ⟨a|⟨b| · |c⟩|d⟩ = ⟨a|c⟩ ⟨b|d⟩ and ⟨e|e⟩ = 1:

⟨A|B⟩   = ⟨ψ|⟨e| · |φ⟩|e⟩  =  ⟨ψ|φ⟩ ⟨e|e⟩  =  ⟨ψ|φ⟩
⟨UA|UB⟩ = ⟨ψ|⟨ψ| · |φ⟩|φ⟩  =  ⟨ψ|φ⟩ ⟨ψ|φ⟩  =  ⟨ψ|φ⟩²

so   ⟨ψ|φ⟩  =  ⟨ψ|φ⟩²

Write x = ⟨ψ|φ⟩. The condition x = x² rearranges to x(x − 1) = 0, whose only solutions are x = 0 or x = 1. In other words, cloning is consistent only when the two states are orthogonal (x = 0) or identical (x = 1). Any pair of distinct, non-orthogonal states, the generic case, breaks the equality. No universal cloner can exist.

⟨ψ|φ⟩ Relationship Cloneable?
0 Orthogonal (a known basis set) Yes, this is just classical copying
1 Identical (already known) Yes, trivially
anything else Distinct, non-orthogonal No

Both proofs converge on the same boundary. Orthogonal states carry distinguishable classical labels and can be copied; overlapping quantum states cannot.

4  ·  “But doesn’t CNOT copy a qubit?”

This is the single most common point of confusion, and it is worth resolving carefully. A CNOT with the input qubit as control and a fresh |0⟩ as target looks exactly like a copy operation. On computational basis states it behaves like one:

CNOT |0⟩|0⟩  =  |0⟩|0⟩
CNOT |1⟩|0⟩  =  |1⟩|1⟩

So far it really is copying: the second qubit ends up matching the first. The trouble appears the moment the control is a superposition. Take |ψ⟩ = a|0⟩ + b|1⟩ as control and |0⟩ as target:

CNOT ( a|0⟩ + b|1⟩ )|0⟩  =  a|00⟩ + b|11⟩

Compare that with what a true clone would have produced, namely |ψ⟩|ψ⟩:

|ψ⟩|ψ⟩  =  a²|00⟩ + ab|01⟩ + ab|10⟩ + b²|11⟩

These are different states. The CNOT output a|00⟩ + b|11⟩ is an entangled pair, not two independent copies. If you discard the original and look at the “copy” on its own, you do not find |ψ⟩; you find a mixed state that has lost the phase relationship between a and b entirely. CNOT copies the value in the computational basis but destroys the superposition structure that made the state quantum in the first place. That is exactly the gap between copying classical information, which is always allowed, and cloning a quantum state, which is not.

Rule of thumb: CNOT copies basis labels, not quantum states. The instant the input is in superposition, the “copy” is entanglement, not duplication.

5  ·  Why this single theorem matters so much

No-cloning is not a footnote. Three of the most important results in quantum information rest directly on it.

Quantum key distribution. In BB84, Alice sends qubits encoded in randomly chosen bases. An eavesdropper, Eve, would love to intercept each qubit, keep a copy, and forward the original untouched so she can measure her copies later once the bases are announced. No-cloning makes that impossible. Eve cannot duplicate an unknown qubit, so she is forced to measure in transit, and measuring in the wrong basis disturbs the state and injects a detectable error rate. The security of the protocol is the no-cloning theorem wearing a different hat.

No faster-than-light signalling. Entanglement correlates distant measurement outcomes, which has always tempted people into superluminal-communication schemes. Many of those schemes secretly assume Bob can clone his half of an entangled pair, make many copies, and read off the statistics to learn which basis Alice measured in. No-cloning closes that loophole and is one of the reasons quantum mechanics and relativity coexist without paradox.

Quantum error correction. Classical error correction leans on the simplest trick imaginable: copy the bit several times and take a majority vote. That is illegal in the quantum setting, because you cannot copy an unknown logical state. Quantum codes had to be built on a different principle, spreading logical information across many physical qubits using entanglement and measuring error syndromes without ever reading or duplicating the encoded state. The whole architecture of fault tolerance is shaped by the fact that the obvious classical fix is off the table.

A useful way to hold it in your head: no-cloning is what stops quantum information from behaving like classical information. Almost everything that makes quantum protocols both powerful and secure traces back to that one restriction.

6  ·  Watching a clone fail in Qiskit

The abstract proof is convincing, but it is satisfying to watch the failure happen numerically. We attempt the naive CNOT “clone” of the state |+⟩ = H|0⟩, then measure how badly it falls short by two yardsticks: fidelity against the intended |+⟩|+⟩, and the purity of the copy qubit on its own.

Three terms in plain language:

Fidelity is a similarity score between two quantum states, from 0 to 1. Think of it as a match percentage: 1.0 means identical, 0 means completely unrelated.

Reduced state is the honest description of one qubit when you ignore its partner. Picture two coins glued so they always land the same way: cover one and look at just the other, and that single coin looks like a plain 50/50 flip. The “match” information lived in the pair, not in either coin alone. Discarding the partner mathematically is called tracing it out.

Purity tells you whether a state is sharp and definite or a blurry random mixture. Purity 1 is a clean, definite state. For a single qubit the lowest value is 0.5, called maximally mixed, which is total randomness, the quantum version of a fair coin holding no information.

from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector, partial_trace, state_fidelity

qc = QuantumCircuit(2)
qc.h(0)         # prepare |+> on qubit 0 (the “original”)
qc.cx(0, 1)    # naive “cloning” attempt via CNOT

state = Statevector(qc)
print(state)   # (|00> + |11>)/sqrt(2), a Bell state

target = Statevector.from_label(‘++’)   # what we wanted: |+>|+>
print(state_fidelity(state, target))   # 0.5

rho_copy = partial_trace(state, [0])   # trace out the original
print(rho_copy.data)   # I/2, maximally mixed
print(rho_copy.purity().real)   # 0.5

Running it gives:

Output state:  (√2/2)|00⟩ + (√2/2)|11⟩
Fidelity to |+⟩|+⟩:  0.5
Reduced state of copy:  [[0.5, 0], [0, 0.5]]
Purity of copy:  0.5

Every number tells the same story. The output is a maximally entangled Bell state, not the product |+⟩|+⟩ we were hoping for, and the fidelity to the intended clone is only 0.5. Trace out the original and the supposed “copy” is the maximally mixed state I/2, with purity 0.5 rather than 1. The copy retains no memory of the |+⟩ superposition at all; it is as good as a fair coin. The CNOT did precisely what the theorem says it must: it produced correlation, not duplication.

Try changing qc.h(0) to any other single-qubit rotation, say qc.ry(0.7, 0). The fidelity stays stubbornly below 1 for every non-basis input, which is the no-cloning theorem reproduced one statevector at a time.

Quantum Series 2026  ·  Built with Qiskit 1.x

✦ This article was generated with the assistance of Claude by Anthropic ✦

About the author

Malcolm Low is an Associate Professor at the Singapore Institute of Technology, writing on quantum computing, programming, and applied computing from Singapore.

Website: malcolmlow.com  ·  Singapore

Quantum Computing: The Walsh-Hadamard Matrix — Backbone of Grover’s Diffusion Operator

QUANTUM SERIES 2026
The mathematical foundation behind Grover’s diffusion operator — derived from first principles.

In the Grover’s Algorithm — Inversion About the Mean walkthrough, the diffusion operator applies H⊗³ twice per iteration. Every single step is governed by a sign table called the Hadamard Reference. That table is not a lookup shortcut — it is the 8×8 Walsh-Hadamard Transform matrix written out in full. This post derives it from scratch: one qubit, then two, then all three, arriving at the complete matrix and the rule behind every sign in it.

1  ·  The Circuit: Three Qubits, Three Hadamard Gates

We initialise all three qubits in the ground state |0⟩ and route each through its own independent Hadamard gate. There are no two-qubit (entangling) gates here — the circuit is entirely parallel.

Qubit Input Gate Output ket
q₀ |0⟩ H (1/√2)( |0⟩ + |1⟩ )
q₁ |0⟩ H (1/√2)( |0⟩ + |1⟩ )
q₂ |0⟩ H (1/√2)( |0⟩ + |1⟩ )

All three outputs are identical because all three inputs are identical. The structure we need emerges when we take their tensor product.

2  ·  Single-Qubit Hadamard Action

The Hadamard gate H maps the two computational basis states as follows:

Input H |input⟩ Short notation
|0⟩ (1/√2)( |0⟩ + |1⟩ ) |+⟩
|1⟩ (1/√2)( |0⟩ − |1⟩ ) |−⟩

In matrix form:

H  =  (1/√2)    +1   +1 
 +1   −1 
Key property: H is its own inverse — H² = I. Every element has magnitude 1/√2, so tensoring three copies multiplies the magnitudes to 1/√8 while the signs follow a precise bitwise pattern.
3  ·  Two-Qubit Tensor Product: q₀ ⊗ q₁

Expanding the tensor product of the first two post-H qubits:

|+⟩ ⊗ |+⟩
  = (1/√2)(|0⟩ + |1⟩) ⊗ (1/√2)(|0⟩ + |1⟩)
  = (1/2)( |0⟩⊗|0⟩ + |0⟩⊗|1⟩ + |1⟩⊗|0⟩ + |1⟩⊗|1⟩ )
  = (1/2)( |00⟩ + |01⟩ + |10⟩ + |11⟩ )
All four two-qubit basis states appear with equal amplitude 1/2. Measurement probability per state: (1/2)² = 25%.
4  ·  Three-Qubit Tensor Product: q₀ ⊗ q₁ ⊗ q₂

Adding the third qubit expands the superposition to all 8 three-bit strings:

|+⟩ ⊗ |+⟩ ⊗ |+⟩
  = (1/√2)³ (|0⟩+|1⟩) ⊗ (|0⟩+|1⟩) ⊗ (|0⟩+|1⟩)
  = (1/√8)( |000⟩ + |001⟩ + |010⟩ + |011⟩
            + |100⟩ + |101⟩ + |110⟩ + |111⟩ )
This is |ψinit⟩ — the uniform superposition over all 8 basis states that opens Grover’s algorithm (Phase 0 in the walkthrough). Each state carries amplitude +1/√8 ≈ 0.3535 and measurement probability 1/8 = 12.5%. All signs are positive because we only applied H to |0⟩ inputs — the sign variation appears when H⊗³ acts on states other than |000⟩.
5  ·  The 8×8 Walsh-Hadamard Sign Matrix

When H⊗³ is applied to an arbitrary basis state |j⟩, the result is:

H⊗³ |j⟩  =  (1/√8)   Σᵢ   (−1)popcount(i AND j)   |i⟩

The entry at row i, column j carries sign (−1)popcount(i AND j) divided by √8. The table below shows all 64 signs — green (+) for +1/√8 and red (−) for −1/√8:

H⊗³ |j⟩ →
output |i⟩ ↓		 |000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
H|000⟩ + + + + + + + +
H|001⟩ + − + − + − + −
H|010⟩ + + − − + + − −
H|011⟩ + − − + + − − +
H|100⟩ + + + + − − − −
H|101⟩ + − + − − + − +
H|110⟩ + + − − − − + +
H|111⟩ + − − + − + + −
+  =  amplitude +1/√8 ≈ +0.3535     −  =  amplitude −1/√8 ≈ −0.3535
6  ·  Why the Sign is (−1)popcount(i AND j)

Because H acts independently on each qubit, H⊗³ is the tensor product of three 2×2 matrices. The entry at row i, column j is simply the product of the three corresponding single-qubit entries:

H⊗³[i, j]  =  H[i₀, j₀]  ×  H[i₁, j₁]  ×  H[i₂, j₂]

Each single-qubit factor equals +1 unless both the k-th bit of i and the k-th bit of j are 1, in which case it equals −1. So the k-th factor contributes a sign of (−1)iₖ·jₖ. Multiplying all three:

sign(i, j)  =  (−1)i₀j₀ + i₁j₁ + i₂j₂  =  (−1)popcount(i AND j)
The rule in plain terms: bitwise AND the row index and the column index, count the 1-bits, check parity. Even count → positive. Odd count → negative.

Quick verification: row H|101⟩, column |011⟩

i (row) j (col) i AND j popcount Sign
101 (= 5) 011 (= 3) 001 1 (odd) − ✓

Matches the matrix in Section 5: row H|101⟩, column |011⟩ is indeed −.

7  ·  Connection to Grover’s Diffusion Operator

This matrix is the Hadamard Reference table used throughout the Grover’s Algorithm — Inversion About the Mean post. The diffusion operator D = H⊗³ (2|0⟩⟨0| − I) H⊗³ works in three sub-steps, each directly using this matrix:

Sub-step Operation Grover walkthrough steps
First H⊗³ Maps computational basis → Hadamard basis. Each amplitude spreads across all 8 columns via the sign table. 4.1  ·  6.1  ·  8.1
Phase flip 2|0⟩⟨0|−I: keeps |000⟩ unchanged, negates all other states. This is the inversion-about-the-mean mechanism. 4.2  ·  6.2  ·  8.2
Second H⊗³ Maps back to computational basis using the same sign table (H is self-inverse). Routes constructive interference into the target state. 4.3  ·  6.3  ·  8.3
The bottom line: without the sign structure of the Walsh-Hadamard matrix, neither the uniform superposition (Phase 0) nor the diffusion step (every iteration) would work. The matrix is the silent engine behind Grover’s quadratic speedup.

Quantum Series 2026  ·  Built with Qiskit 1.x

✦ This article was generated with the assistance of Claude by Anthropic ✦

Quantum Computing: Grover’s Algorithm – Inversion About the Mean

Grover’s Algorithm: Exact Mathematical Evolution

Full 3-Qubit Matrix Interference Walkthrough

What is Grover’s Algorithm? Grover’s algorithm is a quantum search procedure that locates a marked item in an unsorted list of N items in O(√N) oracle queries — a quadratic speedup over any classical approach. For N = 8 (3 qubits), this means roughly ⌊π/4 × √8⌋ = 2 optimal iterations before the probability of measuring the target state peaks.

This walkthrough tracks the exact amplitude of every basis state through each gate operation for the 3-qubit case, with target state |101>. All arithmetic is shown so each step can be verified by hand.

Structure of each iteration (Grover operator G):

  • Oracle Uf — Phase-flips the target state: |x> → -|x> if f(x) = 1, otherwise |x> → |x>.
  • Diffusion operator D = H⊗n(2|0><0| − I)H⊗n — Reflects all amplitudes about their mean, amplifying the marked state at the expense of the others.

Key insight: The oracle introduces destructive interference at the target, which the diffusion operator then converts into constructive interference by inverting amplitudes about their mean. Each iteration rotates the state vector by an angle 2θ closer to the target, where sin(θ) = 1/√N.

Circuit Overview — 3 Qubits, Target |101⟩
Init Diffusion 1 Diffusion 2
|0⟩H Uf HZ0H Uf HZ0H M
|0⟩H   H H   H H M
|0⟩H   H H   H H M
Iteration 1 Iteration 2 · optimal
H = Hadamard Uf = Oracle (phase-flips target) Z0 = 2|0⟩⟨0|−I M = Measure

Phase 0: Initialization

Steps 1 & 2: Apply H⊗3 to |000> to create a uniform superposition over all 8 basis states. Because each single-qubit Hadamard maps |0> to (|0>+|1>)/√2, applying all three simultaneously yields equal amplitude 1/√8 ≈ 0.3535 for every state. This is the starting point — every state is equally likely, and the algorithm has no preference yet.

|ψinit> = 1/√8 [ |000> + |001> + |010> + |011> + |100> + |101> + |110> + |111> ]

Hadamard Reference (Standard Signs)

The 8×8 Walsh-Hadamard matrix defines the sign pattern when H⊗3 is applied to any basis state. Element (i, j) has sign (−1)popcount(i AND j) — i.e., the number of bit positions where both row state and column state have a 1. The actual amplitude contribution is this sign divided by √8. This table is used in every Hadamard step below: each row corresponds to one input basis state, and its sign pattern determines how it distributes into all 8 output states.

Basis State000001010011100101110111
H|000>++++++++
H|001>+–+–+–+–
H|010>++––++––
H|011>+––++––+
H|100>++++––––
H|101>+–+––+–+
H|110>++––––++
H|111>+––+–++–

Round 1: [Oracle → Diffusion]

Step 3: Oracle Uf — The oracle recognises |101> as the marked state and applies a phase kickback, flipping its amplitude from +1/√8 to −1/√8. All other amplitudes remain unchanged. Physically, this encodes “this is the target” purely in phase — no measurement is made, so the superposition is preserved.

Step 4.1: Round 1 First Hadamard (H)

The diffusion operator begins by mapping from the computational basis back into the Hadamard basis. Each input state |x> with amplitude ax contributes ax/√8 to every output column, with sign given by the reference table. For all non-target states ax = +1/√8, so each cell = (+1/√8)×(Sign/√8) = Sign/8. For the oracle-marked |101>, the amplitude is −1/√8, so the entire row is sign-inverted (highlighted in red). The Net Result row is the vertical sum of all 8 rows for each column.

Source (Post-Oracle)000001010011100101110111
+H|000> (1/√8)+18+18+18+18+18+18+18+18
+H|001> (1/√8)+18-18+18-18+18-18+18-18
+H|010> (1/√8)+18+18-18-18+18+18-18-18
+H|011> (1/√8)+18-18-18+18+18-18-18+18
+H|100> (1/√8)+18+18+18+18-18-18-18-18
-H|101> (-1/√8)-18+18-18+18+18-18+18-18
+H|110> (1/√8)+18+18-18-18-18-18+18+18
+H|111> (1/√8)+18-18-18+18-18+18+18-18
Net Result 4.1+68+28-28+28+28-28+28-28

Step 4.2: Round 1 Phase Flip (Z on non-|000>)

This step implements the 2|0><0|−I operator in the computational basis. In practice it means: keep |000>’s amplitude unchanged, and negate every other state. This is the heart of inversion-about-the-mean: because the |000> column accumulated the largest positive amplitude in Step 4.1 (reflecting the mean of all amplitudes before the first H), flipping everything else relative to it creates the inversion effect that will boost the target in the next step.

State000001010011100101110111
Amp (Post-Z)+68-28+28-28-28+28-28+28

Step 4.3: Round 1 Second Hadamard (H)

The second H maps the Hadamard-basis amplitudes from Step 4.2 back to the computational basis, completing the diffusion operator. Each post-Z amplitude contributes to every output column via the reference sign table, multiplied by 1/√8, giving denominators of 8√8. Summing column |101> yields +208√8 ≈ 0.884 — a dramatic amplification from the initial 0.354 — while all other states settle to +48√8 ≈ 0.177. One iteration is complete.

Source (Post-Z)000001010011100101110111
+H|000> (68)+68√8+68√8+68√8+68√8+68√8+68√8+68√8+68√8
-H|001> (-28)-28√8+28√8-28√8+28√8-28√8+28√8-28√8+28√8
+H|010> (28)+28√8+28√8-28√8-28√8+28√8+28√8-28√8-28√8
-H|011> (-28)-28√8+28√8+28√8-28√8-28√8+28√8+28√8-28√8
-H|100> (-28)-28√8-28√8-28√8-28√8+28√8+28√8+28√8+28√8
+H|101> (28)+28√8-28√8+28√8-28√8-28√8+28√8-28√8+28√8
-H|110> (-28)-28√8-28√8+28√8+28√8+28√8+28√8-28√8-28√8
+H|111> (28)+28√8-28√8-28√8+28√8-28√8+28√8+28√8-28√8
Net Result (R1)+48√8+48√8+48√8+48√8+48√8+208√8+48√8+48√8
Decimal (R1)0.1770.1770.1770.1770.1770.8840.1770.177

Round 2: [Oracle → Diffusion]

Step 5: Oracle Uf — The oracle is applied again to the post-R1 state. |101> now carries a much larger amplitude (+208√8), so the phase flip to −208√8 creates a far more pronounced imbalance. The 7 non-target states each carry only +48√8. This large asymmetry is what will drive even stronger constructive interference in the diffusion step.

Step 6.1: Round 2 First Hadamard (H)

Each amplitude is multiplied by 1/√8 as it spreads across the 8 columns via the reference sign table. The denominator becomes 8√8 × √8 = 64. The 7 uniform states (+48√8) form balanced Walsh-Hadamard rows that cancel perfectly for all non-|000> columns — only the oracle-perturbed |101> row breaks the symmetry, contributing an extra −24 or +24 to each non-zero column (depending on the H sign for that bit pattern). Column |000> is special: all 8 rows contribute positively, giving +864.

Source (Post-Oracle)000001010011100101110111
+H|000> (48√8)+464+464+464+464+464+464+464+464
+H|001> (48√8)+464-464+464-464+464-464+464-464
+H|010> (48√8)+464+464-464-464+464+464-464-464
+H|011> (48√8)+464-464-464+464+464-464-464+464
+H|100> (48√8)+464+464+464+464-464-464-464-464
-H|101> (-208√8)-2064+2064-2064+2064+2064-2064+2064-2064
+H|110> (48√8)+464+464-464-464-464-464+464+464
+H|111> (48√8)+464-464-464+464-464+464+464-464
Net Result 6.1+864+2464-2464+2464+2464-2464+2464-2464

Step 6.2: Phase Flip (Z on non-|000>)

Same operation as Step 4.2: negate every amplitude except |000>. The |000> column retains its +864 value. All other states flip sign, converting e.g. +2464 → −2464. This primes the second Hadamard to route amplitude toward the target state.

State000001010011100101110111
Amp (Post-Z)+864-2464+2464-2464-2464+2464-2464+2464

Step 6.3: Round 2 Second Hadamard (H)

The final H of the diffusion operator maps the post-Z amplitudes back to the computational basis. Each amplitude propagates through the Hadamard sign table with denominator 64√8. Column |101> receives a constructive sum of +17664√8 ≈ 0.972 — near-certain success. The non-target states all land at −1664√8 ≈ −0.088, where the negative sign carries no measurement consequence. This is the optimal stopping point for 3-qubit Grover search: stopping here gives the highest possible P(|101>).

Source (Post-Z)000001010011100101110111
+H|000> (864)+864√8+864√8+864√8+864√8+864√8+864√8+864√8+864√8
-H|001> (-2464)-2464√8+2464√8-2464√8+2464√8-2464√8+2464√8-2464√8+2464√8
+H|010> (2464)+2464√8+2464√8-2464√8-2464√8+2464√8+2464√8-2464√8-2464√8
-H|011> (-2464)-2464√8+2464√8+2464√8-2464√8-2464√8+2464√8+2464√8-2464√8
-H|100> (-2464)-2464√8-2464√8-2464√8-2464√8+2464√8+2464√8+2464√8+2464√8
+H|101> (2464)+2464√8-2464√8+2464√8-2464√8-2464√8+2464√8-2464√8+2464√8
-H|110> (-2464)-2464√8-2464√8+2464√8+2464√8+2464√8+2464√8-2464√8-2464√8
+H|111> (2464)+2464√8-2464√8-2464√8+2464√8-2464√8+2464√8+2464√8-2464√8
Net Result (R2)-1664√8-1664√8-1664√8-1664√8-1664√8+17664√8-1664√8-1664√8
Decimal (R2)-0.088-0.088-0.088-0.088-0.088+0.972-0.088-0.088
Success Probability: P(101) = |0.9724|2 ≈ 94.5%

Round 3: [Oracle → Diffusion] (The Overcooking Effect)

Step 7: Oracle Uf — With P(|101>) at 94.5%, one more iteration is one too many. The oracle again flips |101>’s amplitude: +17664√8 → −17664√8. The 7 non-target states each remain at −1664√8. The state vector has been rotated 2θ past its peak, and a third diffusion step will push it further away from the target, not closer.

Step 8.1: Round 3 First Hadamard (H)

The denominator grows to 512 (= 64√8 × √8). All 8 input amplitudes are now negative (after the oracle flip, |101> is −17664√8 and the rest are −1664√8), so the |000> column accumulates a strongly negative sum (−288512). The non-|000> columns are dominated by the large −|101> row contribution, which is sign-inverted from the reference table and therefore contributes ±176512. The net result is a lopsided distribution that the phase flip will convert into a push away from the target.

Source (Post-Oracle)000001010011100101110111
-H|000> (-1664√8)-16512-16512-16512-16512-16512-16512-16512-16512
-H|001> (-1664√8)-16512+16512-16512+16512-16512+16512-16512+16512
-H|010> (-1664√8)-16512-16512+16512+16512-16512-16512+16512+16512
-H|011> (-1664√8)-16512+16512+16512-16512-16512+16512+16512-16512
-H|100> (-1664√8)-16512-16512-16512-16512+16512+16512+16512+16512
-H|101> (-17664√8)-176512+176512-176512+176512+176512-176512+176512-176512
-H|110> (-1664√8)-16512-16512+16512+16512+16512+16512-16512-16512
-H|111> (-1664√8)-16512+16512+16512-16512+16512-16512-16512+16512
Net Result 8.1-288512+160512-160512+160512+160512-160512+160512-160512

Step 8.2: Round 3 Phase Flip (Z on non-|000>)

The |000> amplitude (−288512) is preserved. All other amplitudes flip sign. Notice that after R2 the non-target states had small negative amplitudes; after the phase flip here they become positive (+160512), while the target column was −160512 and now becomes +160512 as well — the diffusion has lost its asymmetry and will no longer strongly favour |101>.

State000001010011100101110111
Amp (Post-Z)-288512-160512+160512-160512-160512+160512-160512+160512

Step 8.3: Round 3 Second Hadamard (H)

The second H maps amplitudes back to the computational basis with denominators of 512√8. The large negative |000> amplitude now spreads destructive interference broadly, while the relatively uniform positive amplitudes for the remaining states partially cancel in the |101> column. The result is +832512√8 = +138√8 ≈ +0.575 for |101> and −448512√8 = −78√8 ≈ −0.309 for all non-target states. P(|101>) has fallen to ~33%, demonstrating that iterating past the optimal count hurts. Importantly, |101> still leads every other state by 3×, so a single extra iteration only partially degrades the result — it has not catastrophically lost the solution.

Source (Post-Z)000001010011100101110111
-H|000> (-288512)-288512√8-288512√8-288512√8-288512√8-288512√8-288512√8-288512√8-288512√8
-H|001> (-160512)-160512√8+160512√8-160512√8+160512√8-160512√8+160512√8-160512√8+160512√8
+H|010> (160512)+160512√8+160512√8-160512√8-160512√8+160512√8+160512√8-160512√8-160512√8
-H|011> (-160512)-160512√8+160512√8+160512√8-160512√8-160512√8+160512√8+160512√8-160512√8
-H|100> (-160512)-160512√8-160512√8-160512√8-160512√8+160512√8+160512√8+160512√8+160512√8
+H|101> (160512)+160512√8-160512√8+160512√8-160512√8-160512√8+160512√8-160512√8+160512√8
-H|110> (-160512)-160512√8-160512√8+160512√8+160512√8+160512√8+160512√8-160512√8-160512√8
+H|111> (160512)+160512√8-160512√8-160512√8+160512√8-160512√8+160512√8+160512√8-160512√8
Net Result (R3)-448512√8-448512√8-448512√8-448512√8-448512√8+832512√8-448512√8-448512√8
Simplified (R3)-78√8-78√8-78√8-78√8-78√8+138√8-78√8-78√8
Decimal (R3)-0.309-0.309-0.309-0.309-0.309+0.575-0.309-0.309

⚠ Overcooking Confirmed — But Not Catastrophic

The state vector has rotated past the optimal angle. P(|101>) drops from 94.5% (R2) to 33.0% — a significant fall, but |101> still has more than double the probability of any other state. The algorithm has not “lost” the answer; it has merely de-amplified it. Note also that the target amplitude is still positive (+0.575) — the vector has not crossed zero, it has simply overshot past the maximum. The 33.0% comes directly from the Born rule: P(|101>) = |amplitude|² = |+0.575|² ≈ 0.330.

About the author

Malcolm Low is an Associate Professor at the Singapore Institute of Technology, writing on quantum computing, programming, and applied computing from Singapore.

Website: malcolmlow.com  ·  Singapore

The Cost of Garbage in Quantum Computing

The Hidden Witness

Why You Must Clean Up “Junk Bits” with Uncomputation

1. The “Observer” Effect

In quantum computing, anything that “knows” what a qubit is doing acts as a Witness. Leftover data (Junk Bits) on an ancilla qubit act as witnesses, destroying the interference your algorithm needs to work.

Case A: Ideal (No Junk)

H
H
|0>
|0>

100% Interference

Case B: Broken (With Junk)

H
+
H
|0>
|0>
?
|junk>

Random 50/50 Noise

2. Mathematical Working

Ideal Case: (1/2) ( |0> + |1> + |0> – |1> ) = |0>
(Identical paths cancel perfectly.)

Junk Case: (1/2) ( |00> + |10> + |01> – |11> )
(Terms cannot cancel because the ancilla bit is different. Interference is destroyed.)

3. The Solution: Uncomputation

To restore interference, we follow the Compute-Copy-Uncompute pattern. This resets our ancilla to |0> and removes the “witness.”

Input |x>
Ancilla |0>
Target |0>
COMPUTE
+
UNCOMPUTE
|x> (Clean)
|0> (Clean)
|f(x)> (Result)

4. Qiskit Implementation

from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

qc = QuantumCircuit(3)
qc.h(0) 
qc.cx(0, 1) # COMPUTE: Create Junk on q1
qc.cx(1, 2) # COPY Result to q2
qc.cx(0, 1) # UNCOMPUTE: Clean Junk back to |0>
qc.h(0)     # Interference Restored!

qc.measure_all()
counts = AerSimulator().run(transpile(qc, AerSimulator())).result().get_counts()
print(f"Resulting state: {counts}")

Built with Qiskit 1.x • Quantum Series 2025

About the author

Malcolm Low is an Associate Professor at the Singapore Institute of Technology, writing on quantum computing, programming, and applied computing from Singapore.

Website: malcolmlow.com  ·  Singapore

Reversible Computation in Quantum Computing

Reversible Computation in Quantum Computing

Mastering Reversibility, Ancilla Bits, and Unitary Logic

1. The Necessity of Reversibility

In classical logic, gates like AND are inherently irreversible. Because they compress two input bits into a single output bit, information is physically destroyed. For example, if an AND gate outputs ‘0’, you cannot distinguish if the original inputs were (0,0), (0,1), or (1,0). This “many-to-one” mapping results in information loss that manifests as heat dissipation.

In quantum computing, thermodynamics and the laws of physics require all operations to be Unitary (U†U = I). This means every quantum gate must be a 1-to-1 (bijective) mapping; no information is ever lost, and the entire computation can be run in reverse to recover the initial state.

AND
Out: 0

The Logic Gap: If the output is 0, the input could be (0,0), (0,1), or (1,0). The path back is lost.

2. Ancilla Bits & Uncomputation

Because we cannot erase information, we use Ancilla bits as temporary “scratch space.” However, if these qubits are left in an arbitrary state, they remain entangled with the computation. Uncomputation (running gates in reverse) resets them to |0>, “cleaning” the quantum workspace.

The Toffoli Gate (CCX)

The Toffoli gate is reversible because its mapping is bijective. No two inputs result in the same output.

+
In: A
In: B
In: C
Input (A, B, C) Output (A, B, C ⊕ AB) Status
0, 0, 00, 0, 0Unique
1, 1, 01, 1, 1Flipped (AND)
1, 1, 11, 1, 0Flipped Back

The Fredkin Gate (CSWAP)

The Fredkin gate is a controlled-swap operation. It swaps the states of the two target qubits (T1 and T2) if and only if the control qubit (C) is in the state |1>. It is conservative, meaning it preserves the Hamming weight (number of 1s) from input to output.

Because it is a universal gate, we can simulate all standard classical logic by fixing certain inputs:

  • NOT: Set T1=0, T2=1. Output T2 becomes NOT C.
  • AND: Set T2=0. Output T2 becomes C AND T1.
  • OR: Set T1=B, T2=1. Output T1 becomes C OR B.
✕
✕
In: C
In: T1
In: T2

3. Mathematics: Unitary vs. Hermitian

Proof: Is Pauli-Y Unitary?

Y =
0–i
i0
Y† =
0–i
i0

Pauli-Y is Unitary (Y†Y = I). Because Y = Y†, it is also Hermitian.

Unitary but NOT Hermitian: The S Gate

S =
10
0i
≠
S† =
10
0–i

Since S ≠ S†, you must apply the S-Dagger gate to reverse an S rotation.

4. Qiskit Verification

from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator

qc = QuantumCircuit(3)
qc.x([0, 1]) # Controls to |1>

# Toffoli is Hermitian (U = U†), so applying it twice cleans the ancilla
qc.ccx(0, 1, 2) # Calculation step
qc.ccx(0, 1, 2) # Uncomputation step

qc.measure_all()
counts = AerSimulator().run(transpile(qc, AerSimulator())).result().get_counts()
print(f"Resulting state: {counts}") # Expect {'011': 1024}

Built with Qiskit 1.x • Quantum Series 2025

About the author

Malcolm Low is an Associate Professor at the Singapore Institute of Technology, writing on quantum computing, programming, and applied computing from Singapore.

Website: malcolmlow.com  ·  Singapore

Deutsch Algorithm Revisited: Quantum vs Classical Implementation in Qiskit

QUANTUM SERIES 2026
Quantum vs classical implementation of Deutsch’s Algorithm in Qiskit: same answer, half the queries.

The previous post covered the theory: four Boolean functions, the reversible oracle Uf, the phase-kickback derivation, and the single-query measurement result. This post puts it into running code. We implement the classical two-query approach and the quantum one-query approach side by side in Qiskit so the advantage is visible, not just promised.

1  ·  The Challenge

Given a black-box function f: {0,1} → {0,1}, determine whether it is constant (f(0) = f(1)) or balanced (f(0) ≠ f(1)).

Approach Oracle queries required Strategy
Classical 2 Evaluate f(0), then f(1), compare
Quantum (Deutsch) 1 Query in superposition, read phase via interference
The quantum advantage: instead of probing the function at individual inputs, the algorithm queries it at a superposition of both inputs simultaneously, then uses interference to extract a global property (constant vs balanced) with a single measurement.
2  ·  Oracle Functions

First we build the four oracle circuits. Each implements one of the four single-bit Boolean functions as a reversible quantum gate. The constant oracles ignore x; the balanced oracles use x as a control.

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator

def create_constant_oracle(constant_value):
    “””Creates a constant oracle (returns 0 or 1 for all inputs)”””
    oracle = QuantumCircuit(2, name=f”Constant_{constant_value}”)
    if constant_value == 1:
        oracle.x(1)  # Flip the output qubit
    return oracle

def create_balanced_oracle(balance_type):
    “””Creates a balanced oracle”””
    oracle = QuantumCircuit(2, name=f”Balanced_{balance_type}”)
    if balance_type == ‘identity’:
        # f(x) = x
        oracle.cx(0, 1)
    elif balance_type == ‘negation’:
        # f(x) = NOT x
        oracle.x(0)
        oracle.cx(0, 1)
        oracle.x(0)
    return oracle
3  ·  Classical Approach: Two Queries Required

The classical algorithm calls the oracle twice: once with input 0 to learn f(0), and once with input 1 to learn f(1). Each query is a separate circuit run.

def classical_deutsch_query1(oracle):
    “””First query: Evaluate f(0)”””
    qr = QuantumRegister(2, ‘q’)
    cr = ClassicalRegister(1, ‘c’)
    qc = QuantumCircuit(qr, cr)
    # Input: x = 0 (already initialised to |0>)
    qc.barrier()
    qc.compose(oracle, inplace=True)
    qc.barrier()
    qc.measure(1, 0)  # Measure output to get f(0)
    return qc

def classical_deutsch_query2(oracle):
    “””Second query: Evaluate f(1)”””
    qr = QuantumRegister(2, ‘q’)
    cr = ClassicalRegister(1, ‘c’)
    qc = QuantumCircuit(qr, cr)
    qc.x(0)  # Input: x = 1
    qc.barrier()
    qc.compose(oracle, inplace=True)
    qc.barrier()
    qc.measure(1, 0)  # Measure output to get f(1)
    return qc
Classical bottleneck: two separate measurements, two separate circuit executions. The classical algorithm measures the output qubit q[1] in both cases to read the function values directly.
4  ·  Quantum Approach: One Query Suffices

The quantum circuit initialises q[1] = |1⟩, applies Hadamard gates to both wires, queries the oracle exactly once, then applies a final Hadamard to q[0] before measuring it. The oracle is never called again.

def deutsch_algorithm(oracle):
    “””Implements Deutsch’s algorithm — requires only ONE query”””
    qr = QuantumRegister(2, ‘q’)
    cr = ClassicalRegister(1, ‘c’)
    qc = QuantumCircuit(qr, cr)

    # Step 1: Initialise q[1] to |1>
    qc.x(1)
    qc.barrier()

    # Step 2: Hadamard on both wires (superposition)
    qc.h(0)
    qc.h(1)
    qc.barrier()

    # Step 3: Single oracle query
    qc.compose(oracle, inplace=True)
    qc.barrier()

    # Step 4: Final Hadamard on q[0]
    qc.h(0)
    qc.barrier()

    # Step 5: Measure q[0] — the INPUT qubit, not the output
    qc.measure(0, 0)
    return qc

The quantum circuit measures q[0], the input qubit. The classical circuits measure q[1], the output qubit. That structural difference is the entire quantum advantage: the quantum algorithm reads a global property of the function via interference, not an individual function value.

5  ·  Running the Comparison

Test all four oracles with both approaches and compare query counts.

oracles = [
    (“Constant 0”,           create_constant_oracle(0)),
    (“Constant 1”,           create_constant_oracle(1)),
    (“Balanced (Identity)”, create_balanced_oracle(‘identity’)),
    (“Balanced (Negation)”, create_balanced_oracle(‘negation’))
]
simulator = AerSimulator()

for name, oracle in oracles:
    # Classical: 2 queries
    f_0 = int(list(simulator.run(classical_deutsch_query1(oracle), shots=1).result().get_counts().keys())[0])
    f_1 = int(list(simulator.run(classical_deutsch_query2(oracle), shots=1).result().get_counts().keys())[0])
    classical_result = “CONSTANT” if f_0 == f_1 else “BALANCED”

    # Quantum: 1 query
    counts = simulator.run(deutsch_algorithm(oracle), shots=1000).result().get_counts()
    quantum_result = “CONSTANT” if ‘0’ in counts else “BALANCED”

    print(f”{name}: Classical={classical_result}, Quantum={quantum_result}”)

Sample output:

Constant 0:          Classical=CONSTANT, Quantum=CONSTANT
Constant 1:          Classical=CONSTANT, Quantum=CONSTANT
Balanced (Identity): Classical=BALANCED, Quantum=BALANCED
Balanced (Negation): Classical=BALANCED, Quantum=BALANCED
Both methods always agree. The quantum result is deterministic: the simulator returns 100% |0⟩ for constant oracles and 100% |1⟩ for balanced ones, with zero noise on shots=1000.
6  ·  Circuit Overview

Classical Query 1 — Evaluate f(0)
q[0] stays in |0⟩, both wires pass through Uf, and q[1] is measured to read f(0).

q[0]: |0⟩ (not measured)
Uf
q[1]: |0⟩ M f(0)

Classical Query 2 — Evaluate f(1)
An X gate flips q[0] to |1⟩, both wires pass through Uf, and q[1] is measured to read f(1).

q[0]: |0⟩ X (not measured)
Uf
q[1]: |0⟩ M f(1)

Quantum Deutsch — Single Query
H gates create superposition on both wires, one oracle query encodes f(0) ⊕ f(1) as a phase, the final H on q[0] converts phase to amplitude, and measuring q[0] gives the answer directly.

q[0]: |0⟩ H H M 0=const, 1=bal
Uf
q[1]: |1⟩ H
The structural difference: the classical circuits measure the output qubit q[1] to read individual function values. The quantum circuit measures the input qubit q[0] after interference to read a global property of the function. That is what lets a single query reveal whether the function is constant or balanced.
7  ·  Measurement Interpretation and Conclusion

The measurement result on q[0] maps directly to the function type:

Measure q[0] Function type Interference mechanism
0 Constant f(0) ⊕ f(1) = 0 → constructive on |0⟩
1 Balanced f(0) ⊕ f(1) = 1 → destructive on |0⟩, constructive on |1⟩

The quantum speedup is 2x here (one query instead of two). Modest for a two-input function, but the same technique scales: Deutsch-Jozsa extends this to n-bit functions, cutting 2n−1+1 classical queries down to one. Simon’s algorithm extends it further. Shor’s algorithm for factoring, the most consequential quantum algorithm known, relies on the same architectural idea: query in superposition, encode information as phase, extract via interference and measurement.

To run the code: pip install qiskit qiskit-aer. The full comparison script outputs all four oracle types side by side. Try modifying the oracle functions to explore how each gate sequence implements f.

Quantum Series 2026  ·  Built with Qiskit 1.x

✦ This article was generated with the assistance of Claude by Anthropic ✦

Deutsch’s Algorithm in Quantum Computing: The 4 Cases

QUANTUM SERIES 2026
The four Boolean functions, the reversible oracle, and the single-query Deutsch circuit with full derivation.

Deutsch’s Algorithm determines whether a single-bit function f(x) is constant (f(0) = f(1)) or balanced (f(0) ≠ f(1)) using only one oracle query. To understand how the algorithm works, we first need to see how each possible function is physically realised as a reversible quantum gate, and then how the complete Deutsch circuit encodes that function into a measurable phase difference.

1  ·  The 4 Possible Functions

With a single input bit x ∈ {0,1} and output bit f(x) ∈ {0,1}, there are exactly four possible Boolean functions. Two are constant (output ignores the input) and two are balanced (output depends on the input).

# Name f(0) f(1) Gate implementation Type
1 Constant Zero 0 0 Identity — no gates needed Constant
2 Constant One 1 1 X gate on output wire only Constant
3 Balanced ID 0 1 CNOT (x = control, y = target) Balanced
4 Balanced NOT 1 0 X on x, CNOT, X on x (flip, copy, restore) Balanced

The two balanced oracles as quantum circuits. Both have x on the control wire and y on the target wire, with the bottom wire carrying y ⊕ f(x) as output.

Balanced ID — f(x) = x

x: control — x unchanged
y: + y ⊕ x = y ⊕ f(x)

Balanced NOT — f(x) = ¬x

x: X X flip, control, restore
y: + y ⊕ ¬x = y ⊕ f(x)
Key point: both constant oracles leave the x wire untouched and act only on y. Both balanced oracles use x as a control and output y ⊕ f(x) on the target wire. All four are reversible, which is required for quantum computation.

2  ·  The General Oracle Uf

All four functions are wrapped in a single reversible gate Uf that leaves the input register unchanged and XORs the function value into the output register:

Uf |x⟩|y⟩  =  |x⟩ |y ⊕ f(x)⟩

As a two-wire circuit, Uf passes x unchanged on the top wire while the bottom wire carries y ⊕ f(x). The box spans both wires to show they are processed jointly by a single gate:

x: x (unchanged)
Uf
y: y ⊕ f(x)

The reversibility of Uf is guaranteed because XOR is its own inverse: applying Uf twice returns the original state. This property allows quantum algorithms to query f without destroying the superposition.

Setting y = |−⟩ = (1/√2)(|0⟩ − |1⟩) turns Uf into a phase-kickback machine: Uf|x⟩|−⟩ = (−1)f(x)|x⟩|−⟩. The function value is encoded in the phase of the control qubit rather than the target, and the target remains in |−⟩ unchanged.

3  ·  The Complete Deutsch Circuit

The algorithm wraps Uf in Hadamard gates on both wires. Initialise q[0] = |0⟩ and q[1] = |1⟩, apply H to both, query Uf once, apply a final H to q[0], then measure q[0]:

q[0]: |0⟩ H H M
Uf
q[1]: |1⟩ H
|ψ₀⟩ |ψ₁⟩ |ψ₂⟩

The three states at each checkpoint:

State Expression Note
|ψ₀⟩ |0⟩|1⟩ Initialisation
|ψ₁⟩ |+⟩|−⟩ = ½(|0⟩+|1⟩)(|0⟩−|1⟩) After both H gates
|ψ₂⟩ (1/√2)[(−1)^f(0)|0⟩+(−1)^f(1)|1⟩] ⊗ |−⟩ After Uf, before final H
The target qubit q[1] stays in |−⟩ throughout. Only the phase of q[0] changes, carrying the function information via kickback.

4  ·  Mathematical Proof

The full derivation follows four steps. Each is exact; no approximation is involved.

Step 1 — Initialisation:
  |ψ₀⟩ = |0⟩|1⟩

Step 2 — Apply H to both wires:
  |ψ₁⟩ = |+⟩|−⟩
       = (1/√2)(|0⟩ + |1⟩) ⊗ (1/√2)(|0⟩ − |1⟩)

Step 3 — Apply U_f (phase kickback on |−⟩ target):
  U_f |x⟩|−⟩ = (−1)^f(x) |x⟩|−⟩

  |ψ₂⟩ = (1/√2)[ (−1)^f(0)|0⟩ + (−1)^f(1)|1⟩ ] ⊗ |−⟩

Step 4 — Apply H to q[0] and inspect cases:

  Constant  f(0) = f(1) = c:
    |ψ₂⟩ = (−1)^c (1/√2)(|0⟩ + |1⟩) ⊗ |−⟩
    After H: (−1)^c |0⟩ ⊗ |−⟩  →  Measure 0

  Balanced  f(0) ≠ f(1):
    |ψ₂⟩ = ±(1/√2)(|0⟩ − |1⟩) ⊗ |−⟩
    After H: ±|1⟩ ⊗ |−⟩  →  Measure 1
The global phase (−1)^c in the constant case is unobservable. All that matters is whether the amplitudes on |0⟩ and |1⟩ are in phase (constant) or out of phase (balanced), which the final H converts to a deterministic measurement.

5  ·  Final Measurement

The measurement of q[0] after the final Hadamard gives a deterministic result in both cases:

Measure q[0] Function type Why
0 Constant f(0) ⊕ f(1) = 0; amplitudes add constructively on |0⟩
1 Balanced f(0) ⊕ f(1) = 1; amplitudes cancel on |0⟩, survive on |1⟩

A classical algorithm must evaluate f(0) and f(1) separately, requiring two queries. Deutsch’s algorithm queries Uf exactly once, using superposition to probe both inputs simultaneously and interference to extract a global property of the function. This is the first demonstrated quantum computational advantage over any classical approach.

The technique introduced here — query in superposition, encode information as phase, extract via interference — is the blueprint for Deutsch-Jozsa, Simon’s algorithm, and ultimately Shor’s factoring algorithm.
About the author

Malcolm Low is an Associate Professor at the Singapore Institute of Technology, writing on quantum computing, programming, and applied computing from Singapore.

Website: malcolmlow.com  ·  Singapore

Quantum Series 2026  ·  Built with Qiskit 1.x

✦ This article was generated with the assistance of Claude by Anthropic ✦

Understanding Phase Kickback in Quantum Computing

QUANTUM SERIES 2026
How the target controls the controller and why this underpins Grover’s, Shor’s, and Deutsch’s algorithms.

In standard classical logic, a control bit dictates what happens to a target. In quantum mechanics the relationship is symmetric. When the target qubit is in an eigenstate of the gate operator, the eigenvalue phase is kicked back onto the control qubit, leaving the target unchanged while flipping the relative phase of the control. This post derives that result from first principles using the CNOT gate on |+⟩ ⊗ |−⟩.

1  ·  The CNOT Circuit and the Kickback Setup

The circuit places the control qubit in superposition |+⟩ and the target qubit in |−⟩. Since |−⟩ is an eigenstate of X with eigenvalue −1, the kickback occurs.

control: |+⟩ |−⟩
target: |−⟩ + |−⟩
Key observation: The target qubit is unchanged after the CNOT. The control qubit flips from |+⟩ to |−⟩. The phase was kicked back to the control, not forward to the target.

2  ·  Full Derivation: |+⟩ ⊗ |−⟩ through CNOT

Step 1 — Define the initial state

|ψ₀⟩ = |+⟩ ⊗ |−⟩
  = (1/√2)(|0⟩ + |1⟩) ⊗ (1/√2)(|0⟩ − |1⟩)

Step 2 — Expand the tensor product

|ψ₀⟩ = (1/2)[ |00⟩ − |01⟩ + |10⟩ − |11⟩ ]

Step 3 — Apply the CNOT gate

|ψ₁⟩ = (1/2)[ |00⟩ − |01⟩ + |11⟩ − |10⟩ ]

Step 4 — Factor and identify the result

|ψ₁⟩ = (1/2)[ |0⟩(|0⟩ − |1⟩) − |1⟩(|0⟩ − |1⟩) ]
  = (1/√2)(|0⟩ − |1⟩) ⊗ (1/√2)(|0⟩ − |1⟩)
  = |−⟩ ⊗ |−⟩
The target qubit is still |−⟩ — unchanged by the CNOT. The control qubit changed from |+⟩ to |−⟩. The −1 eigenvalue of the target has been kicked back as a relative phase onto the control.

3  ·  Why Phase Kickback Matters

The math shows that while we applied a gate to the target, the relative phase of the control qubit changed from positive to negative. This is a structural property of controlled unitaries acting on their eigenstates, and it appears at the core of every major quantum algorithm.

AlgorithmHow phase kickback is used
Deutsch’s AlgorithmThe oracle kicks a −1 phase onto the control qubit to encode whether f is constant or balanced, extractable with a single H gate measurement.
Grover’s AlgorithmThe oracle flips the sign of the target state’s amplitude by kicking a −1 phase back to the control register, enabling amplitude amplification.
Shor’s AlgorithmQuantum Phase Estimation relies entirely on phase kickback to transfer eigenvalue information from the target register to the control register.
The general rule: for any unitary U with eigenstate |u⟩ (so U|u⟩ = eⁱᵖ|u⟩), a controlled-U gate with the control in superposition kicks the phase eⁱᵖ back to the control qubit. The target is unchanged.
About the author

Malcolm Low is an Associate Professor at the Singapore Institute of Technology, writing on quantum computing, programming, and applied computing from Singapore.

Website: malcolmlow.com  ·  Singapore

Quantum Series 2026  ·  Built with Qiskit 1.x

✦ This article was generated with the assistance of Claude by Anthropic ✦