table of content

Part 1 Foundations

1 Advantages and challenges of programming quantum computers

1.1 Why quantum computing?

1.2 Becoming quantum ready

1.3 The superpowers of quantum computing

1.3.1 The power of quantum parallelism

1.3.2 The random nature of quantum measurement

1.4 The anatomy of a quantum computation

1.4.1 Computing with a single classical bit

1.4.2 Computing with a single quantum bit

1.4.3 Computing with multiple quantum bits

1.4.4 Putting it together

1.5 Patterns of quantum computations

1.5.1 Sampling from probability distributions

1.5.2 Searching for specific outcomes

1.5.3 Estimating the probability of specific outcomes

Summary

2 A first look at quantum computations: The knapsack problem

2.1 A quick overview of optimization problems

2.1.1 The knapsack problem

2.1.2 Problem setup

2.2 The steps of a quantum computation

2.2.1 Outcomes as binary strings

2.2.2 Quantum state and probabilities

2.3 A quantum solution to the knapsack problem

2.3.1 Encoding the problem

2.3.2 Knapsack problem solution

2.4 Tools for programming a quantum solution

Summary

3 Single-qubit states and gates

3.1 Single-qubit state: A pair of complex numbers

3.1.1 Visualizing single-qubit states with tables

3.1.2 The general form of a single-qubit state

3.1.3 Programmatically encoding single-qubit states with lists

3.1.4 Implementing a single-qubit quantum computing simulator in Python

3.2 Changing amplitudes with single-qubit gates

3.2.1 Rotation is multiplication

3.2.2 Basic single-qubit gates

3.2.3 The general form of a single-qubit gate

3.2.4 More basic single-qubit gates

3.2.5 Single-qubit gate inverses

3.3 Simulating changing amplitudes with gates

3.3.1 Printing and visualizing the state

3.3.2 Transforming a single-qubit state

3.3.3 Single-qubit circuits

3.4 Simulating measurement of single-qubit states

3.4.1 Encoding the uniform distribution in a single-qubit quantum state

3.5 Applications of single-qubit computations

3.5.1 Encoding a Bernoulli distribution in a single-qubit quantum state

3.5.2 Encoding a number with a single qubit

Summary

4 Quantum state and circuits: Beyond one qubit

4.1 Computing with more than one qubit

4.1.1 Measurement counts

4.1.2 Sampling from a probability distribution

4.1.3 Understanding quantum computations with a simple Python simulator

4.2 A quantum state is a list of complex numbers

4.2.1 Two-qubit states

4.2.2 Multi-qubit states

4.2.3 Simulating multi-qubit states in Python

4.3 Changing amplitudes with quantum transformations

4.3.1 Selecting pairs of amplitudes based on the target qubit

4.3.2 Pair selection in Python

4.3.3 Simulating amplitude changes

4.3.4 Encoding a uniform distribution in a multi-qubit quantum system

4.4 Controlled quantum transformations

4.4.1 Simulating controlled gate transformations in Python

4.4.2 Simulating multicontrol gate transformations in Python

4.5 Simulating quantum circuits

4.5.1 Simulating measurement of multi-qubit states

4.5.2 Quantum registers and circuits in code

4.5.3 Reimplementing the uniform distribution with registers and circuits

4.5.4 Encoding the binomial distribution in a multi-qubit state

4.5.5 Implementing the Bell states

Summary

Part 2 Fundamental algorithms and patterns

5 Selecting outcomes with quantum oracles

5.1 Describing outcomes with quantum oracles: Intuition and classical implementation

5.1.1 Phase oracles

5.1.2 Bit oracles

5.2 Quantum implementation of oracles

5.2.1 Creating quantum circuits from building blocks

5.2.2 Phase oracle

5.2.3 Bit oracle

5.3 Converting between phase and bit quantum oracles

5.3.1 Converting a phase oracle to a bit oracle

5.3.2 Converting a bit oracle to a phase oracle

5.4 Fibonacci numbers and the golden ratio with good outcomes

Summary

6 Quantum search and probability estimation

6.1 Amplitude amplification: Intuition and classical implementation

6.1.1 Finding good outcomes with oracles

6.1.2 Computing similarity with inner products

6.1.3 The inversion operator

6.1.4 Putting it together: The Grover iterate

6.1.5 A classical but quantum-friendly implementation of the inversion operator

6.2 Magnitude amplification: Quantum circuit implementation

6.2.1 Quantum oracle

6.2.2 The inversion operator

6.2.3 Grover iterate

6.2.4 Putting it all together: Grover’s algorithm

Summary

7 The quantum Fourier transform

7.1 Periodic patterns in sound waves and quantum states

7.1.1 Periodic patterns in sound waves

