Take quantum computing from theory to practice with Amazon Braket

Take quantum computing from theory to practice with Amazon Braket In this post, we’ll explore quantum computing using Amazon Braket. We’ll take an educational approach for this by using a well-known quantum algorithm, Grover’s algorithm. We’ll first explain how Grover’s algorithm works, then we’ll introduce the dinner party problem which involves identifying a set of friends that can be invited together to a party satisfying a set of constraints. And then we’ll explain how Grover’s algorithm can be used to solve it.

Grover’s algorithm is a widely cited and historically important quantum algorithm. It was a significant early milestone that helped demonstrate the potential power of quantum computers. It’s arguably almost as well-known as Shor’s factoring algorithm. It’s primarily used for searching in unstructured search spaces and provides a quadratic speedup over classical algorithms for this category of problems. Theoretically it can be applied to areas like cryptanalysis, optimization problems, machine learning, or quantum simulation. While the practical use of Grover’s algorithm is currently limited by the availability of large-scale, fault-tolerant quantum computers, it’s a great choice for learning and exploring ideas involved in quantum computing.

Background

Since the 1980s, quantum computing emerged as a new computing paradigm with the promise to surpass the speed of machines based on classical physics. For a gentle introduction to this new paradigm, see this excellent article from The New Yorker. It explains in simple language the key ideas behind quantum computing that make it different from the ‘classical’ computing (today’s computers are classical), its current limitations, and its promise to potentially revolutionize a lot of industries.

Amazon Braket Service for building QC Algorithms

Amazon Braket is a cloud service that accelerates quantum computing research by letting customers seamlessly build, test, run, and analyze results, leveraging different types of quantum computers and simulators. You can use the AWS console (Figure 1) or your local development environment with the Braket SDK or one of its software integrations to access the service. In addition, for researchers and customers new to quantum computing, the Amazon Braket Algorithm library offers an open-source GitHub repository providing customers with ready-to-use Python code for some of the most famous quantum algorithms.

Figure 1: Amazon Braket Service dashboard

Unsorted search on classical computers, and the idea of “oracles”

Let’s first see how classical computers search a number in an unsorted list. As an example, given an unsorted array [3,6,1,9,7,8,5,0,2,4], we need to write an algorithm that finds the index at which the number ‘8’ is sitting. Checking one-by-one from left to right would take six tries in this list to find it at index 5.

Checking for the match can be seen as a call to a function which returns True if the input is 5, else returns False. If we start from index 0 and go sequentially, we’d call the function six times before we found 8 at index 5 in the list. On average, we’ll need to check in the range of N numbers N/2 times. In other words, it has time complexity of O(N). However, on a quantum computer, you can perform this search in time complexity of O(√N) using Grover’s algorithm.

Oracles

An ‘oracle’ is a function that entirely contains the validation logic that defines the search problem. An example is the function we just mentioned in the previous paragraph. Such operations can be defined as a classical Boolean function f:{0,1}ⁿ→{0,1}, which takes an n-bit binary input and – for this discussion – produces a 1-bit binary output.

So, considering our example problem again, we want a function, f, that takes an index between 0-9, and returns True if the item at the indexed position is 8 in the underlying array, i.e. f(5) = True.

Quantum oracles

Oracles in quantum computing are implemented by quantum functions, all of which are unitary operations whose inputs and outputs have the same number of qubits. As shown in Figure 2, for a quantum oracle with n input qubits and 1 output qubits, we need to send in both the input qubits and the output qubits to the oracle, so we need n+1 qubits. In addition to these, the oracle might use additional l qubits as work qubits that hold some intermediate values during the computation. Thus, the oracle would use n+1+l qubits in total.

Figure 2: Quantum oracle with a binary output

Unsorted search on quantum computers – Grover’s algorithm

Now, on to unsorted search on quantum computers using Grover’s algorithm. Let’s look at how this algorithm takes advantage of superposition, entanglement, and interference in quantum computers to perform the search more efficiently than classical computers.

At the heart of Grover’s algorithm are two operators: the oracle and Grover’s diffusion operator. Let’s go over each of these in the next sections.

The oracle

