Rock Paper Scissors: A Quantum Computing Twist

TUTORIAL

Having fun with quantum computing games

I love demonstrating the effects of quantum computing. Especially, through games that use quantum superposition and entanglement.

Quantum computing is an incredibly exciting technology that will impact virtually every industry and science. Learning about how quantum computing works, and specifically how it differs from classical computing, can make you a better programmer and a more logical thinker!

So, I thought it would be fun to come up with a game that could be implemented on a quantum computer in order to further demonstrate the differences between quantum and traditional computing.

No shortage of amazing quantum feats

There are many surprisingly powerful (and even confusing!) properties that quantum computers can perform compared to their classical counterparts.

Increased performance from exponential processing power, evaluating multiple scenarios simultaneously, and even something as simple as generating advanced random numbers can all be achieved on a quantum level.

We'll focus on superposition – the technique that allows a quantum computer to evaluate many different scenarios simultaneously. To make it fun – we'll use a game!

Ideas for quantum games

I searched far and wide for ideas of a game that would be simple enough to use, easy enough to play, and yet that can take advantage of quantum processing.

It would also help if this has never been done before!

This led me to the idea of classical games such as tic tac toe, poker, and other games.

While many research papers that combine quantum computing with games often focus on various algorithmic approaches and mathematical complexity, I wanted to create something more easily understandable.

Writing a quantum computing program doesn't have to be difficult.

Once you have an understanding of the various gates and behaviors of qubits, you can create a vast array of quantum applications.

What better way to demonstrate this than with a game of rock, paper, scissors!

Rock, paper, scissors

Rock, Paper, Scissors is a game for two players. The game involves each player secretly choosing an item of rock, paper, or scissors. The players typically count to three and then reveal their hand at the same time.

The rules of the game state that rock defeats scissors, scissors defeats paper, and paper defeats rock.

Simple enough! Or is it?

A mathematical paradox

The underlying principle of rock, paper, scissors is really a measure of weights and values.

We can consider that rock is valued greater than scissors. Likewise, scissors is valued greater than paper. So far, so good.

Rock > Scissors > Paper

Now, if rock is greater than scissors, and scissors is greater that paper, then surely rock is greater than paper as well. However, according to the game rules, paper is valued greater than rock!

Rock > Scissors > Paper > Rock?

It's quite the paradox!

Thinking about this mathematically for a moment

Let's take a step back to consider the paradox that makes the game rock, paper, scissors so unique.

Consider that we have three variables: A, B, and C (representing rock, paper, and scissors respectively). Each variable is assigned a weight such that A > B and B > C. The transitive property of inequality states that according to this arrangement, A > C.

This would lead us to believe that if rock > scissors, and scissors > paper, then rock > paper. Clearly, this is not how the game is played!

In fact, this is the premise behind Hardy's Paradox.

The Hardy Paradox of rock, paper, and scissors

The Hardy Paradox, developed by Lucien Hardy in 1992, examines the situation where three variables that are seemingly aligned in weights of each being greater than the next, can still create a situation where the last variable ends up being greater than the first – violating the transitive property of inequality.

In fact, this type of violation is distinctly possible in the quantum world where particles may become entangled and, in fact, can be found in the game rock, paper, scissors!

I think we've just found the perfect game to demonstrate some of the power behind quantum computing.

Establishing the rules of the game

We're going to create a quantum computing program that can find all winning hands in a game of rock, paper, scissors.

We'll create both a classical and quantum version of the program in order to demonstrate the difference in complexity.

The first thing that we need to do is to encode the items in the game so that we can utilize them in an algorithm. Since each player can choose one of three items (rock, paper, or scissors) during each round of the game, we can have nine different possibilities for game hands.

Let's use the first letter for each item to represent possible choices from each player in a round of the game. Therefore, the possible hands that can be played are shown below.

[RR, RP, RS, PR, PS, PP, SR, SP, SS]

The above list shows all possible hands, beginning with rock versus rock (RR), rock versus paper (RP), rock versus scissors (RS), etc.

Of the above nine possible hands, only three of these are winning choices: rock versus scissors (RS), scissors versus paper (SP), and paper versus rock (PR).

