CNOT and toffoli in simple naive grover

Issues
#1

Hello, I am trying to implement a simple and naive grover algorithm using the following code:

Code

Gates declaration

X = catalog[‘x’].build_processor()
H = catalog[‘h’].build_processor()
cnot = catalog[‘heralded cnot’].build_processor()
toffoli = catalog[‘toffoli’].build_processor()

Our qubits in the dual rail encoding

q1, q2, q3 = [0,1], [2,3], [4,5]

Initialisation

p = pcvl.Processor(“SLOS”,6)
p.add(q3, X)
p.add(q1, H)
p.add(q2, H)
p.add(q3, H)

Naive oracle

p.add(q1, X)
p.add(q1+q2+q3, toffoli)
p.add(q1, X)

Amplification

p.add(q1, H)
p.add(q2, H)
p.add(q1, X)
p.add(q2, X)
p.add(q2, H)

p.add(q1+q2, cnot)

p.add(q2, H)
p.add(q1, X)
p.add(q2, X)
p.add(q1, H)
p.add(q2, H)

printing the circuit

pcvl.pdisplay(p,recursive=False)

Questions

When commenting either the toffoli OR the CNOT, the circuit gets printed.
But when I let both, I get :
AssertionError: Post-selection conditions cannot compose with modes [0, 1, 2, 3]

From what I am understanding, we cannot post select because when we post select on thoses modes we can guarantee we have qubits at the end but we cannot guarantee in the middle of the two that we effectively had qubits (~that the first CNOT worked). Is this Right ?

If this is right, why can we use multiple (as in strictly more than one) CNOT in
Detailed walkthrough — perceval v0.13 documentation

#2

Hello Martin,

You’re placing a Toffoli gate on qubits 1,2 and 3 and, later, a CNOT on qubits 1 and 2.
So, the Toffoli and the CNOT share qubits 1 and 2.
In this particular configuration, all 2+ qubit gates have to be heralded except for the last one (the Toffoli would need to be heralded and the CNOT could be either heralded or post-selected).

The issue here is that the Toffoli implementation provided in Perceval is not heralded (but only post-selected).
This means that whenever you’re using this Toffoli implementation it has to be the last 2+ qubit gate on the qubits it’s located on.
The error message you encounter means that the post-selection function embedded in the Toffoli gate implementation is not compatible with the next 2-qubit gate (the heralded CNOT, in your case).

Also, I don’t think we have a heralded Toffoli implementation, so we cannot provide you with any.

Best regards,
Eric

#3

Hello Eric,

Thank you for our answer.

I used to think heralded CNOT and post selected CNOT had only a subtle difference in their realisation. But it seems you cannot use more than one post selected gates on a given qubit (wich seems logical).

You are telling me that it is possible with heralded CNOT ?

Appologies if my questions seem basic, I am starting out on QC.

So I could be building the toffoli myself using heralded cnot and T gates and it should work ?

What papers would you recommand describing heralded CNOT ? I have read Ralph’s paper wich seems to be post selected. Is the one using “NS gates” from KLM protocol heralded ?

Thank you again for your time,

Best regards,
Martin

#4

Hello Martin,

Yes, heralded (Knill) and post-selected (Ralph) CNOT fill in the same “functional” need but there’s a trade off in how/where to use them. Heralded uses more resources (photons) but will get deterministic CNOT results anywhere in the circuit, whereas post-selected one uses (two) less photons but needs to be placed at the end of the circuit.

Theoretically, you can add as many heralded CNOTs as you want, on any qubits, but pay attention that the 2 ancillary modes + 2 additional photons for each is very “costly” both in a QPU and in a simulation. So you’ll still be limited by the photon count.

I cannot confidently answer the rest of your questions, as I’m not working on photonic gate based implementations, but if you can implement a Toffoli gate using CNOT and T gates, then yes, having heralded CNOT in the mix will make you circuit work.

I didn’t reopen the KLM protocol paper, but I’m pretty sure they use heralded gates in their demonstration.

Best regards,
Eric