1
$\begingroup$

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"])

```
$\endgroup$
6
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Commented May 12, 2023 at 15:17
  • $\begingroup$ Thank you for looking at this issue. I added a Qiskit code, to be more precise. $\endgroup$ Commented May 12, 2023 at 20:34
  • $\begingroup$ Are you allowing access to the inverse of the circuit in the general case? $\endgroup$ Commented May 14, 2023 at 18:57
  • $\begingroup$ I can not use qc.inverse() on this version of the circuit, for it is dynamic: several times "reset". But I could replace them by using more ancilla qubits. Would that help? $\endgroup$ Commented May 14, 2023 at 20:15
  • $\begingroup$ Making the variant of the Grover diffusion operator for this case would traditionally require flanking $2|0^n\rangle\langle0^n| - I$ with the circuit used to create the superposition and that circuit's inverse. If the circuit can be formulated with tractable classical resources as a set of unitary gates with known inverses then things are much easier than otherwise. $\endgroup$ Commented May 14, 2023 at 20:47

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.