👰🏿 🕸️ 👨‍👨‍👧 The book "Development using quantum computers" 🧞 👨‍🍳 🙍🏿

Hello, habrozhiteli! Quantum computing doesn't just change reality! A completely new industry is being born before our eyes in order to create the unthinkable before and to devalue some of the achievements of the past. This book discusses the most important components of a quantum computer: qubits, logic gates, and quantum circuits, and also explains the difference between quantum architecture and traditional. You can experiment with them for free both in the simulator and on a real quantum device using IBM Q Experience.

You will learn how quantum calculations are performed using QISKit (software tools for processing quantum information), the Python SDK, and other APIs, in particular QASM.

Finally, you will study modern quantum algorithms that implement entanglement, random number generation, linear search, integer factorization, and others. You’ll deal with Bell states describing entanglement, the Grover algorithm for linear search, the Shore algorithm for integer factorization, optimization algorithms, and much more. .

You will learn: • Run programs remotely using the Q Experience REST API. • Write algorithms that provide the highest performance compared to analogs for traditional computers. • Create a REST client on Node.js to authenticate, listen to remote devices, request information about quantum processors, remotely control and run experiments in the cloud. • Use quantum teleportation. Using classical calculations and quantum entanglement between the sender and the receiver, transmit the exact state of the qubit (quantum information). • Program and play the quantum version of Sea Battle. • Use Q Experience Composer to create visual programs / experiments.

Excerpt. Game Theory: With quantum mechanics, the advantage is always on your side

This chapter explores two gaming puzzles that demonstrate the impressive superiority of quantum algorithms over their classic counterparts.

The fake coin riddle. This is the classic weighing problem proposed by mathematician E.D. Shell in 1945. In it, using a laboratory scale for a limited number of weighings, you need to determine a coin whose weight differs from the weight of others (false).
The magic square of Mermin - Perez. This is an example of quantum pseudo telepathy, or the ability of players to achieve results that are possible only if they read each other's thoughts during the game.

In both cases, quantum computing empowers players with pseudo-magical abilities, as if they were cheating all the time. Let's see how this happens.

The fake coin riddle

The player has eight coins and a laboratory scale. One of the coins is false and therefore weighs less than the rest. Can you find her? Let's take a brief look at the solution shown in fig. 7.1.

1. Put coins 1-3 on the left side of the scale, and 4-6 on the right. Set aside coins 7 and 8.

2. If the right side of the scale has outweighed, then false - among coins 1-3 (on the left). Remember that fake coin is easier. Then remove coin 3 and put coin 1 on the left side of the scale and coin 2 on the right.

If the right bowl outweighs, then false - coin 1.
If the left bowl outweighs, then the false one - coin 2.
If the balance is balanced, then false - coin 3.

3. If the left side of the scale has outweighed, then the false one - among coins 4–6. Remove coin 6 and put coin 4 on the left side of the scale and coin 5 on the right.

If the right bowl outweighs, then false - coin 4.
If the left bowl outweighs, then the false one - coin 5.
If the balance is balanced, then false - coin 6.

4. If the balance is balanced, then the counterfeit coin is either 7 or 8. Put coin 7 on the left side of the scale and coin 8 on the right side and weigh it.

If the right bowl outweighs, then false - coin 7.
If the left bowl outweighs, then the counterfeit coin 8.

The classical algorithm can be implemented regardless of the total number of coins N and the number of counterfeit coins k. In general, the time complexity for the generalized fake coin problem is O (k log (N / k)).

NOTE
It has been proven that at least two attempts are needed to detect one counterfeit coin using a laboratory balance on a classic computer.

Quantum Solution

Believe it or not, there is a quantum algorithm that can find a fake coin in one quantum weighing, regardless of the number of coins N! Generally speaking, for any number of counterfeit coins k, regardless of N, the time complexity of such an algorithm is

NOTE The
quantum algorithm for determining a fake coin is an example of fourth-degree acceleration compared to its classic counterpart.

So, in fig. 7.2 shows the superiority of the quantum algorithm over the classical counterpart in solving the fake coin riddle. Let's consider it in more detail. The quantum search algorithm for one counterfeit coin

can be divided into three stages: a request for quantum weights, the creation of quantum weights and the definition of a counterfeit coin.

Step 1. Request for quantum weights

The quantum algorithm will query the quantum weights in superposition. To do this, use a binary query string to encode coins on the scales. For example, the query string 11101111 means that all coins are on the scales, except for the coin with index 3. The scales are balanced if there are no counterfeit coins, and are tilted otherwise. This is illustrated in the following table.

The algorithm of actions is as follows.

1. Use two quantum registers to query quantum weights, where the first register is for the query string and the second for the result.