[RS, SP, PR]

Moving to the digital world

Now that we've defined our game choices, we need to convert these choices from letters (R, S, P) into binary digits of zero or one. This is needed so that we can eventually represent the choices as qubits.

Since we have three items, we'll represent them from the values zero to two (00, 01, 10).

# The Items
00 = Rock
01 = Paper
10 = Scissors

It's important to note the binary values that we assign to each item, as we will be referring back to these when looking at the input and output to our programs.

Next, let's define the rules of the game from the perspective of player one.

# Rock
00 vs 00 = Tie
00 vs 01 = Loss
00 vs 10 = Win

# Paper
01 vs 00 = Win
01 vs 01 = Tie
01 vs 10 = Loss

# Scissors
10 vs 00 = Loss
10 vs 01 = Win
10 vs 10 = Tie

Now that we've defined a simple digital definition for each possible game hand, let's start writing some code.

Encoding the game as bits

With our game items defined as binary values, we can now store these values within qubits. Let's create a Python object that defines each item with a corresponding value as listed in the prior section above.

# Encode the choices as qubits.
choices = {
 'rock': [0,0],
 'paper': [0,1],
 'scissors': [1,0]
}

Now, let's see if we can find all possible winning moves that can be made.

Creating a logical expression for the win

We've already defined a representation for each choice (rock 00, paper 01, scissors 10). Since we have two players, there would be four bits per round.

A single round of the game might appear as shown below.

Player 1 chooses Rock. Player 2 chooses Paper. Rock = 00 and Paper = 01

The input would be 0001.

In order to determine if this is a winning move for player one, we need to check some logic that dictates the rules of the game.

The game rules state that rock defeats scissors, scissors defeats paper, and paper defeats rock.

We can encode these rules using Boolean logic.

bool isWin = (rock and scissors) or (scissors and paper) or (paper and rock)

The slow way to find all winning hands

Let's begin by writing a classical computer program to find all winning hands.

We can create a method called _check_allgames() that loops through a list of all possible combinations of items and returns only those that are winning hands for player one.

def check_all_games():
    # Generate a list of all possible game choices for player1 and player2.
    result = []
    count = 0

    games = list(itertools.product([0, 1], repeat=4))
    for game in games:
        # Example: (1, 0, 0, 1) => scissors vs paper
        player1 = list(game[0:2])
        player2 = list(game[2:4])

        # A quick check to make sure both player moves are valid.
        if player1 in list(choices.values()) and player2 in list(choices.values()):
            # ...
            is_win = isWin(player1, player2)
            if is_win:
                result += [game]

        count += 1

    return (result, count)

([(0, 0, 1, 0), (0, 1, 0, 0), (1, 0, 0, 1)], 16)

The method returns the list of winning hands including rock versus scissors, paper versus rock, and scissors versus paper. It also returns the number of iterations that it took to search through all combinations.

(0, 0, 1, 0) = rock (0, 0) vs. scissors (1, 0) (0, 1, 0, 0) = paper (0, 1) vs. rock (0, 0) (1, 0, 0, 1) = scissors (1, 0) versus paper (0, 1)

Did you notice that this required 16 iterations to find all winning games? Not to mention, the iterations include invalid bit combinations, such as [1, 1, 1, 1] – which do not even correspond to a valid item!

Can quantum do better?

Let's try this again. However, this time we're going to create a quantum computing program to find all winning hands.

In the same manner as the classical program, we'll define a function isWin() that encodes the rules of the game.

A black box quantum circuit that encodes some specific set of logical rules (such as the rules for winning in our game), is called an oracle.

Since our oracle will work with binary values of 0 and 1, rather than variable names, let's just rewrite our logical expression using these values.

bool isWin = (00 and 10) or (01 and 00) or (10 and 01)

Also, since we will be using the quantum computing library Qiskit, we will need to represent the qubits in reverse order. Therefore, we'll arrange our logic accordingly by swapping the positions of the right and left bits.

[(0, 0, 1, 0), (0, 1, 0, 0), (1, 0, 0, 1)]
[(q1 q0 q3 q2),(q1 q0 q3 q2),(q1 q0 q3 q2)]