7.1.2 Periodic patterns in quantum states

7.1.3 Roots of unity and their geometric sequences

7.2 Converting from phase to magnitude encoding with the Hadamard gate

7.3 From classical to quantum Fourier transforms

7.3.1 The classical (discrete) Fourier transform

7.3.2 Introducing the QFT and IQFT

7.4 Quantum circuits for the QFT and IQFT

7.4.1 Understanding the effect of the IQFT on a geometric sequence state

Summary

8 Using the quantum Fourier transform

8.1 The single-slit experiment: Wave diffraction

8.1.1 Introducing the discrete sinc function

8.2 Encoding a periodic signal using discrete sinc quantum states

8.2.1 Phase-to-magnitude frequency encoding with the IQFT

8.2.2 Some useful numerical forms of the frequency encoding pattern

8.2.3 Reversed qubit implementation of phased discrete sinc quantum states

8.3 Discrete sinc as a sequence of coin flips

8.4 Encoding trigonometric distributions in a quantum state

8.4.1 Raised cosine

8.4.2 Other trigonometric functions

Summary

9 Quantum phase estimation

9.1 Estimating the frequency of a periodic quantum state

9.1.1 Getting better angle estimates with more qubits

9.1.2 Reading between the ticks: Getting better estimates with interpolation

9.2 Quantum circuits as rotations with eigenstates and eigenvalues

9.3 The quantum phase estimation algorithm

9.4 Circuit-level implementation of the quantum phase estimation algorithm

9.5 An alternative implementation of the phase estimation circuit without qubit swaps

9.6 Amplitude estimation and quantum counting

9.6.1 Amplitude estimation

9.6.2 Estimating the number of good outcomes with quantum counting

9.6.3 Estimating the probability of good outcomes with amplitude estimation

Summary

Part 3 Quantum solutions: Optimization and beyond

10 Encoding functions in quantum states

10.1 Encoding function inputs and outputs

10.1.1 Encoding a simple function

10.1.2 Encoding the knapsack problem

10.1.3 Encoding polynomials of binary variables

10.1.4 Complexity of polynomial-encoding circuits

10.1.5 Representing negative values

10.2 Searching for function values

10.3 Finding zeros of polynomial functions

Summary

11 Search-based quantum optimization

11.1 Finding desired outcomes with Grover adaptive search

11.2 Finding optimal outcomes with the Grover optimizer

11.3 Solving the knapsack problem with a Grover optimizer

11.3.1 Preparing the state

11.3.2 Encoding constraints

11.3.3 Defining the parameters of the Grover optimizer

Summary

12 Conclusions and outlook

12.1 Quantum concepts in review

12.1.1 Quantum readiness

12.1.2 Quantum advantage and its limitations

12.2 Building quantum software and running on real quantum computers

12.2.1 The importance of a fast, flexible quantum simulator

12.2.2 Source-level compatibility between Hume and Qiskit

12.2.3 Running on real quantum hardware

12.2.4 Quantum assistant

12.3 Revisiting quantum gates and the butterfly pattern

12.3.1 Another look at single-qubit gates and the butterfly pattern

12.4 Quantum states as an image

12.4.1 Visualizing quantum state evolution

12.5 Combinatorial optimization problems

12.5.1 Encoding polynomials with noninteger coefficients

12.5.2 Shor’s factorization algorithm

Summary

Appendices

Appendix A: Math refresher

A.1 Diving deeper into binary strings

A.1.1 Converting between binary and decimal values

A.1.2 Adding a digit to a binary string

A.1.3 Visualizing binary strings with binary trees

A.1.4 Joining and splitting binary strings with prefixes and suffixes

A.1.5 Encoding negative integers

A.2 Using complex numbers to represent amplitudes

A.2.1 Amplitudes as arrows inside the unit circle

A.2.2 Amplitudes as complex numbers: The algebraic form

A.2.3 Amplitudes as complex numbers: The trigonometric (polar) form

A.2.4 Conjugates of complex numbers

A.2.5 Combining amplitude pairs

A.2.6 Amplitudes as colored bars

Summary

Appendix B: More about quantum states and gates

B.1 The Bloch sphere

B.2 Building any gate from Hadamard and phase gates

B.2.1 Example: The Z gate

B.2.2 Example: The X gate

Appendix C: Outcome pairing strategies

C.1 Additional strategies for pair selection in Python

C.1.1 Recognizing pairs by checking the digit for the target qubit

C.1.2 Generating pairs by concatenating the prefix, target, and suffix

Overview

5 Selecting outcomes with quantum oracles