For the problem of searching in a range, the oracle on a quantum computer takes as input, a number encoded in binary, and toggles an output qubit if the input number is the correct answer (e.g. f(5) = True in our example where we’re searching for the index of 8 in the array [3,6,1,9,7,8,5,0,2,4]).

However, the qubits can be in a superposition of multiple bit-strings. If the input is in such a superposition, the quantum oracle puts the output qubit also in a superposition, such that the output qubit is toggled/not-toggled, in alignment with the individual states in the input superposition. The output qubit gets entangled with the input qubits.

Let’s illustrate that using an oracle with 2 qubits as input and 1 qubit as output. The input can have 4 possible values, and if the input is in a uniform superposition of these, it will be as follows (where square of amplitudes of all states must add up to 1):

If we initialize the output qubit to |0⟩, the overall state at the beginning will be as follows (the output qubit is shown as most-significant):

Suppose the number the oracle matches is 2 (i.e., |10⟩), so, f(2) = True, and f(0)=f(1)=f(3)=False. With this, state after the oracle operator would be:

Note that the qubits are now entangled: the output qubit is |1⟩ only when the input qubits are in |10⟩ state, and |0⟩ otherwise.

This seems to already solve the search problem, right? No. To be able to find out the qubit values for which the output qubit is |1⟩, we’ll have to perform a measurement operation. Since the amplitudes of all the states is the same, we have equal probability of measuring any one of these answers. If we have n qubits, addressing 2ⁿ=N input bit combinations, the amplitudes would be 1/√N, and the probability (square of the amplitude) of measuring the state with output qubit as |1⟩ is 1/N, i.e., still O(N) tries required; so, no real benefit so far.

To bring about the promised speedup, Grover’s algorithm uses the mentioned diffusion operator along with an oracle to increase the amplitude of the desired state, and in doing so increases the probability of measuring that state.

Phase kickback

Let’s cover one more useful concept in the context of oracles: the phase kickback.

Say an oracle, only for a particular input state |m⟩, toggles the output qubit. That is,

Now consider the situation where the output qubit is not in state |0⟩ but is instead prepared to be in superposition state 1/√2 (|0⟩ -|1⟩) (also known as |-⟩ state). Applying the oracle operation to this results in an interesting outcome as follows,

As you see, the operation changes the sign of the overall state, which is the same as leaving the output qubit as-is, and inverting the sign of the input state |m⟩.

Figure 3: Oracle operator with phase kick-back, visual depiction of phase-kick-back

Thus, if the input is in a uniform superposition of all states, the oracle inverts the sign of |m⟩, leaving all others unchanged. We can plot the amplitudes of the states before and after the operator, as we’ve done in Figure 3.

Diffusion operator

This second operator, known as the diffusion operator, or amplitude amplification operator is the key idea behind Grover’s algorithm.

The diffusion operator essentially creates a series of rotations which amplifies only the phase flipped state. This operator – used along with the oracle with phase-kickback – amplifies the amplitude of the target state as depicted in Figure 4.

Figure 4: Amplitude amplification by Grover’s diffusion operator

Grover’s diffusion operator can be described as ‘flipping the amplitudes around the mean’. Let’s illustrate the concept using a simple example. Let’s say we have the input in an equal superposition as:

and we want to find the 3^rd element. Note that generally the amplitudes will be complex but we’re using real numbers here for simplicity.

By applying the oracle (along with phase kickback), the 3^rd amplitude’s sign is changed

The mean of these amplitudes is

Applying Grover’s diffusion operator flips all the amplitudes around this mean. So, for an initial amplitude a, the resulting amplitude will be 2*avg – a. Thus, for a=1/2, the resulting amplitude is 0, and for a=-1/2, it’s 1. Hence, the overall the result is

We can now see that the 3^rd element’s amplitude is amplified, hence increased the probability of measuring the correct element – in this example to a probability of 1.

So, by applying this pair of oracle and diffusion operators repeatedly, it’s possible to amplify the amplitude of the target state till it gets to, or very near, 1. Performing measurement now yields the result m with a high probability.

Figure 5: Grover’s Diffusion Operator

Figure 5 shows a diagram of the diffusion operator. Hⁿ is the Hadamard gate individually applied on each of the n qubits, U_≠0 inverts the phase of the input qubits if the input qubits are not |00…0⟩.

Putting it all together

