Das Buch "Entwicklung mit Quantencomputern"

Auszug. Spieltheorie: Mit der Quantenmechanik ist der Vorteil immer auf Ihrer Seite

• Das falsche Münzrätsel. Dies ist das klassische Wiegeproblem, das der Mathematiker E. D. Shell 1945 vorgeschlagen hat. Darin müssen Sie unter Verwendung einer Laborwaage für eine begrenzte Anzahl von Wägungen eine Münze bestimmen, deren Gewicht sich vom Gewicht anderer unterscheidet (falsch).
• Das magische Quadrat von Mermin - Perez. Dies ist ein Beispiel für Quantenpseudotelepathie oder die Fähigkeit der Spieler, Ergebnisse zu erzielen, die nur möglich sind, wenn sie während des Spiels die Gedanken des anderen lesen.

Das falsche Münzrätsel

• Wenn die richtige Schüssel überwiegt, dann Falschmünze 1.
• Wenn die linke Schüssel überwiegt, dann die falsche - Münze 2.
• Wenn das Gleichgewicht ausgeglichen ist, dann Falschmünze 3.

• Wenn die rechte Schüssel überwiegt, dann Falschmünze 4.
• Wenn die linke Schüssel überwiegt, dann die falsche - Münze 5.
• Wenn das Gleichgewicht ausgeglichen ist, dann Falschmünze 6.

• Wenn die rechte Schüssel überwiegt, dann Falschmünze 7.
• Wenn die linke Schüssel überwiegt, dann die gefälschte Münze 8.

HINWEIS
Es wurde nachgewiesen, dass mindestens zwei Versuche erforderlich sind, um eine gefälschte Münze mithilfe einer Laborwaage auf einem klassischen Computer zu erkennen.

Quantenlösung

HINWEIS Der
Quantenalgorithmus zur Bestimmung einer gefälschten Münze ist ein Beispiel für eine Beschleunigung vierten Grades im Vergleich zu seinem klassischen Gegenstück.

Schritt 1. Anforderung von Quantengewichten

HINWEIS
Das Hamming-Gewicht (hw) einer Zeichenfolge ist die Anzahl der Zeichen, die nicht das Nullzeichen des verwendeten Alphabets sind. Zum Beispiel ist hw (11101) = 4, hw (11101000) = 4, hw (000000) = 0.

HINWEIS
Um die Wahrnehmung zu vereinfachen, ist das Programm zur Ermittlung einer gefälschten Münze in die Listen 7.1–7.3 unterteilt. Obwohl ich hoffe, dass Sie diese Auflistungen kombinieren können, um das Programm auszuführen, befindet sich der vollständige Code in der Quelle in der Datei Workspace\Ch07\p_counterfeitcoin.py.

# -------    
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)

Schritt 2. Quantengewichte erstellen

#-----   
k = indexOfFalseCoin

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

Schritt 3. Identifizieren Sie eine gefälschte Münze

# ---   
#     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)

• Wenn das Bit ganz links 0 ist, haben wir die gefälschte Münze erfolgreich identifiziert.
• Wenn das Bit ganz links 1 ist, haben wir nicht die gewünschte Überlagerung erhalten und müssen den Vorgang erneut wiederholen.

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)

Verallgemeinerter Algorithmus für eine beliebige Anzahl gefälschter Münzen

• am Eingang
• Es wird eine Abfragezeichenfolge erstellt, die aus N Dreifachbits besteht, so dass mit der gleichen Anzahl von 1 und –1;
• Die Antwort ist so ein bisschen
  

HINWEIS Das
Oracle ist Teil des Algorithmus, der als Black Box betrachtet wird. Es wird verwendet, um Schemata zu vereinfachen und die Komplexität von Quanten- und klassischen Algorithmen zu vergleichen. Ein gutes Orakel muss schnell, vielseitig und einfach zu implementieren sein.

Über den Autor

Über Wissenschaftsredakteure