2. Prepare a superposition of all binary query strings with an even number of units.

3. To obtain a superposition of states with an even number of units, perform the Hadamard transform in the base state and check whether the Hamming weight for | x | even. It can be shown that the Hamming weight for | x | is even if and only if x1 ⊕ x2 ⊕ ... ⊕ xN = 0.

NOTE
The Hamming Weight (hw) of a string is the number of characters other than the null character of the alphabet used. For example, hw (11101) = 4, hw (11101000) = 4, hw (000000) = 0.

4. Finally, measure the second register. If a condition is observed

, then the first register is a superposition of all the desired binary query strings. If received

, then you need to repeat the procedure until a condition is observed.

Note that with each repetition, the probability of success is exactly 0.5. However, after several repetitions, we can get the desired superposition of states. Listing 7.1 shows the implementation of the quantum program for querying the weights, and the corresponding graphical diagram is shown in Fig. 7.3.

NOTE
To simplify the perception, the program for determining a fake coin is divided into listings 7.1–7.3. Although I hope that you can combine these listings to run the program, the full code is in the source in the file Workspace\Ch07\p_counterfeitcoin.py.

Listing 7.1. Quantum Weights Query Script

# -------    
Q_program = QuantumProgram()
Q_program.set_api(Qconfig.APItoken, Qconfig.config["url"])

#  numberOfCoins +1 / 
#      
#  
qr = Q_program.create_quantum_register("qr", numberOfCoins + 1)

#     qr
cr = Q_program.create_classical_register("cr", numberOfCoins + 1)

circuitName = "QueryStateCircuit"
circuit = Q_program.create_circuit(circuitName, [qr], [cr])

N = numberOfCoins

#       N
for i in range(N):
     circuit.h(qr[i])

#  XOR(x)     CNOT  qr[0]
#  qr[N–1]     qr[N]
for i in range(N):
     circuit.cx(qr[i], qr[N])

#  qr[N]     cr[N]. ,
#  cr[N]  ,     
circuit.measure(qr[N], cr[N])

#     ,     
# cr[0]...cr[N],     |1>,
#   |0> - |1>  qr[N]
circuit.x(qr[N]).c_if(cr, 0)
circuit.h(qr[N]).c_if(cr, 0)

#      cr[N]
for i in range(N):
     circuit.h(qr[i]).c_if(cr, 2**N)

In fig. 7.3 is a complete diagram for the fake coin puzzle with eight coins and one fake with index 6. It shows all the steps described here for the IBM Q Experience platform. The second stage of the algorithm is the creation of weights.

Step 2. Creating quantum weights

In the previous section, we created a superposition of all binary query strings for which the Hamming weight is even. At this step, create a quantum balancer, setting the position of the fake coin. Thus, if k is the position of the counterfeit coin relative to the binary string,

then quantum scales will return:

This is implemented using the CNOT gate with xk as the control qubit and the second register as the target (see Listing 7.2).

Listing 7.2. Creating quantum weights

#-----   
k = indexOfFalseCoin

#       
# (  cr,  )
circuit.cx(qr[k], qr[N]).c_if(cr, 0)

Step 3. Identify a fake coin

To reveal a fake coin after a query to the weights, apply the Hadamard transform to the binary query string. It is assumed that we are making a query on quantum weights with binary strings with an even Hamming weight, therefore, having performed a measurement in the computational basis after the Hadamard transform, we can determine a fake coin, since only its label is different from most labels (see Listing 7.3).

Listing 7.3. Fake coin definition

# ---   
#     qr[0] ... qr[N-1]
for i in range(N):
     circuit.h(qr[i]).c_if(cr, 0)

#  qr[0] ... qr[N–1]
for i in range(N):
     circuit.measure(qr[i], cr[i])

results = Q_program.execute([circuitName], backend=backend, shots=shots)
answer = results.get_counts(circuitName)

print("Device " + backend + " counts " + str(answer))

#     
for key in answer.keys():
     normalFlag, _ = Counter(key[1:]).most_common(1)[0]

for i in range(2,len(key)):
     if key[i] != normalFlag:
          print("False coin index is: ", len(key) - i - 1)

When the leftmost bit is 0, the counterfeit coin index can be determined by finding the one whose weight is different from the weight of the others. For example, with N = 8 and counterfeit coin index 6, the result should be 010111111 or 001000000. Note that since we use cr [N] to control the operation before and after the request for weights:

if the leftmost bit is 0, then we have successfully identified the counterfeit coin;
if the leftmost bit is 1, then we did not get the desired superposition and must repeat the process again.

