Chapter 7 What is a Quantum Algorithm?

This chapter covers:

  • What is a quantum algorithm?
  • How to designoraclesto represent classical functions in quantum programs
  • A first example of a quantum algorithm
  • Several useful quantum programming techniques

One important application for quantum algorithms is in obtaining speedups for solving problems where we need to search over inputs to a function that we’re trying to learn about. Such functions could be obfuscated (such as hash functions), or could be computationally difficult to evaluate (common in studying mathematical problems). In either case, applying quantum computers to such problems requires us to understand how we program and provide input to quantum algorithms. To learn how to do so, we’ll program up and run an implementation of an algorithm known as the Deutsch–Jozsa algorithm, which will let us learn properties of unknown functions quickly using quantum devices.

Figure 7.1. In this Chapter, we will be covering topics in both the Q# language and intrinsic operations for quantum devices.
CH07 FIGxx mental model

7.1 CLASSICAL AND QUANTUM ALGORITHMS

Algorithm

noun: a step-by-step procedure for solving a problem or accomplishing some end. —Merriam–Webster Dictionary

7.1.1 Quicksort algorithm

7.2 DEUTSCH–JOZSA ALGORITHM: MODERATE IMPROVEMENTS FOR SEARCHING

7.3 LADY OF THE (QUANTUM) LAKE

7.3.1 Kingmaker game rules

7.3.2 Nimue’s objectives

7.3.3 Merlin’s strategies:

7.4 ORACLES: REPRESENTING CLASSICAL FUNCTIONS IN QUANTUM ALGORITHMS

7.4.1 Our strategy for representing classical functions as quantum oracles

7.4.2 Deutsch–Jozsa Algorithm

7.5 SIMULATING THE DEUTSCH–JOZSA ALGORITHM IN Q#

7.6 EXPLORING THE DEUTSCH–JOZSA ALGORITHM BY EXAMPLE

7.7 STEP 1. PREPARING THE INPUT STATE FOR DEUTSCH–JOZSA

7.8 STEP 2. APPLYING THE ORACLE

7.9 STEPS 3 AND 4. UNDO THE PREPARATION ON THE TARGET QUBIT AND MEASURE.

7.10 REFLECTING BACK

7.11 SHOES AND SOCKS: APPLYING AND UNDOING QUANTUM OPERATIONS

7.12 USING HADAMARD INSTRUCTIONS TO FLIP CONTROL AND TARGET

7.13 PHASE KICKBACK

7.14 SUMMARY

sitemap