10 Encoding functions in quantum states

 

This chapter covers

  • Representing integer key–value pairs in quantum states
  • Extending frequency (value) encoding to (polynomial) function encoding
  • Using Grover’s algorithm to search for function values

In classical computing, we can use several data structures to represent pairs, such as attributes and corresponding values or the inputs and outputs of a function. One such data structure is a dictionary, where unique keys are mapped to specific values. In this chapter, we will learn how to represent such integer key–value pairs in a quantum state. We will use two qubit registers: one to represent keys and one to represent values. We will entangle the registers so that if a measurement is performed, the outcome will contain a key paired with its corresponding value.

We will use the frequency-value-encoding method introduced in chapter 8 to encode integer-valued functions by entangling inputs in one register with outputs in another. We encode a value in a single quantum register by creating a geometric sequence state where the encoded value is reflected in the (progression of the) phases of the state’s amplitudes and then applying the inverse quantum Fourier transform (IQFT).

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