Calculating the classical OR gate in a 3 qubit (+1 ancillary qubit) circuit

Question

I have a 2 qubit (+1 ancillary qubit) circuit in Qiskit which calculates the classical OR gate (q0 or q1) as follows:

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer

for input in ['00','01','10','11']:
    
    mycircuit1 = QuantumCircuit(3,1)
    
    #Initialization - Note qiskit order
    if input[0] == '1':
        mycircuit1.x(1)
    if input[1] == '1':
        mycircuit1.x(0)

    mycircuit1.cx(0,2)
    mycircuit1.cx(1,2)
    mycircuit1.ccx(0,1,2)

    mycircuit1.measure(2,0)

    job    = execute(mycircuit1, Aer.get_backend('qasm_simulator'), shots = 1000)
    counts = job.result().get_counts(mycircuit1)
    print("Input:", input, "Output:", counts)

that returns:

Input: 00 Output: {'0': 1000}
Input: 01 Output: {'1': 1000}
Input: 10 Output: {'1': 1000}
Input: 11 Output: {'1': 1000}

and and I want to expand it to a 3 qubit(+1 ancillary qubit) circuit that calculates (q0 or q1 or q2) but I do not know how. One way of thinking is that (q0 OR q1 OR q2) = (qo OR q1) OR q2 so I can put the gates from the previous circuit and repeat the process. However, I do not know how to bind these two together. Here is the circuit that I have at the moment:

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, Aer

for input in ['000','100','010','001', '110','011','101','111']:
    
    mycircuit1 = QuantumCircuit(4,1)
    
    #Initialization - Note qiskit order
    if input[0] == '1':
        mycircuit1.x(1)
    if input[1] == '1':
        mycircuit1.x(0)

    mycircuit1.cx(0,2)
    mycircuit1.cx(1,2)
    mycircuit1.ccx(0,1,2)

    mycircuit1.barrier()

    mycircuit1.cx(1,3)
    mycircuit1.cx(2,3)
    mycircuit1.ccx(1,2,3)
    
    mycircuit1.measure(3,0)

    job    = execute(mycircuit1, Aer.get_backend('qasm_simulator'), shots = 1000)
    counts = job.result().get_counts(mycircuit1)
    print("Input:", input, "Output:", counts)

that returns:

Input: 000 Output: {'0': 1000}
Input: 100 Output: {'1': 1000}
Input: 010 Output: {'1': 1000}
Input: 001 Output: {'0': 1000}
Input: 110 Output: {'1': 1000}
Input: 011 Output: {'1': 1000}
Input: 101 Output: {'1': 1000}
Input: 111 Output: {'1': 1000}

I am stuck at this point and I do not know what to do next. As demonstrated in the results if q0 or q1 equals one, the final result would be one, so if I can fix the problem in the 001 input, I can say I implemented the classical OR gate for three inputs.

Answer 1

There are two errors in your code:

1. You only initialize the first two bits, the last bit of the input is unused. Thus, you should replace:

    if input[0] == '1':
        mycircuit1.x(1)
    if input[1] == '1':
        mycircuit1.x(0)

