0
$\begingroup$

I have a set S=[1,2,3,4] from which I need to find out two subsets which has the same sum. For example S0=[1,4] and S1=[2,3]. Assume that we've a solution. One approach is to encode all states in the set but I do not want to take this route rather encode the sum's. With the circuit below I'm trying to generate all possible sum's and trying to find which states adds up to 5. Currently I'm getting the 101 state as the max. probability. I'm not sure how to proceed further from here. Any pointers would be of great help!

# Importing standard Qiskit libraries
from qiskit import QuantumCircuit, transpile
from qiskit import QuantumRegister, ClassicalRegister, execute
from qiskit.tools.jupyter import *
from qiskit.visualization import *
from ibm_quantum_widgets import *
from qiskit_aer import AerSimulator
from qiskit.circuit.library import C3XGate
from qiskit import Aer
from qiskit.visualization import plot_histogram

# qiskit-ibmq-provider has been deprecated.
# Please see the Migration Guides in https://ibm.biz/provider_migration_guide for more detail.
from qiskit_ibm_runtime import QiskitRuntimeService, Sampler, Estimator, Session, Options

# Loading your IBM Quantum account(s)
service = QiskitRuntimeService(channel="ibm_quantum")


def diffuser():

    qc = QuantumCircuit(3, name='diffuser')

    qc.h(0)
    qc.h(1)
    qc.h(2)
    qc.x(0)
    qc.x(1)
    qc.x(2)
    qc.ccz([2], [1], [0])
    qc.x(0)
    qc.x(1)
    qc.x(2)
    qc.h(0)
    qc.h(1)
    qc.h(2)

    return qc

d = diffuser()

dg = d.to_gate()
c_d = dg.control()

circuit = QuantumCircuit(8)
circuit.append(c_d, [0,1,2,3])
print(circuit)


def sum_1():

    qreg_q = QuantumRegister(3, 'q')

    circuit = QuantumCircuit(qreg_q, name='sum 1')

    circuit.ccx(qreg_q[0], qreg_q[1], qreg_q[2])
    circuit.cx(qreg_q[1], qreg_q[2])
    circuit.x(qreg_q[2])

    return circuit

s1 = sum_1()

s1g = s1.to_gate()
ctrl_s1 = s1g.control()

circuit = QuantumCircuit(5)
circuit.append(ctrl_s1, [0,1,2,3])
print(circuit)


def sum_2():

    qreg_q = QuantumRegister(3, 'q')

    circuit = QuantumCircuit(qreg_q, name='sum 2')

    circuit.cx(qreg_q[1], qreg_q[2])
    circuit.x(qreg_q[1])

    return circuit

s2 = sum_2()

s2g = s2.to_gate()
ctrl_s2 = s2g.control()

circuit = QuantumCircuit(4)
circuit.append(ctrl_s2, [0,1,2,3])
print(circuit)


def sum_3():

    qreg_q = QuantumRegister(3, 'q')

    circuit = QuantumCircuit(qreg_q, name='sum 3')

    circuit.ccx(qreg_q[0], qreg_q[1], qreg_q[2])
    circuit.cx(qreg_q[1], qreg_q[2])
    circuit.x(qreg_q[2])
    # circuit.barrier(qreg_q[0], qreg_q[1], qreg_q[2])
    circuit.cx(qreg_q[1], qreg_q[2])
    circuit.x(qreg_q[1])
    # circuit.barrier(qreg_q[0], qreg_q[1], qreg_q[2])

    return circuit

s3 = sum_3()

s3g = s3.to_gate()
ctrl_s3 = s3g.control()

circuit = QuantumCircuit(5)
circuit.append(ctrl_s3, [0,1,2,3])
print(circuit)


def sum_4():

    qreg_q = QuantumRegister(3, 'q')

    circuit = QuantumCircuit(qreg_q, name='sum 4')

    circuit.cx(qreg_q[1], qreg_q[2])
    circuit.x(qreg_q[1])
    circuit.cx(qreg_q[1], qreg_q[2])
    circuit.x(qreg_q[1])

    return circuit

s4 = sum_4()

s4g = s4.to_gate()
ctrl_s4 = s4g.control()

circuit = QuantumCircuit(4)
circuit.append(ctrl_s4, [0,1,2,3])
print(circuit)


# define set
S = [1,2,3,4]
# S0 = [1,4] S1 = [2,3]
# h = sum = 5

