2 A first look at quantum computations: the knapsack problem
The knapsack problem is a binary optimization problem where the optimal solution is the collection of items with the highest value that does not exceed the weight limit.
The steps of a quantum computation.
The outcome of running a quantum program is a binary string.
Three registers encoding an item selection, its total value, and its total weight for solving the knapsack problem.
A rose chart representation of the probabilities associated with the outcomes of a three-qubit quantum system.
Table 2.3 The possible outcomes of a three-qubit system and the corresponding probabilities.
An elementary quantum intsruction (gate) recombines pairs of amplitudes.
Three registers encoding an item selection, its total value, and its total weight for solving the knapsack problem.
The register for encoding item selections.
Table 2.5 The selection register outcome probabilities after looking for selections with a maximum weight of 4 and a minimum value of 3.
Table 2.6 The selection register outcome probabilities after looking for selections with a maximum weight of 4 and a minimum value of 4.
Map of quantum concepts implemented in Hume.
Summary
Binary optimization problems are an ideal candidate for efficient quantum computing solutions.
The output of one execution (run) of a quantum computation can be interpreted as a binary string, with one digit for each qubit in the system.
The state of a quantum system (quantum state) consists of a value, called an amplitude, for each possible outcome. The corresponding amplitude determines the probability of an outcome.
We change the amplitudes, and therefore the probabilities, using elementary quantum instructions called quantum gates.
To solve several types of problems—including optimization problems—using a quantum computation, the goal is to increase the probability of desired outcomes. We do this using a process called amplitude amplification.
FAQ
Do I need a background in quantum mechanics to follow this chapter?No. The chapter assumes no prior knowledge of quantum mechanics or quantum hardware. You only need familiarity with binary strings, complex numbers, and basic trigonometry; quick refreshers are provided as you go.What is the knapsack problem addressed in the chapter?It’s a binary optimization problem: choose a subset of items (include = 1, exclude = 0) to maximize total value without exceeding a weight limit. The worked example uses three items with weights 3, 2, and 1 and values 2, 3, and 1, and a capacity of 4.Why are binary optimization problems challenging for classical computers?The search space grows exponentially. With n binary variables, there are 2^n possible configurations. Even modest n (for example, 41 items) yields over a trillion combinations, making exhaustive search impractical.What are the three steps in a single run of a quantum computation?1) Initialize the qubits to a starting state. 2) Apply gates that evolve the state according to the problem’s criteria. 3) Measure the system, which collapses the state and returns one outcome.What does a measurement outcome look like?Each run yields a binary string, one bit per qubit. Across many runs, you collect a distribution over all possible binary strings (2^n outcomes for n qubits).How are registers used to encode the knapsack problem?The chapter uses three quantum registers: one for the item selection (three qubits, one per item), one to accumulate total value, and one to accumulate total weight. The sizes of the value and weight registers depend on the ranges they must represent.What is a quantum state and how are probabilities determined?A quantum state assigns a complex amplitude to each possible outcome. The measurement probability of an outcome is the squared magnitude of its amplitude. This rule is a postulate of quantum mechanics.How does the quantum approach in the chapter find the optimal selection?It iteratively boosts the probability of feasible selections (within the weight limit) that meet or exceed a target minimum value, measures to obtain a candidate, then raises the target and repeats until no better selection is found. In the example, the optimal selection is items 1 and 2 (total weight 3, total value 4).What roles do the oracle and amplitude amplification play?The oracle efficiently flags states that satisfy the constraints (e.g., weight ≤ max and value ≥ current threshold). Amplitude amplification increases the chances of measuring those flagged states, making good solutions appear more frequently.Which tools and code does the chapter use?The example uses a Python simulator called Hume and a helper function find_optimal_selection(values, weights, max_weight). Hume’s circuits can be converted to Qiskit for simulator or hardware runs, and there’s also a high-performance Rust simulator (Spinoza). A complete Jupyter notebook is available in the book’s companion repository.
pro $24.99 per month
access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
Building Quantum Software with Python ebook for free
