Quantum Algorithm: Types, Speedups and a Grover Example in Qiskit

A quantum algorithm is a step-by-step procedure written as a quantum circuit: it prepares qubits, applies gates, and measures, so that the measurement outcomes answer a computational question. This guide is for researchers and students who need to place an algorithm in the literature, run a small one, and report the result honestly. It sorts algorithms using the Quantum Algorithm Zoo’s categories and speedup labels, then walks through Grover’s search in Qiskit with code that was run for this page.

What a quantum algorithm is used for in research

Researchers use quantum algorithms to state a problem in circuit form, estimate how its cost grows with input size, and test it on a simulator or on hardware. The speedup claim is always relative to a classical baseline, so the useful question is not “is it quantum?” but “faster than what, and at what oracle or data-loading cost?” The circuit-level mechanics (gates, wires, measurement) are covered in the quantum circuit guide; the physics background is in what is quantum physics.

Types of quantum algorithm and their speedups

The Quantum Algorithm Zoo (maintained by Stephen Jordan, read 2026-11-08) describes itself as a comprehensive catalog of quantum algorithms. It groups them into four families and labels entries with a speedup type:

Zoo category	Example entries listed	Speedup label given in the Zoo
Algebraic and Number Theoretic	Factoring, Discrete-log, Pell’s Equation	Factoring and Discrete-log: superpolynomial
Oracular	Searching, Abelian Hidden Subgroup, Deutsch-Jozsa	Searching: polynomial; Deutsch-Jozsa: exponential over P, none over BPP
Approximation and Simulation	Hamiltonian dynamics, Knot Invariants	Given per entry in the Zoo
Optimization, Numerics, and Machine Learning	Adiabatic, QAOA, Linear Systems	Linear Systems: superpolynomial

Two anchor results come from the primary papers. Shor’s factoring and discrete-logarithm algorithms are in arXiv quant-ph/9508027 (submitted 1995-08-30). Grover’s database-search algorithm is in arXiv quant-ph/9605043 (submitted 1996-05-29); its search speedup is quadratic, which is optimal for unstructured search at about the square root of N queries. Attacks on public-key schemes based on Shor-type algorithms need a large fault-tolerant machine; see what is cryptography for the classical side of that discussion.

Install or access (official source only)

The IBM Quantum Grover tutorial (read 2026-11-08) requires Qiskit SDK v2.0 or later with visualization support, and, for hardware runs, Qiskit Runtime v0.22 or later (pip install qiskit-ibm-runtime). For the local simulator example below, pip install qiskit is enough; the code on this page was executed with Qiskit 2.6.2. Hardware access and accounts are described in the IBM Quantum Platform access guide. If you collaborate across borders on quantum hardware or software, see the export-control guide.

Step-by-step: Grover’s search on 3 qubits

The IBM tutorial marks two bitstrings, “011” and “100”, among the eight possible 3-bit strings. The workflow is: map the problem to an oracle, build the circuit, transpile, run, and read counts.

1. Build a phase oracle that flips the sign of each marked bitstring (a multi-controlled Z, with X gates on the qubits that must be 0).
2. Turn the oracle into an amplification step with grover_operator() from qiskit.circuit.library.
3. Choose the number of repetitions. With M marked items among N = 2ⁿ, the code below uses floor(π / (4 · arcsin(√(M/N)))); here that is 1.
4. Apply Hadamard gates to all qubits, append the operator repeated with QuantumCircuit.power(), and measure.
5. Transpile with generate_preset_pass_manager(), run with StatevectorSampler (simulator) or SamplerV2 (hardware), and read the counts.

import math
from qiskit import QuantumCircuit
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.primitives import StatevectorSampler
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

def phase_oracle(targets):
    n = len(targets[0])
    qc = QuantumCircuit(n)
    for t in targets:
        flips = [i for i, b in enumerate(reversed(t)) if b == "0"]
        if flips: qc.x(flips)
        qc.compose(MCMTGate(ZGate(), n - 1, 1), inplace=True)
        if flips: qc.x(flips)
    return qc

targets = ["011", "100"]
oracle = phase_oracle(targets)
op = grover_operator(oracle)
iters = math.floor(math.pi / (4 * math.asin(math.sqrt(len(targets) / 2**op.num_qubits))))
qc = QuantumCircuit(op.num_qubits)
qc.h(range(op.num_qubits))
qc.compose(op.power(iters), inplace=True)
qc.measure_all()
isa = generate_preset_pass_manager(optimization_level=3).run(qc)
counts = StatevectorSampler().run([isa], shots=10_000).result()[0].data.meas.get_counts()
print(counts)

This oracle is an independent implementation of the tutorial’s workflow, run for this page with Qiskit 2.6.2. It printed counts of 4971 for “011” and 5029 for “100” out of 10,000 shots; your split will differ because sampling is random.

Output and how to read it

The counts dictionary maps measured bitstrings to how often each occurred. On success the marked bitstrings are the most probable outcomes; here the two targets account for all 10,000 shots. Plot a result with plot_distribution(counts) from qiskit.visualization. In the Runtime sampler pattern the tutorial reads counts from the measurement register with result[0].data.meas.get_counts(), as in the code above. Report the shot count with any distribution you publish.

Troubleshooting

The wrong bitstrings are amplified

Qiskit orders bits with qubit 0 as the rightmost character, so an oracle written for a target string must reverse it. The tutorial’s oracle does this, and the code above does it with reversed(t). If your marked state looks mirrored, check bit order before suspecting the algorithm.

The result is noisy on hardware

The IBM tutorial scales the same circuit to more qubits and reports two-qubit gate depth growing from 39 at n=3 to 111 at n=4, 466 at n=5, 1646 at n=6, 3550 at n=7, 7989 at n=8 and 14824 at n=9. It concludes that this growth makes Grover impractical on current noisy hardware beyond very small problems. A noiseless simulator hides that cost, so say which one you used.

Free alternatives

Option	What it gives you	Where to read more
Qiskit with StatevectorSampler	Local, noiseless run of the example above	This page
Cirq	A separate circuit-building framework	Cirq guide
PennyLane	Circuits as Python quantum functions bound to a device	Quantum circuit guide

Reporting a quantum algorithm in a paper

• State the speedup type (for example polynomial or superpolynomial) and the classical baseline it is measured against.
• State what the oracle or data-loading step costs, since an oracle can hide the work.
• Say whether results come from a simulator or hardware, the shot count, and the software version.

FAQ

What is a quantum algorithm?

It is a procedure expressed as a quantum circuit whose measured output answers a computational problem. Shor’s factoring and Grover’s search are the two best-known examples.

Does Grover’s algorithm give an exponential speedup?

No. Its speedup is quadratic for unstructured search, and the Zoo labels searching as a polynomial speedup.

Can I run a quantum algorithm without hardware?

Yes. A simulator such as Qiskit’s StatevectorSampler runs small circuits locally, as in the example above.

Sources

• IBM Quantum documentation, Grover’s algorithm tutorial, read 2026-11-08.
• Quantum Algorithm Zoo, read 2026-11-08.
• Shor, arXiv quant-ph/9508027; Grover, arXiv quant-ph/9605043 (titles and dates checked via the arXiv API, 2026-11-08).