Putting it all together, the quantum circuit for Grover’s algorithm is as we’ve depicted in Figure 6, and its sequence of five steps are explained like this:

Initialize: Input register qubits are put in uniform superposition of all states by applying H gate to each of those qubits. This leads to all the input register states having equal amplitude. Also, to effect phase kick-back, the output qubit is put in |-⟩ state by applying the X gate followed by the H
Oracle operator: The oracle operator takes the input register and, for the target bit string, toggles the output qubit, but not otherwise. As explained earlier in the section on phase kickback, with the output qubit being in |-⟩ state, the target’s amplitude sign gets flipped.

Diffusion operator: The diffusion operator is the key trick behind Grover’s algorithm: it flips every amplitude around the mean amplitude. As we explained, that increases the amplitude of the target.
Repeat: The pair of oracle and diffusion operators are applied repeatedly π/4 √(2ⁿ ) times to amplify the amplitude of the target. In a more general case, if the oracle identifies more than 1 targets, say t targets, they need to be applied only π/4 √(2ⁿ/t) times.
Measurement: Finally, a measurement operation is performed on the input register. Since the amplitude of the target is nearly 1, the measured bit string is nearly certain to be the target.

Figure 6: Quantum circuit for Grover’s algorithm

Dinner party problem

Let’s now look at using Grover’s algorithm to solve a problem known as the dinner party problem, which can be cast into a search problem suitable for Grover’s algorithm.

The setup of this problem is to select a set of friends to invite for a dinner party while satisfying certain constraints. The constraints specify friends who get along well (so can be invited together) and friends who don’t get on (so can’t be invited to the same dinner).

It turns out that to solve this requires exponential time in terms of the number of friends – i.e., you have to check all combinations of friends (2ⁿ combinations, for n friends). However, if we’re given any one specific combination of friends, we can determine efficiently if that combination meets all the constraints, or not.

This is a Boolean satisfiability problem which belongs to the NP-Complete set of problems for which the correctness of each input can be verified quickly, and a brute-force search algorithm can find a solution – by trying all possible inputs.

Getting ready with a Jupyter notebook on Amazon Braket

Let’s first get ready with a Jupyter notebook on the Amazon Braket service. We’ve provided instructions, with screenshots, in the create-notebook.md in our repo on GitHub. The instructions in brief are as follows. For clarity, we’re assuming you’re logged in to the us-west-2 AWS region.

Login to the AWS console.
Type Braket in the services search box, and then click on Amazon Braket in the results dropdown.
On the Braket console view, click on Notebooks in the left side panel.
Next, click on the Create button under the Standard notebook If you have some pre-existing notebooks, you’ll see a button called Create notebook instance. Click that.
On the next screen, fill in a name for your Jupyter notebook, like grovers-algorithm. Keep all the other values as default, and click on the Next button at the bottom.
Follow subsequent pages, keeping the default values on each page. On the last page, click on the Launch
After several minutes, the notebook will be ready and you’ll see a regular Jupyter notebook interface.

Developing the solution on Amazon Braket

Let’s start with defining the parameters of the problem. For this instance of the problem we need to select from 3 friends, creatively named 0, 1, and 2. The constraints for selecting from among them are that:

0 and 1 can be invited together
0 and 2 can be invited together
but 1 and 2 cannot be invited together – perhaps because they don’t like each other

While each of these constraints has only 2 people, in general for a larger problem the constraints will involve many more people. Perhaps your friends Alice and Bob gang up and pick on your other friends Charlie and David if they see them together, and you don’t want that to happen in your party.

Lastly, it’ll be a good idea to have at least someone turn up to the party, so we should include that when coding the constraints.

We’ll build an oracle and then use that to setup the circuit for Grover’s algorithm to find the solution.

What follows refers to code from a Jupyter notebook called grovers search - party problem.ipynb which you can find in our GitHub repo. We encourage you to download it and follow along using your own AWS account. You can also run this using your local development environment with Jupyter and the Amazon Braket SDK installed.

Let’s first set up our qubit registers – input, work, and output – as follows. These registers are shortcuts to refer to the qubits we used for those purposes.

inreg = [0,1,2]
work = [3,4,5,6,7]
outreg = [8]

