transpile may produce wrong results when coupling restraints are present. Example ccx

Costor commented 3 years ago

Information

{'qiskit-terra': '0.17.1', 'qiskit-aer': '0.8.2', 'qiskit-ignis': '0.6.0', 'qiskit-ibmq-provider': '0.12.3', 'qiskit-aqua': '0.9.1', 'qiskit': '0.25.3', 'qiskit-nature': None, 'qiskit-finance': None, 'qiskit-optimization': None, 'qiskit-machine-learning': None} Python 3.9.4 Windows 10 fully updated

What is the current behavior?

When coupling restrictions are present (e.g. on FakeAthens() backend), tranpile will compile cx(0,2) to which is not correct: The back swap is optimized out (Edit 2021-06-24) by reordering of qubits but the reordering is not documented in .qasm() output if no measurements are present, see comment below.

This extends to more complex gates: When restricted to basis gates rz, sx, x, cx (the IBM standard) , transpile will generate a wrong circuit for the ccx / toffoli gate when coupling restrictions are also present (probably because of missing back swaps when transpiling cx(0,2)). Without coupling restrictions transpile will generate the expected result as shown e.g. in exercise 1 of IBM Quantum Challenge 2021. With coupling restrictions present the resulting circuit is not equivalent to ccx, it cannot even be mapped using any base permutation or any change of base at all. This can be shown by comparing the eigenvalues of the unitary matrices of ccx (which are [1,1,1,1,1,1,1, -1]) and of the resulting circuit, which are not equivalent by a phase factor. The problem is probably also present with other controlled gates which require non-direct-neighbour coupling. The issue seems to creep in when non-neighbouring cx gates are replaced by swaps and cx.

Steps to reproduce the problem

I have provided a jupyter notebook to demonstrate the issue (see below / zip attachment). Choosing option 'C' will show the expected correct result transpiled without coupling restraints. Options 'F' and 'S' will demonstrate the issue, using either FakeAthens() as backend (which is restrained) or the aer_simulator using basis_gates and coupling_map restrictions as FakeAthens() has. Please note that I had to remove unused ancilla qubits from the transpile result but you will immediately verify by comparing the circuits before and after cleaning that no error is introduced there.

Qiskit_TranspileCCX_CouplingRestraints.zip

What is the expected behavior?

transpile should either add the missing back swap for cx(0,2) etc. and unroll ccx correctly using rz, sx, x, cx also in the presence of coupling restrictions, resulting in an unitary matrix that is equivalent to the textbook representation of the Toffoli unitary matrix, and/or document qubit renumbering in .qasm() output even if no measurements are present.

Suggested solutions

none.

# Qiskit: Demo transpile ccx problem with coupling restraints
# COSTOR 2021-06-21
import numpy as np

# Import Qiskit
from qiskit import *
from qiskit import QuantumCircuit
from qiskit import Aer, transpile
from qiskit.visualization import array_to_latex
from qiskit.test.mock import FakeAthens #or FakeVigo, FakeArmonk, FakeMumbai, FakeRome,...
print(f"{qiskit.__qiskit_version__}\n")

# Chose the demo:
while ((ch := input("Enter demo (F)akeDevice, (S)imulator, [C]orrect:").lower())):
    if (ch in ['f', 's', 'c']): break

# Construct quantum circuit with Toffoli gate
circ = QuantumCircuit(3)
circ.ccx(control_qubit1=0, control_qubit2=1, target_qubit=2)
#circ.save_unitary() #this will hang transpile on fake devices instead of erroring out

# Chosing backend
if (ch == 'f'): #use this to demo the problem with fake devices
    print("Demoing problem with fake device:")
    backend = FakeAthens() #device with constrained coupling
    circTransp = transpile(circ, backend=backend, optimization_level=1)
elif (ch == 's'): #use this to demonstrate the problem in simulator
    print("Demoing problem with simulator:")
    simulator = Aer.get_backend('aer_simulator') 
    circTransp = transpile(circ, backend=simulator, optimization_level=1, 
                        basis_gates = ['rz','sx', 'x', 'cx'], 
                        coupling_map = FakeAthens().configuration().coupling_map )
else: #use this to demonstrate the correct result without coupling restraints
    print("Showing correct solution when no coupling restraints exist:")
    simulator = Aer.get_backend('aer_simulator') 
    circTransp = transpile(circ, backend=simulator, optimization_level=1, 
                        basis_gates = ['rz','sx', 'x', 'cx'] )
print("Transpiled circuit:")
display(circTransp.draw(output='mpl', fold=-1))

# Prove that result circuit does not implement cxx
# Reconstruct circuit for simulator, removing unused ancillas
cleanCircTransp = QuantumCircuit(3)
qasm_str = circTransp.qasm()
qasm_str = qasm_str.replace(f"qreg q[{circTransp.num_qubits}];", f"qreg q[3];")
cleanCircTransp = cleanCircTransp.from_qasm_str(qasm_str) #will fail if qubits > 2 involved
cleanCircTransp.save_unitary() #prepare to get the unitary matrix
#display the cleaned transpiled circuit, coincides with original!
print("Cleaned circuit:")
display(cleanCircTransp.draw(output='mpl', fold=-1))
#Get the unitary matrix of the cleaned circuit:
simulator = Aer.get_backend('aer_simulator')
result = simulator.run(cleanCircTransp).result()
unitary = result.get_unitary(cleanCircTransp)
# divide out global phase for readibility
if (abs(unitary[0,0]) > 0.99):  
    unitary = unitary / unitary[0,0]
display(array_to_latex(unitary.round(2)))
# eigenvalues show that no base change can make this circuit a ccx
display(array_to_latex(np.linalg.eigvals(unitary).round(2)))

kdk commented 3 years ago

Thanks for reporting this @Costor ! I believe this is a duplicate of #4608 (which has a draft pull request to address the issue #5280 .)

Costor commented 3 years ago

yes #5280 looks very close (I can't judge on 4608).

However I found that the issue is probably due another cause: In order to save gates transpile reorders / renumbers qubits. However this reordering information is not reflected in the qasm-code if there are no measurement statements in the original circuit - which is the case if the original circuit contains the .save_unitary() statement.
So in that case the renumbering information is lost from the transpiled circuit which makes the resulting gates sequence / qasm code not reflect the original circuit, less the resulting unitary matrix.

This real life example shows the effect: Transpile has optimized away the swap back and instead renumbered the qubits. Without that information the sequence of gates does not represent the original circuit.

So I propose that the qasm() of the transpiled circuit should contain the reordering information even if no measurements are present.

Qiskit / qiskit