n = len(S)



qr1 = QuantumRegister(n, 'summing')
qr2 = QuantumRegister(n, 'elements')
qr3 = QuantumRegister(1, 'f(x)')

qcr1 = ClassicalRegister(3, 'output')

qc1 = QuantumCircuit(qr1, qr2, qr3, qcr1)

# apply h gate
for i in range(n):
    qc1.h(i)

# apply x gate to f(x)
qc1.x(qr3[0])

qc1.append(ctrl_s1, [qr2[0], qr1[0], qr1[1], qr1[2]])
qc1.append(ctrl_s2, [qr2[1], qr1[0], qr1[1], qr1[2]])
qc1.append(ctrl_s3, [qr2[2], qr1[0], qr1[1], qr1[2]])
qc1.append(ctrl_s4, [qr2[3], qr1[0], qr1[1], qr1[2]])

qc1.barrier(qr1, qr2, qr3)

# check if sum exceeded 8?
# total sum is 10
# then check when sum adds up to 5 (101)

qc1.append(C3XGate(ctrl_state='101'), [qr1[0], qr1[1], qr1[2], qr3[0]])

# qc1.measure(qr3[0], qcr1[0])

qc1.barrier(qr1, qr2, qr3)

# append diffuser
qc1.append(c_d, [qr3[0], qr1[0], qr1[1], qr1[2]])

qc1.barrier(qr1, qr2, qr3)

qc1.measure(qr1[0], qcr1[0])
qc1.measure(qr1[1], qcr1[1])
qc1.measure(qr1[2], qcr1[2])

# execute the circuit on a simulator
simulator = Aer.get_backend('qasm_simulator')
job = execute(qc1, simulator, shots=8192)

# retrieve the counts of the measurement outcomes
result = job.result()
counts = result.get_counts(qc1)

# plot the histogram of the counts
plot_histogram(counts)