The first row is our result of winning hands, as returned from our classical program. We're just representing each bit with a qubit (indicated as q0, q1, q2, q3). The qubits are arranged in reverse order so that the first two bits are player one, and the last two bits are player two. Each player's qubits are arranged with the least-significant bit to the right and the most-significant bit to the left (corresponding to [q1, q0] and [q3, q2]). We repeat this for all three of the winning hand combinations.

Creating an oracle

Let's create the oracle for our quantum computing solution.

Just as we did with the classical program, we will encode the rules of the game using Boolean logic. The difference this time, however, is that we're referring to q0, q1, q2, q3 to represent rock, paper, scissors.

For example, the first type of winning hand encoded within our oracle is for rock versus scissors. We can encode this as shown below.

Rock versus scissors (0, 0, 1, 0) (q1 q0 q3 q2)

First winning hand condition (not q0 and not q1 and not q2 and q3)

Reversing the qubit order (not q1 and not q0 and q3 and not q2)

Converting to binary (00 versus 10)

Converting to a game round (rock versus scissors)

# Define a classical logical circuit with 4 variables (qubits).
isWin = 'def isWin(q0: Int1, q1: Int1, q2: Int1, q3: Int1) -> Int1:n  return (not q0 and not q1 and not q2 and q3) or (q0 and not q1 and not q2 and not q3) or (not q0 and q1 and q2 and not q3)'

# Convert the logic to a quantum circuit.
formula = ClassicalFunction(isWin)
fc = formula.synth()

# Convert the quantum circuit to a quantum program.
qc = QuantumCircuit(4+1)
qc.compose(fc, inplace=True)

All winning hands are encoded in the oracle with one line of Boolean logic. This creates a quantum computing circuit that can be used within our program to find all winning hands!

Putting this all together, we can create a quantum computing program using this oracle.

# Get the number of qubits needed.
n = len(choices['rock']) * 2

qc = QuantumCircuit(n + 1, 1)

# Paper vs Rock.
qc = encode('paper', 'rock', qc)

# Append the rock, paper, scissors oracle.
qc.append(oracle, range(5))

# Measure the result!
qc.measure(4, 0)

In this example, we're playing a single round of the game with paper versus rock. In the resulting quantum computing program, notice that the first qubit (q0) is inverted using the X-Gate to a value of one, and the second qubit (q1) is left with a value of zero. This corresponds to (01) which represents paper. Similarly, qubits three and four (q2 and q3) are left as zero (00), corresponding to rock.

This is a game of paper versus rock.