This chapter introduces how quantum oracles let us specify “good” outcomes inside a quantum computation, a capability that underpins search and probability-estimation tasks. Unlike classical databases—where writing a WHERE clause is easy but scanning is costly—quantum workflows make the search step cheap (for example with Grover’s algorithm) once an efficient oracle is available, making oracle design the hard and crucial part. The chapter motivates oracles with practical contexts such as unstructured search, optimization, and sampling, and frames them as a universal tagging mechanism: they identify outcomes that satisfy a desired predicate so later algorithmic steps can amplify, isolate, or measure them.

Two oracle styles are developed. Phase oracles flip the phase of marked amplitudes, while bit oracles entangle marked outcomes with an extra “tag” qubit that reads 1 for good and 0 for bad. The text first builds classical, state-vector-level versions to build intuition, then constructs true quantum circuits in a Python simulator. Readers learn to assemble reusable subcircuits with append and controlled-append, employ multi-controlled gates, and manage ancilla qubits. Practical helper routines create phase and bit oracles from a set of target items, and examples show their effects on uniform and random states, reinforcing how amplitude signs or tag-bit populations encode the predicate without measuring the data qubits.

The chapter also shows how to convert between oracle types: a bit oracle can be realized from a phase oracle by controlling it with an ancilla prepared in superposition, and a phase oracle can be synthesized from a bit oracle by sandwiching a phase rotation on the tag between two calls to the bit oracle. A thematic example marks outcomes whose binary strings have no consecutive ones, revealing that the count of “good” states follows the Fibonacci sequence and that carefully chosen rotations can concentrate probability on exactly those outcomes, with probability ratios tied to the golden ratio. By the end, readers have both the conceptual model and concrete Python circuits needed to define, implement, and interchange oracles—foundational pieces for Grover’s algorithm and many optimization and machine-learning workflows that follow.

A dependency diagram of concepts introduced in this chapter. Oracles are also an essential building block of Grover’s algorithm, covered in the next chapter.

The effect of a phase oracle on the amplitudes of a state with good outcomes $g$ and bad outcomes $b$.

The effect of a phase oracle on a $n = 3$ qubit state prepared with amplitudes in equal superposition and a single good outcome 3.

The effect of a bit oracle on the amplitudes of a state with good outcomes $g$ and bad outcomes $b$.

The effect of a bit oracle on an $n = 3$ qubit state prepared with amplitudes in equal superposition and a single good outcome 3.

The effect of a bit oracle on a random $n = 3$ qubit state with a single good outcome 3.

The phase oracle circuit for $n = 3$ qubits and a single good outcome 3.

The state tables before and after applying a circuit that applies a Hadamard gate to each of $n = 3$ qubits followed by the phase oracle for a single good outcome 3.

The state tables before and after applying a circuit that applies a Hadamard gate to each of $n = 3$ qubits followed by the phase oracle for good outcomes 1, 3, and 5.

The state tables before and after applying a circuit that applies a Hadamard gate to each of $n = 3$ qubits followed by the bit oracle for a single good outcome 3.

The state tables before and after applying a circuit that applies a Hadamard gate to each of $n = 3$ qubits followed by the phase oracle for good outcomes 1, 3, and 5.

Circuit diagram of a bit oracle using the corresponding phase oracle $O_P$.

Circuit diagram of the phase oracle $O_P$ for $n = 3$ qubits and good outcomes 1, 3, and 5.

Circuit diagram of the bit oracle created using the phase oracle $O_P$ for $n = 3$ qubits and good outcomes 1, 3, and 5 in figure 5.12.

The state tables before and after applying the bit oracle in figure 5.15 to a random $n = 3$ qubit state.

Circuit diagram of a phase oracle using the corresponding bit oracle $O_B$.

Circuit diagram of the bit oracle $O_B$ for $n = 3$ qubits and good outcomes 1, 3, and 5.

Circuit diagram of the phase oracle created using the bit oracle $O_B$ for $n = 3$ qubits and good outcomes 1, 3, and 5 in figure 5.19.

The state tables before and after applying the phase oracle in figure 5.20 to a random $n = 3$ qubit state.

Table 5.2 A single-qubit state with good outcomes $G_1$.

Table 5.3 A two-qubit state with good outcomes $G_2$.

Table 5.4 A three-qubit state with good outcomes $G_3$.

Summary

To solve problems that search for specific outcomes or estimate the probability of specific outcomes, we need mechanisms to identify outcomes of interest.
The quantum circuits used to identify certain outcomes, which we call "good" outcomes, are called oracles.
Phase oracles rotate the amplitudes of the good outcomes by $180^\circ$.
Bit oracles entangle good outcomes with an additional qubit in such a way that the good ones are associated with its measurement of 1, and the bad ones with its measurement of 0.
We can convert from a bit oracle to a phase oracle and vice versa.

FAQ