```
$\endgroup$

1 Answer 1

0
$\begingroup$

I was able to find it for S = [1,2,3,4]. Max. probability is for states 0110 and 1001 which represents the partitions [2,3] and [1,4] respectively. Now I need to figure out a way to address the carry bit when the list has more elements.

# Importing standard Qiskit libraries
from qiskit import QuantumCircuit, transpile
from qiskit import QuantumRegister, ClassicalRegister, execute
from qiskit.tools.jupyter import *
from qiskit.visualization import *
from ibm_quantum_widgets import *
from qiskit_aer import AerSimulator
from qiskit.circuit.library import C3XGate
from qiskit.circuit.library import MCXGate
from qiskit import Aer
from qiskit.visualization import plot_histogram

# qiskit-ibmq-provider has been deprecated.
# Please see the Migration Guides in https://ibm.biz/provider_migration_guide for more detail.
from qiskit_ibm_runtime import QiskitRuntimeService, Sampler, Estimator, Session, Options

# Loading your IBM Quantum account(s)
service = QiskitRuntimeService(channel="ibm_quantum")

# Invoke a primitive inside a session. For more details see https://qiskit.org/documentation/partners/qiskit_ibm_runtime/tutorials.html
# with Session(backend=service.backend("ibmq_qasm_simulator")):
#     result = Sampler().run(circuits).result()


def diffuser_4():

    # Create a 4-qubit quantum register
    qr = QuantumRegister(4, 'q')

    # Create the Grover diffuser circuit
    grover_diffuser = QuantumCircuit(qr, name='grover_diffuser')

    # Apply Hadamard gates to all qubits
    grover_diffuser.h(qr)

    # Apply X gates to all qubits
    grover_diffuser.x(qr)

    # Apply controlled-Z gates between each pair of qubits
    grover_diffuser.cz(qr[0], qr[1])
    grover_diffuser.cz(qr[0], qr[2])
    grover_diffuser.cz(qr[0], qr[3])
    grover_diffuser.cz(qr[1], qr[2])
    grover_diffuser.cz(qr[1], qr[3])
    grover_diffuser.cz(qr[2], qr[3])

    # Apply X gates to all qubits
    grover_diffuser.x(qr)

    # Apply Hadamard gates to all qubits
    grover_diffuser.h(qr)

    return grover_diffuser

d = diffuser_4()

dg = d.to_gate()
c_d = dg.control()

circuit = QuantumCircuit(8)
circuit.append(c_d, [0,1,2,3,4])
print(circuit)


def sum_1():

    qreg_q = QuantumRegister(3, 'q')

    circuit = QuantumCircuit(qreg_q, name='sum 1')

    circuit.ccx(qreg_q[1], qreg_q[2], qreg_q[0])
    circuit.cx(qreg_q[2], qreg_q[1])
    circuit.x(qreg_q[2])

    return circuit

s1 = sum_1()

s1g = s1.to_gate()
ctrl_s1 = s1g.control()

circuit = QuantumCircuit(5)
circuit.append(ctrl_s1, [0,1,2,3])
print(circuit)


def sum_2():

    qreg_q = QuantumRegister(3, 'q')

    circuit = QuantumCircuit(qreg_q, name='sum 2')

    circuit.cx(qreg_q[1], qreg_q[0])
    circuit.x(qreg_q[1])

    return circuit

s2 = sum_2()

s2g = s2.to_gate()
ctrl_s2 = s2g.control()

circuit = QuantumCircuit(4)
circuit.append(ctrl_s2, [0,1,2,3])
print(circuit)


def sum_3():

    qreg_q = QuantumRegister(3, 'q')

    circuit = QuantumCircuit(qreg_q, name='sum 3')

    circuit.ccx(qreg_q[1], qreg_q[2], qreg_q[0])
    circuit.cx(qreg_q[2], qreg_q[1])
    circuit.x(qreg_q[2])

    circuit.cx(qreg_q[1], qreg_q[0])
    circuit.x(qreg_q[1])

    return circuit

s3 = sum_3()

s3g = s3.to_gate()
ctrl_s3 = s3g.control()

circuit = QuantumCircuit(5)
circuit.append(ctrl_s3, [0,1,2,3])
print(circuit)


def sum_4():

    qreg_q = QuantumRegister(3, 'q')

    circuit = QuantumCircuit(qreg_q, name='sum 4')

    circuit.cx(qreg_q[1], qreg_q[0])
    circuit.x(qreg_q[1])

    circuit.cx(qreg_q[1], qreg_q[0])
    circuit.x(qreg_q[1])

    return circuit

s4 = sum_4()

s4g = s4.to_gate()
ctrl_s4 = s4g.control()

circuit = QuantumCircuit(4)
circuit.append(ctrl_s4, [0,1,2,3])
print(circuit)


# define set
S = [1,2,3,4]
# S0 = [1,4] S1 = [2,3]
# h = sum = 5

n = len(S)



qr1 = QuantumRegister(n, 'summing')
qr2 = QuantumRegister(n, 'elements')
qr3 = QuantumRegister(1, 'f(x)')

qcr1 = ClassicalRegister(n, 'output')

qc1 = QuantumCircuit(qr1, qr2, qr3, qcr1)

# apply h gate
for i in range(n,n+n):
    qc1.h(i)

# apply x gate to f(x)
qc1.x(qr3[0])

qc1.append(ctrl_s1, [qr2[0], qr1[0], qr1[1], qr1[2]])
qc1.append(ctrl_s2, [qr2[1], qr1[0], qr1[1], qr1[2]])
qc1.append(ctrl_s3, [qr2[2], qr1[0], qr1[1], qr1[2]])
qc1.append(ctrl_s4, [qr2[3], qr1[0], qr1[1], qr1[2]])

# barrier
qc1.barrier(qr1, qr2, qr3)

# add condition to check sum = 5
qc1.append(MCXGate(4, ctrl_state='0101'), [qr1[0], qr1[1], qr1[2], qr1[3], qr3[0]])

# barrier
qc1.barrier(qr1, qr2, qr3)

# append diffuser
qc1.append(c_d, [qr3[0], qr2[0], qr2[1], qr2[2], qr2[3]])

# barrier
qc1.barrier(qr1, qr2, qr3)

# measure
qc1.measure(qr2[0], qcr1[0])
qc1.measure(qr2[1], qcr1[1])
qc1.measure(qr2[2], qcr1[2])
qc1.measure(qr2[3], qcr1[3])


# execute the circuit on a simulator
simulator = Aer.get_backend('qasm_simulator')
job = execute(qc1, simulator, shots=8192)

# retrieve the counts of the measurement outcomes
result = job.result()
counts = result.get_counts(qc1)

# plot the histogram of the counts
plot_histogram(counts)

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.