2 A first look at quantum computations: The knapsack problem

 

This chapter covers

  • Introducing a quantum solution to an optimization problem: the knapsack problem
  • Examining the steps of a quantum computation, including quantum state evolution and measurement
  • Tools for programming a quantum solution

The material in this book does not depend on any knowledge of quantum mechanics or how to build a quantum computer. Programming quantum computers requires familiarity with a few mathematical concepts, specifically binary strings, complex numbers, and some basic trigonometry and probabilities. We provide an overview of these concepts for readers who are unfamiliar or want a refresher.

Note  Elementary quantum computing instructions can be represented with simple trigonometric expressions. The instructions used for quantum computing are very different from those used in classical software development. For that reason, it’s important to understand the foundational mathematical concepts—complex numbers and basic trigonometry—that are at the core of quantum theory.

In this chapter, we will look at a quantum solution applied to a simple optimization problem. We will cover the relevant concepts as we go through the computation step by step. We will also use this example to familiarize you with some tools used throughout the book.

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