When you run the program on a remote IBM Q Experience simulator, you will get the result shown in the source code of the book Workspace\Ch07\p_counterfeitcoin.py. Note that I use Windows: If you do not have access to the source code of the book, but you still want to experiment with this script, then place the code snippets from the previous sections in the script container from Listing 7.4 (check the indentation, this Python syntax feature is simple crazy). Listing 7.4. The main script container for the fake coin riddle

c:\python36-64\python.exe p_counterfeitcoin.py
Device ibmq_qasm_simulator counts {'001000000': 1}
False coin index is: 6

import sys
import matplotlib.pyplot as plt
import numpy as np
from math import pi, cos, acos, sqrt
from collections import Counter
from qiskit import QuantumProgram
sys.path.append('../Config/')
import Qconfig

#      
import basic plot tools
from qiskit.tools.visualization import plot_histogram

def main(M = 16, numberOfCoins = 8 , indexOfFalseCoin = 6
      , backend = "local_qasm_simulator" , shots = 1 ):

      if numberOfCoins < 4 or numberOfCoins >= M:
           raise Exception("Please use numberOfCoins between 4 and ", M-1)
      if indexOfFalseCoin < 0 or indexOfFalseCoin >= numberOfCoins:
           raise Exception("indexOfFalseCoin must be between 0 and ",
           numberOfCoins-1)

      //   7.1–7.3 

#################################################
# main
#################################################
if __name__ == '__main__':
     M = 8                      #    
     numberOfCoins = 4          #  M-1,  M —   
     indexOfFalseCoin = 2             #   0, 1... numberOfCoins — 1

     backend = "ibmq_qasm_simulator"
     #backend = "ibmqx3"
     shots = 1                         #      

     main(M, numberOfCoins, indexOfFalseCoin, backend, shots)

Generalized algorithm for any number of counterfeit coins

To solve the fake coin riddle, mathematicians Terhal and Smolin in 1998 created a generalized algorithm for any number of fake coins (k> 1). In their implementation, the “B-oracle" model ("balanced oracle") is used, while:

at the input
a query string is created, consisting of N triples of bits such that with the same number of 1 and –1;
the answer is one such bit that

NOTE The
Oracle is part of the algorithm, considered as a black box. It is used to simplify schemes and compare the complexity of quantum and classical algorithms. A good oracle must be fast, versatile, and easy to implement.

An example of using the B-oracle for two counterfeit coins with k = 2 and N = 6 is shown in Fig. 7.4.

In general, the fake coin riddle is a typical example of the acceleration of the quantum algorithm compared to the classic counterpart. In the next section, we will consider another peculiar pseudo-magic puzzle called “the magic square of Mermin - Perez”.

about the author

Vladimir Silva graduated from Middle TN State University with a Master's degree in Computer Science. For five years, he worked at IBM as a Research Engineer, where he gained rich experience in distributed and GRID computing.

Vladimir has many certificates, including OCP (Oracle Certified Professional), MCSD (Microsoft Certified Solutions Developer) and MCP (Microsoft Certified Professional). He is also the author of a large number of technical articles for the IBM developerWorks site. He has written the following books: Grid Computing for Developers (Charles River Media), Practical Eclipse Rich Client Platform (Apress), Pro Android Games (Apress), and Advanced Android 4 Games (Apress).

Vladimir is an avid marathon runner who participated in 16 races in North Carolina (at the time of writing). He loves to play the classical guitar and reflect on such amazing things as quantum mechanics.

About science editors

Original Edition

Jason Whitehorn is an experienced entrepreneur and software developer. He has helped many oil and gas companies automate and improve their technology through operational data collection, SCADA (Supervisory Control and Data Acquisition - dispatch control and data collection) and machine learning. Jason graduated from Arkansas State University with a bachelor's degree in Computer Science.

Jason loves spending free time with his wife and four children. Lives in Tulsa, Oklahoma. More information about Jason can be found on his jason.whitehorn.us website .

Russian edition

Mikhail Korobko- a physicist, is engaged in theory and experiments on the application of quantum optics, optomechanics and quantum measurements to improve the sensitivity of gravitational-wave detectors. Since 2012, it has been a member of the international collaboration of scientists at the LIGO gravitational wave detector.

Mikhail graduated from the Physics Department of Moscow State University. Lomonosov, is currently a graduate student of the Institute of Laser Physics at the University of Hamburg. He spends his free time with his family, writes popular science articles about quantum physics and publishes posts on Twitter (@hbar_universe).

»More information on the book can be found on the publisher’s website
» Table of Contents
» Excerpt

For Savingsbenders 25% off coupon - Silva

Upon payment of the paper version of the book, an electronic book is sent by e-mail.

The book "Development using quantum computers"