Transpiler pass to remove gates with negligible effects

[kevinsung]

What should we add?

This pass would be very useful to ensure that negligible gates are not needlessly applied. In Cirq, whether a gate is negligible is determined by its implementation of the trace distance bound protocol: see https://github.com/quantumlib/Cirq/blob/3e3d6f7d9368badeafd0f2ca3ee0929ab0fdaa25/cirq-core/cirq/transformers/drop_negligible_operations.py. I'm not sure yet what would be the best way to implement this in Terra.

[mtreinish]

A new transformation pass as that runs as part of the optimization stage is probably the best approach. I'm not sure exactly what interface we'd want for this though. Or how you define the boundary between what is negligible impact or not.

The only knob we really have for something like this is approximation_degree which is just a a rough knob that has a value between 0.0 and 1.0 to specify how much you're willing to approximate. We could probably use this as the input and translate that into some tolerance value and filter based on something like what is done in the cirq example you cited.

[kevinsung]

I'm not sure exactly what interface we'd want for this though. Or how you define the boundary between what is negligible impact or not.

What do you think of adopting Cirq's approach? That is, defining a TraceDistanceBound Protocol that gates can implement. The optimization pass would take the requested tolerance as input (with a reasonable default) and a gate would be considered negligible if its trace distance bound were smaller than the specified tolerance.

See https://github.com/quantumlib/Cirq/blob/3e3d6f7d9368badeafd0f2ca3ee0929ab0fdaa25/cirq-core/cirq/protocols/trace_distance_bound.py for the Cirq Protocol.

[mtreinish]

That seems like a reasonable approach me, but I'd be curious what @ajavadia @levbishop and @kdk think.

If we go that way I think we'll probably just want to start with computing it just from the unitary for Gate instances that have their matrix defined and we'll need to add a similar trace distance function to quantum_info.

[kevinsung]

In general it's not practical to compute the bound from the gate's unitary since this can be an exponentially large matrix. Even if all the gates act on at most a few qubits, constructing the matrices explicitly may lead to a large overhead. These are the reasons to rely on the protocol.