We then need to create the oracle for this problem. Given the constraints for the 3 friends, the following snippet encodes a function that returns a quantum circuit that implements the oracle’s Boolean logic:

def party_oracle(inreg,outreg,work):
    partyckt = Circuit()
    # Invite ((0 and 1) or (0 and 2)) and NOT (1 and 2)
    qand(partyckt,[inreg[0], inreg[1]], work[0])
    qand(partyckt,[inreg[0], inreg[2]], work[1])
    qor(partyckt, [work[0], work[1]], work[2])
    qand(partyckt, [inreg[1], inreg[2]], work[3])
    partyckt.x(work[3])
    qand(partyckt, [work[2], work[3]], work[4])
    partyckt.cnot(work[4], outreg[0])
    # cleanup the work qubits
    qand(partyckt,[work[2],work[3]], work[4])
    partyckt.x(work[3])
    qand(partyckt, [inreg[1],inreg[2]], work[3])
    qor(partyckt, [work[0], work[1]], work[2])
    qand(partyckt, [inreg[0], inreg[2]], work[1])
    qand(partyckt, [inreg[0], inreg[1]], work[0])
    
    return partyckt

The utility functions qand and qor implement the Boolean and and or functions using quantum gates. The code for these is present in the Jupyter notebook you downloaded earlier. To implement the logic for the oracle, we needed 5 additional qubits that comprise the work register, which we clean up (we return them to their initial states), after the computation.

Next, we’ll use another function to create the circuit for the diffusion operator.

def diffusion_op(inreg, outreg):
    # diffusion operator
    diff = Circuit()
    diff.h(inreg)
    diff.x(inreg)
    diff.cnx(inreg + outreg)
    diff.x(outreg)
    diff.x(inreg)
    diff.h(inreg)

    return diff

Finally, we need a function that creates the circuit to initialize the input and output qubits. This puts all the input qubits in uniform superposition, and the output qubit in |-⟩ state.

def prepare(inreg, outreg):
    prep = Circuit()
    prep.h(inreg)
    prep.x(outreg)
    prep.h(outreg)
    return prep

Now we’re ready to assemble the entire Grover circuit for this problem. The next snippet shows the function that creates that circuit, and shows the overall circuit, too:

def grover_ckt(inreg, outreg, work,n_reps):
    gckt = prepare(inreg, outreg)
    for i in range(n_reps):
        ora = party_oracle(inreg, outreg,work)
        gckt.add(ora)
        diff = diffusion_op(inreg, outreg)
        gckt.add(diff)
    gckt.probability(target=inreg)

    return gckt

For now we can use a cheat we happen to know in advance: there are two solutions to this dinner party problem. This means the number of iterations turns out to be 1. Given that, we call the following function to assemble the Grover circuit:

groverckt = grover_ckt(inreg,outreg,work,n_reps=1)

The algorithm to determine the number of solutions (the quantum counting algorithm) is a topic in itself which we won’t cover here.

Running this circuit, and plotting the probability of values measured, looks like this:

# set up the local simulator
device = LocalSimulator()

# Run on this device
probs = get_result(groverckt, device)

# Plot the probabilities measured
show_probs(inreg, probs)

The results therefore are to either invite friends 0 and 2, or friends 0 and 1. Figure 7 shows the probabilities measured at the end of the run, from which we’ve concluded this.

Figure 7: Probabilities measured at the end of the run

Conclusion

In this post, we hope you learned some fundamentals of quantum computing and how Amazon Braket works to build and implement quantum algorithms.

We explored one of the fundamental quantum algorithms used for unsorted search, Grover’s algorithm. The companion Jupyter notebook – well-commented and ready to run – will help you explore different aspects of Braket while you get accustomed to how to use cloud services on AWS to build and explore quantum algorithms. The Jupyter notebook instances in Braket have a link to the Braket Algorithm Library containing an extensive list of algorithms. This is a great resource for quantum developers.

To learn more about quantum programming, quantum simulators and actual quantum computers, you can check our resources pages for Amazon Braket. We also encourage you to look at Braket Direct, and make use of its Office Hours feature. The Amazon Quantum Solutions Lab (QSL) is another resource for helping customers looking to perform larger bodies of work.

We hope this blog post helps you in your quantum computing journey on AWS.

AWS Quantum Technologies Blog