Inefficient 1Q sequences in -O3

ecpeterson commented 3 years ago

Information

Qiskit Terra version: 0.17
Python version: 3.7
Operating system: macOS Catalina

What is the current behavior?

synthesis(..., optimization_level=3, translation_method='synthesis') emits programs with inefficient 1Q subsequences.

Steps to reproduce the problem

Supply any sufficiently complex circuit (e.g., a quantum volume circuit) to the synthesis routine with optimization level turned up.

What is the expected behavior?

Each 1Q subsequence should be efficient, e.g., should apply sx no more than twice.

Suggested solutions

The _unroll set of passes (UnitarySynthesis specifically) is un-doing some of the work of _opt (Optimize1qDecompose specifically). I think what’s happening is:

ConsolidateBlocks produces operation strings like u q[0] q[1]; v q[1] q[2];, where u and v are opaque two-qubit unitaries.
UnitarySynthesis subsequently throws single-qubit sequences onto q[1] after u and before v.
No one then merges + resynthesizes that pair of sequences.

For an 8x8 quantum volume circuit, this pushes the depth up from ~340 to ~400 — a significant effect.

Omitting _unroll entirely works fine for QV circuits targeting IBM devices, but the purpose of _unroll was to re-nativize any non-native output that _opt may have emitted. So long as we're concerned about that, we'll have to install a more delicate fix. For instance, we might run an analysis pass which checks for instructions outside of basis_gates, and only apply _unroll if any are found — though I'm not sure that this is sufficient logic.

mtreinish commented 3 years ago

I like the proposed solution of an analysis pass to detect for gates outside the basis and condition running the basis translation passes on that. We only added the _unroll piece to the optimization loop in https://github.com/Qiskit/qiskit-terra/pull/6133 and https://github.com/Qiskit/qiskit-terra/pull/5671 as a stop gap for two passes injecting gates outside the basis into the circuit, mainly commutative cancellation (which has been fixed to be basis aware since https://github.com/Qiskit/qiskit-terra/pull/5672 ) and gate/cx direction. But if we detected whether or not we actually needed to do that seems like a reasonable improvement on that.

irajput commented 3 years ago

I'd like to work on this!

jlapeyre commented 3 years ago

Can someone supply something like a MWE? @irajput passed me the following example. After the first pair of passes ConsolidateBlocks, UnitarySynthesis, the subsequences with more than one pair of SXs are gone and do not reappear. Is the circuit not complicated enough?

from qiskit.circuit.library import QuantumVolume
from qiskit import *

from qiskit.test.mock import FakeBelem
qcomp = FakeBelem()

qv_circuit=QuantumVolume(3)
qv_circuit.draw()

from IPython.display import display
from qiskit.converters import dag_to_circuit
from qiskit.transpiler import TransformationPass

def callback_func(pass_,dag, time, property_set, count):
    if True:    
#    if isinstance (pass_, TransformationPass):
        circuit = dag_to_circuit(dag)
        print(pass_.name())
        display(circuit.draw(output='mpl'))

transpile(qv_circuit,backend=qcomp, optimization_level=3,callback=callback_func,translation_method='synthesis').draw(output='mpl')

EDIT: I have checked out terra v0.17 here. EDIT: Mon Aug 9 07:20:15 PM EDT 2021. @irajput gave me an corrected version of the example posted here.

Qiskit / qiskit