by (I've also replaced input by input_ because input is a built-in):

    for index, bit in enumerate(input_[::-1]):
        if bit == '1':
            mycircuit1.x(index)

2. You have to use 5 qubits in total, not 4: 3 to store the input bits, 1 to store q0 or q1 and 1 to store (q0 or q1) or q2.

Thus, your code should look like this:

for input_ in ['000','100','010','001', '110','011','101','111']:
    mycircuit1 = QuantumCircuit(5,1)
    
    # Reverse input_ because of qiskit order
    for index, bit in enumerate(input_[::-1]):
        if bit == '1':
            mycircuit1.x(index)

    mycircuit1.cx(0, 3)
    mycircuit1.cx(1, 3)
    mycircuit1.ccx(0, 1, 3)

    mycircuit1.barrier()

    mycircuit1.cx(2, 4)
    mycircuit1.cx(3, 4)
    mycircuit1.ccx(2, 3, 4)
    
    mycircuit1.measure(4,0)

    job    = execute(mycircuit1, Aer.get_backend('qasm_simulator'), shots = 1000)
    counts = job.result().get_counts(mycircuit1)
    print("Input:", input_, "Output:", counts)

Note however that, as mentioned by DaftWullie in the comments, you can define a QuantumCircuit that you want to append to your main circuit. For instance, define:

or_circ = QuantumCircuit(3)
or_circ.cx(0, 2)
or_circ.cx(1, 2)
or_circ.ccx(0, 1, 2)

And you can then do:

for input_ in ['000','100','010','001', '110','011','101','111']:
    mycircuit1 = QuantumCircuit(5,1)
    
    # Reverse input_ because of qiskit order
    for index, bit in enumerate(input_[::-1]):
        if bit == '1':
            mycircuit1.x(index)

    mycircuit1.append(or_circ, [0, 1, 3])

    mycircuit1.barrier()

    mycircuit1.append(or_circ, [2, 3, 4])
    
    mycircuit1.measure(4,0)

    job    = execute(mycircuit1, Aer.get_backend('qasm_simulator'), shots = 1000)
    counts = job.result().get_counts(mycircuit1)
    print("Input:", input_, "Output:", counts)

As a final note, since you know that q0 OR q1 is equivalent to NOT (NOT q0 AND NOT q1), you can define your OR gate with only X and CCX gates:

or_circ = QuantumCircuit(3)
or_circ.x([0, 1, 2])
or_circ.ccx(0, 1, 2)
or_circ.x([0, 1])

Using this gate would still give you the right results.

---

Finally, note that you can use the same last trick to implement the OR gate with only 4 qubits: just use an MCX gate, which represents the logical AND and negate it:

for input_ in ['000','100','010','001', '110','011','101','111']:
    mycircuit1 = QuantumCircuit(4, 1)
    
    # Reverse input_ because of qiskit order
    for index, bit in enumerate(input_[::-1]):
        if bit == '1':
            mycircuit1.x(index)

    mycircuit1.x(range(4))
    mycircuit1.mcx([0, 1, 2], 3)
    mycircuit1.x(range(3))
    
    mycircuit1.measure(3, 0)

    job    = execute(mycircuit1, Aer.get_backend('qasm_simulator'), shots = 1000)
    counts = job.result().get_counts(mycircuit1)
    print("Input:", input_, "Output:", counts)

Answer 2

Maybe I'm not answering the root of your question. I would like to point out that Qiskit has a boolean expression synthesiser that automatically does that:

from qiskit.circuit.classicalfunction import BooleanExpression

circuitXorY = BooleanExpression("x or y").synth()
print(circuitXorY)

q_0: ──■───────
       │       
q_1: ──o────■──
     ┌─┴─┐┌─┴─┐
q_2: ┤ X ├┤ X ├
     └───┘└───┘

With 3 qubits (plus one for the result):

circuitXorYorZ = BooleanExpression("x or y or z").synth()
print(circuitXorYorZ)

q_0: ──■────────────
       │            
q_1: ──o────■───────
       │    │       
q_2: ──o────o────■──
     ┌─┴─┐┌─┴─┐┌─┴─┐
q_3: ┤ X ├┤ X ├┤ X ├
     └───┘└───┘└───┘

You can see how is that implemented without open controls like this:

print(circuitXorYorZ.decompose())

q_0: ───────■───────────────────────────
     ┌───┐  │  ┌───┐                    
q_1: ┤ X ├──■──┤ X ├───────■────────────
     ├───┤  │  ├───┤┌───┐  │  ┌───┐     
q_2: ┤ X ├──■──┤ X ├┤ X ├──■──┤ X ├──■──
     └───┘┌─┴─┐└───┘└───┘┌─┴─┐└───┘┌─┴─┐
q_3: ─────┤ X ├──────────┤ X ├─────┤ X ├
          └───┘          └───┘     └───┘