I designed a circuit (under Anaconda/Jupyter/Qiskit) whose output is a superposition of states of n qubits, q(0), ...q(n-1). For most of them q(n-1) is |0>, and for a few |1>. I'd like to complete the circuit to "extract" (improve the probability) of one of these last ones (or possibly, of all of them), and then measure. I suspect it is possible with the Grover's algorithm, but I don't precisely know how to do that. Maybe looking for a maximum? Any suggestion would be welcome.
Please find below a test code (Qiskit), in which I explain more precisely what I'd like to do. It uses reset, so I added then a longer version without any reset in order, as suggested, to be able to easily reverse the circuit.
import math
import numpy as np
import random
from qiskit import *
from qiskit.visualization import plot_histogram
%matplotlib inline
backend_sim = Aer.get_backend('qasm_simulator')
List=[1,1,1 ]
l=len(List)
nN=3
nE=2
nC=3
nshots=100
#------ Build the circuit
nnc=nN*nC
ancill=nnc+nE+1
nqbits=ancill+1
# Create a Quantum Circuit
q = QuantumRegister(nqbits)
c=ClassicalRegister(nnc+1)
qc = QuantumCircuit(q,c)
# ============== Generate a superposition
# Initialisation
qc.h(range(nnc))
#print(qc)
# Constraints
# A 1 and only one 1 in each row of the nN*nC matrix
# Note: with this method the distribution is not uniform
s=0
for n in range(nN):
for k in range(nC-1):
for l in range(k+1,nC):
# Eliminate 11
qc.ccx (s+k,s+l,ancill)
# s+k or s+l (not really needed)
# choice=random.randint(0,1);
assign=choice*(s+k) + (1-choice)*(s+l)
assign=s+k
qc.cx (ancill,assign)
qc.reset(ancill)
# Eliminate 0*
for k in range(nC): qc.x(s+k) # Not needed if you can use a negative multicontrolled gate
cb=list(range(s,s+nC) )
qc.mcx (cb,ancill)
for k in range(nC): qc.x(s+k) # Not needed if you can use a negative multicontrolled gate
assign=random.randint(s, s+nC-1 ) # If all |0>, assign a random |1>
qc.cx (ancill,assign)
qc.reset(ancill)
s=s+nC
# At this point, if we measure, we have nNxNc matrices
# one and only one 1 in each row
print('end of generating matrices')
#qc.draw(output='mpl',filename="./circuit.eps")
# Check conflicts
eQubit=nnc-1
n=-1
for n1 in range(nN-1):
qnode1=n1*nC # rank of the first qubit for the node n1
for n2 in range(n1+1,nN):
qnode2=n2*nC # rank of the first qubit for the node n2
n=n+1
if List[n]>0:
eQubit=eQubit+1
print([ n1, n2,eQubit])
qc.x(eQubit)# Set to |1> initially
for k in range(nC): # For each column k ...
nk1=qnode1+k # |1> if row n1 has 1 in column k
nk2=qnode2+k # |1> if row n2 has 1 inb column k
cb=[nk1,nk2] # control qubits
print(cb)
qc.mcx (cb,eQubit) # Switched to |0> if same column (i.e. conflict) and List[n]>0
print('end of check conflicts') #
# Status of the state
cb=list(range(nnc,nnc+nE) )
qc.mcx(cb, nqbits-1)
print(cb)
print(nqbits-1)
# HERE, complete the circuit to manipulate the states (Grover?)
# so that the probabilities of states with status |0> become almost zero
# ???
# Measure
cb=0
for n in range(nN):
s=n*nC
for k in range(nC):
qb=s+k
qc.measure(qb,cb)
cb=cb+1
# Measure the validity qubit
qc.measure(nqbits-1,cb)
print('end of measures')
# print(qc) # Display the circuit
qc.draw(output='mpl',filename="./circuit.eps") # Save the circuit
d=qc.depth()
print("Circuit depth: ",d)
print("Circuit width: ",nqbits)
print("Complexity: ",d*nqbits)
job = execute(qc, backend_sim,shots=nshots)
result=job.result()
#print(result)
print('end of execute')
# Grab the results from the job.
counts = result.get_counts(qc)
print(counts)
print([len(counts)," states"])
plot_histogram(counts)
# Non quantum
# Exploit the nNxnC binary matrices
str=list(counts.keys()) #, list(counts.values()))
nClass=len(str)
nbSol=0
for n in range(nClass):
binary=str[n] # Bit string,
print(binary)
reverse_str = binary[::-1] # Should be read from right to left
print("Binary solution")
C=[]
for i in range(nN):
start=i*nC
end=start+nC
row = reverse_str[start : end]
print(row)
for j in range(nC):
if int(row[j])>0:
C.append(j+1)
if binary[0] =="1":
nbSol=nbSol+1
print("Valid")
print(" ")
if nbSol==0: print("Sorry, I didn't find any solution")
else: print([nbSol,"solutions"])
======= No reset version
import math
import numpy as np
import random
from qiskit import *
from qiskit.visualization import plot_histogram
%matplotlib inline
backend_sim = Aer.get_backend('qasm_simulator')
List=[1,0,1 ]
l=len(List)
nN=3
nE=2
nC=2
nshots=20
# Measure
cb=0
for n in range(nN):
s=n*nC
for k in range(nC):
qb=s+k
qc.measure(qb,cb)
cb=cb+1
# Measure the validity qubit
qc.measure(nqbits-1,cb)
print('end of measures')
# print(qc) # Display the circuit
qc.draw(output='mpl',filename="./circuit.eps") # Save the circuit
d=qc.depth()
print("Circuit depth: ",d)
print("Circuit width: ",nqbits)
print("Complexity: ",d*nqbits)
job = execute(qc, backend_sim,shots=nshots)
result=job.result()
#print(result)
print('end of execute')
# Grab the results from the job.
counts = result.get_counts(qc)
print(counts)
print([len(counts)," states"])
plot_histogram(counts)
# Non quantum
# Exploit the nNxnC binary matrices
str=list(counts.keys()) #, list(counts.values()))
nClass=len(str)
nbSol=0
for n in range(nClass):
binary=str[n] # Bit string,
print(binary)
reverse_str = binary[::-1] # Should be read from right to left
print("Binary solution")
C=[]
for i in range(nN):
start=i*nC
end=start+nC
row = reverse_str[start : end]
print(row)
for j in range(nC):
if int(row[j])>0:
C.append(j+1)
if binary[0] =="1":
nbSol=nbSol+1
print("Valid")
print(" ")
if nbSol==0: print("Sorry, I didn't find any solution")
else: print([nbSol,"solutions"])
```
