CSP ignores 3-or-more-qubit gates

[1ucian0]

Information

• Qiskit Terra version: main

What is the current behavior?

Take the following circuit:

from qiskit import QuantumCircuit
qc = QuantumCircuit(3)
qc.cx(0,1)
qc.ccx(2,0,1)
qc.draw()

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

CSPLayout should not be able to find a solution with a layout 0- > 1 -> 2. However:

from qiskit.transpiler import CouplingMap
from qiskit.transpiler.passes import CSPLayout

pass_ = CSPLayout(CouplingMap([(0, 1), (1, 2)]))
result = pass_(qc)
pass_.property_set["CSPLayout_stop_reason"]

'solution found'

Suggested solutions

There are two options. If CSPLayout encounters a 3-or-more-qubit gate, either assumes that this needs complete connection among the involved qubits, or just fails with reason 3-or-more-qubit gate found.

[yjt98765]

@1ucian0 I tried to add 3-or-more-qubit gates as constraints, and the pass generates this layout:

Layout({
1: Qubit(QuantumRegister(3, 'qr'), 0),
0: Qubit(QuantumRegister(3, 'qr'), 1),
2: Qubit(QuantumRegister(3, 'qr'), 2)
})

I guess maybe it is reasonable? It does not involve swaps. It simply suggests that mapping qr[0] to physical qubit 1. Such mapping is allowed, right? It is kind of the point of using CSP in this pass.

[1ucian0]

In the original example, CCX does not have a possible layout in the coupling map 0 - > 1 -> 2. No solution should be found or raise.

[Silrem]

Can I work on this?

[1ucian0]

Sure thing @Silrem. Assigning. let me know if I can help!

[Silrem]

@1ucian0 Just created a PR (#7625). Not sure if I can/should add you as a reviewer. Anyway, my first draft is there =)

[javabster]

un-assigning so that this issue is open for others to have a go. If anyone would like to pick this work up make sure to take a look at #7625 and go from there 😄

[lmpawan10]

I want to work on the issue if it still exists.

[javabster]

sorry for the slow reply @lmpawan10, I'll assign to you 😄 As this is an old issue the first step would be to check that the bug still exists

[1ucian0]

Hello @lmpawan10 ! Are you still working on this one?

[lmpawan10]

Sorry that I got busier with other tasks. I am planning to work on this issue this month.
You can give it to others if they are interested, or I will deal with it.

[1ucian0]

Hi @lmpawan10 ! how is that going?

[1ucian0]

clearing assignee

[1ucian0]

@ChilliPenguin submitted #12912, can you leave a comment in this issue so I can assign it to you?

[alexanderivrii]

Sorry that I bring this point so late in the process (after there is a PR implementing the requested change), but I don't understand why to layout a multi-qubit gate we should assume that all of its qubits should be mapped to pairwise connected physical qubits. In the normal transpilation flow, we always decompose multi-qubit gates into single-qubit and two-qubit gates, so the issue presented here (a layout algorithm needs to handle a 3-qubit gate) would simply not arise.

On the other hand, if, hypothetically, in some future we would be able to apply a CCX gate natively on a device, then we would also need a generalization of the coupling map that holds the information which 3-qubit gates can or cannot be natively applied (so this would still not be the right approach).

Hmm, I can also see a scenario where someone would want to use CSPLayout pass to produce a "high-level" layout for multi-qubit gates, with the goal to then synthesize (post-routing!) these multi-qubit gates adhering to the coupling map. However, in this case it would only make sense to require that the qubits are connected (and not pairwise connected) -- the actual synthesis algorithm would need to make sure that the 2-qubit gates it produces are connected.

@1ucian0, @ChilliPenguin, would love to hear your thoughts on this.