5
$\begingroup$

I am currently creating a blackbox for a grover search algorithm to solve the graph colouring problem with qiskit. One of my search criteria is that one node can only have one color. Therefore, with my current problem having 4 colours and 8 nodes, I need to design something like an XOR gate with 4 control qubits. So that the target qubit flips, only if one of the control qubits is |1>.
What would be an efficient way to design such a gate (best case for n control qubits)?

$\endgroup$
7
$\begingroup$

For the general case, you can use a counting strategy like this:

enter image description here

This has a gate count of $O(n \lg n)$ and a work qubit count of $O(\lg n)$. Much better than the naive $O(n^2)$ gate count.

You can improve the gate count to $O(n)$ if you're willing to use more ancilla qubits, by using a recursive strategy where you classify the first half and second half of the input as "none, one, more" and then merge. This will increase the ancilla qubit count from $O(\lg n)$ to $O(n)$. Though that count can probably be reduced by playing pebble games with the intermediate values.

Note that for specific $n$ you can often find improvements that pretty substantially reduce the gate count over the generic strategies. For example, for the four control case you can do much better: four Toffolis, one ancilla, and six CNOTs is sufficient.

enter image description here

(verification in Quirk via state channel duality)

Start from the obvious solution:

enter image description here

Conjugate adjacent "controls differ in two places" pairs with CNOTs to reduce the big operation count in half:

enter image description here

Move CNOTs to the sides and decompose the triple-controlled NOTs into Toffolis, being sure to use the controls common to both big operations as the controls for the temporary accumulator:

enter image description here

There are once again two adjacent operations that differ in controls at two places. They can be downgraded into CNOTs, producing the solution at the top.

| improve this answer | |
$\endgroup$
7
$\begingroup$

You can create gates that are controlled on 0 or on 1. You could therefore implement this condition as several gates in a row, each controlled by 1 in the index of the qubit and 0 elsewhere. This will only flip the target qubit if exactly one of the other qubits it 1.

You should be able to do this using C4XGate. This would look something like

from qiskit.circuit.library.standard_gates import C4XGate
qr = QuantumRegister(5)
qc = QuantumCircuit(qr)

gate = C4XGate(qr, ctrl_state='1000')
qc.append(gate, qr)
gate = C4XGate(qr, ctrl_state='0100')
qc.append(gate, qr)
gate = C4XGate(qr, ctrl_state='0010')
qc.append(gate, qr)
gate = C4XGate(qr, ctrl_state='0001')
qc.append(gate, qr)
| improve this answer | |
$\endgroup$
2
$\begingroup$

If we are allowed to use ancillary qubits, then this will work (here is an answer about multi-control qubit gates and answer that can show why there are $X$ gates in the following circuit):

The $q[0 - 3]$ qubits are controlled qubits, the $q[4]$ qubit is the target qubit, $q[5 - 6]$ are ancillary qubits. One small optimization can be done by erasing $15$th and $16$th $CCNOT$ gates (nearby two $X$s commute with them). This solution can be extended for $n$ qubits (with more ancillary qubits).

This answer to the related question might be interesting.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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