The result of our quantum computing program returns an output indicating if this is a winning hand. Since the output of qubits are in reverse order (remember, we're reading from right to left!), I've highlighted an example along with notation that explains each qubit value below.

1 00 01
^- win
  ^^----- rock
     ^^--------paper

Running the quantum computing program

Let's run the program and see the result. Since paper always defeats rock, we would expect our program to output a value of one across all measurements of the quantum program.

simulator = Aer.get_backend('aer_simulator')
job = execute(qc, simulator)
result = job.result()
counts = result.get_counts()

key = max(counts, key=counts.get)

print(counts)
plot_histogram(counts)

{‘1': 1024}

Indeed, we can see that all measurements result in a strong value of one. This indicates that paper versus rock is a win for player one!

Similarly, we can run the same oracle against a game round of paper versus scissors. In this round, we would expect the result to be zero, since paper is always defeated by scissors.

# Rock vs Scissors.
qc = encode('paper', 'scissors', qc)

{‘0': 1024}

Once again, we've obtained a correct answer, indicating that this is a loss for player one.

Well, so far, we're only determining if a single round of the game is a win for player one. That's not very impressive. After all, our classical program found all winning hands (albeit it took 16 iterations to calculate this!).

Can we find all winning hands?

The power of quantum processing

As it turns out, since we've created a quantum oracle that encodes the winning hands of our game, we can in fact calculate all winning hands. Even better, we can do this in just one single CPU cycle!

Instead of hard-coding our qubits with a specific value of zero or one, which corresponded to a particular item choice of rock, paper, scissors for each player, we will place the qubits into superposition. This changes the qubits from a value of 0 or 1 to a value of 0 and 1 at the same time!

By using superposition, we can evaluate all possible game hands in one single execution and only return those winning hands that satisfy the oracle Boolean logic.

Here is an example for how this is done.

qc = QuantumCircuit(n + 1)

qc.h(range(n))

# Append the sudoku oracle.
qc.append(oracle, range(n+1))

# Measure the result!
qc.measure_all()
qc.draw(output='mpl')

Notice that we've omitted hard coding a specific item for player one and player two. Instead, we're using the Hadamard Gate to place all four qubits into superposition so that they hold a value of both 0 and 1 simultaneously.

This results in a quantum computing circuit as shown above. If we run this program we should expect to see an indication of all winning hands that satisfy the oracle Boolean logic.

In the results, the most significant qubit (the left-most or downward-most) is a value of 0 (loss) or 1 (win). So, we're concerned with the 3 wins at the far right of the graph.

However, this doesn't appear quite right!

In fact, all possible combinations of qubit values appear to be completely random.

Grover search to the rescue

As it turns out, when search across a space of qubits in superposition with an oracle, we need to amplify the measurement results for winning hands that satisfy the oracle, while minimizing losing hands that do not satisfy the oracle.

We can do this using the Grover search quantum algorithm.

Grover's search algorithm utilizes a diffuser and amplification process that allows correct results to "float" higher, while incorrect results remain low. It can be used for searching for a key within a database of unordered items and searches quadratically faster than any classical algorithm.

After running this new circuit using the Grover search algorithm, along with our same oracle for rock, paper, scissors, we can see the following change in output.

Examining the above results, we indeed have three results that are far higher than the rest of the combinations. In fact, these correspond directly to the winning moves in the game!

If we decode each result, beginning from the left-most in the chart, and reversing the bits that Qiskit returned as output, we can determine the winning hands. Recall, the top-most bit is the least-significant bit and corresponds to Player One.

0001 = paper (01) vs rock (00) = WIN 0110 = scissors (10) vs paper (01) = WIN 1000 = rock (00) vs scissors (10) = WIN

0001 => 01 versus 00 => paper versus rock => WIN
   ^-  q0
  ^--- q1
 ^---- q2
^----- q3

The most amazing part about this is that the classical program took 16 iterations to find these three winning combinations. The Quantum Computing program took just one!

One more bit of fun

We've just examined how a quantum computing program can find all winning moves in the game rock, paper, scissors with just a single execution on the CPU. We did this by placing the qubits into superposition.

However, by playing with which qubits are in and out of superposition, we can actually create different behaviors of our program.

For example, suppose that we want to find the best move for player one when given a specific choice by player two. We can do this by setting player one's qubits into superposition and leaving player two's qubits hard-coded to a specific value.

If we now run the quantum program, instead of seeing three results with high measurements (corresponding to all winning hands), we should expect to see just one high measurement, which will correspond to the winning hand that player one should choose in order to defeat player two.

In the above scenario, we're assigning player two the choice of rock (00). Let's see what the quantum program selects as its move!

The result indicates (0001). Reading from least to most significant bits, this evaluates to player one choosing paper (01) whenever player two chooses rock (00). Making this move is, indeed, a winning play for player one!

Paper defeats rock!

You can download the complete code example for the rock, paper, scissors program here.

It's your turn

Now that we've completed a quantum computing program to find all winning moves in the game Rock, Paper, Scissors, let's think for a moment what we've achieved.

A classical program took 16 iterations to find all winning hands. By contrast, a quantum version using Grover's search executed in just 1 single iteration. This is just one of the fantastic differences between how classical and quantum computers work.

Grover's search can be applied to many different searchability problems, including algorithms, file systems, and databases, just to name a few. Additionally, since the field of quantum computing is still so young, you have the real opportunity to make an impact.

I hope that your excitement is piqued into learning more about this amazing technology. Now it's your turn!

About the Author

If you've enjoyed this article, please consider following me on Medium, Twitter, and my web site to be notified of my future posts and research work.

Tags: Hands On Tutorials Programming Qiskit Quantum Computing Quantum Physics

Comment