What is a quantum oracle, and why is it important for search and estimation tasks?

A quantum oracle is a circuit that recognizes “good” outcomes and tags them so downstream algorithms can find or amplify them. It plays the role of a predicate (like a SQL WHERE clause) but in quantum form. In unstructured search, specifying the oracle efficiently is the hard part, while the search or amplification (for example with Grover’s algorithm) is comparatively easy.

What’s the difference between a phase oracle and a bit oracle?

- Phase oracle: multiplies the amplitudes of good outcomes by −1 (a 180° phase flip).
- Bit oracle: entangles good outcomes with an extra “tag” qubit so that good outcomes correlate with measuring the tag qubit as 1, and bad ones with 0.

How do I specify “good” outcomes programmatically?

Define a classical predicate over the integers 0..2^n−1 that returns True for good items and False otherwise (for example, lambda k: k in [1, 3, 5]). This predicate is used both in classical simulations (for intuition) and to construct the corresponding quantum oracle circuits.

How does a classical phase-oracle simulator work?

Given a state vector and a predicate, it scans all indices and multiplies by −1 the amplitudes whose indices satisfy the predicate. This mirrors the 180° phase rotation that a quantum phase oracle applies to good outcomes.

How does a classical bit-oracle simulator work, and how are indices arranged after adding a tag qubit?

It appends amplitudes for the extra qubit, doubling the state length from N to 2N. Outcomes 0..N−1 correspond to tag=0; outcomes N..2N−1 correspond to tag=1. For each good item k, it moves the amplitude from index k to index N+k (setting the original to 0), so measuring the tag qubit as 1 points to good outcomes.

How do I assemble oracle circuits from reusable building blocks in the simulator?

Use QuantumCircuit.append to apply a reusable subcircuit to a register of matching size, and QuantumCircuit.c_append to append it controlled on an external qubit. Multi-controlled gates are available via methods like mcx (multi-controlled X) and mcp (multi-controlled phase), following Qiskit conventions.

How do I implement a phase oracle circuit from a list of good outcomes?

For each good item m: (1) X-flip qubits whose corresponding bits in m are 0 to align the all-ones pattern, (2) apply a multi-controlled phase of π (e.g., mcp(pi,...)) on the most significant target, and (3) uncompute the X flips. Repeating this for every item yields a circuit that flips the sign of all tagged amplitudes.

How do I implement a bit oracle circuit from a list of good outcomes?

Add an ancilla (tag) qubit. For each good item m: (1) X-flip the “0” bits of m, (2) apply a multi-controlled X (mcx) targeting the ancilla, and (3) uncompute the X flips. Measuring the ancilla as 1 identifies the good subset.

How do I convert between phase and bit oracles?

- Phase → Bit: Prepare an ancilla with H, apply the phase oracle controlled on the ancilla (c_append), then H the ancilla again. This turns the phase mark into a measurable tag bit.
- Bit → Phase: Apply the bit oracle, then a Z/phase-π on the ancilla, then uncompute with the bit oracle. The phase “kicks back” to good items, producing a phase oracle.

Why do Fibonacci numbers and the golden ratio appear in this chapter?

Define good outcomes Gₙ as n-bit strings with no consecutive ones. Their count satisfies |Gₙ| = |Gₙ₋₁| + |Gₙ₋₂|, so |Gₙ| = Fₙ₊₂ (Fibonacci). A tailored circuit (fib_circuit) prepares states where bad outcomes are suppressed and the ratio between probabilities of good outcomes starting with 1 versus 0 approaches the golden ratio (1+√5)/2.

pro $24.99 per month

access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
choose one free eBook per month to keep
exclusive 50% discount on all purchases
renews monthly, pause or cancel renewal anytime

lite $19.99 per month

access to all Manning books, including MEAPs!

team

5, 10 or 20 seats+ for your team - learn more

eBook

pdf, ePub, online

$64.99 $32.49

you save $32.50 (50%)

include audio $24.99 $12.49

pro $24.99 per month

access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
choose one free eBook per month to keep
exclusive 50% discount on all purchases
renews monthly, pause or cancel renewal anytime

lite $19.99 per month

access to all Manning books, including MEAPs!

team

5, 10 or 20 seats+ for your team - learn more

eBook

$64.99 $32.49

you save $32.50 (50%)

include audio $24.99 $12.49

eBook

pdf, ePub, online

$64.99 $32.49

you save $32.50 (50%)

include audio $24.99 $12.49

pro $24.99 per month

access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
choose one free eBook per month to keep
exclusive 50% discount on all purchases
renews monthly, pause or cancel renewal anytime

lite $19.99 per month

access to all Manning books, including MEAPs!

team

5, 10 or 20 seats+ for your team - learn more