Recursively controlling a circuit takes exponential time and memory

[nonhermitian]

Environment

• Qiskit version: 1.0
• Python version: 3.12
• Operating system: OSX and Linux

What is happening?

Recursively adding controls to an initial sub-circuit will cause Qiskit to hang, using up ever increasing CPU and memory resources. E.g. the below will never complete, but taking N=5 or so will.

N = 10
sub_qc = QuantumCircuit(1)
sub_qc.x(0)

out = QuantumCircuit(N)
out.compose(sub_qc,range(sub_qc.num_qubits), inplace=True)

for kk in range(N-1):
    sub_qc = sub_qc.control()
    out.compose(sub_qc,range(sub_qc.num_qubits), inplace=True)

How can we reproduce the issue?

Run above

What should happen?

It should not take apparently exponential time

Any suggestions?

No response

[jakelishman]

This is because control by default, for historical reasons, performs an eager synthesis of the control operation, so the scaling is fairly naturally super-linear (for arbitrary controlled gates). The solution for the simple representation of the objects is to use the modern form that @alexanderivrii has been getting in place, where controls, inverses and gate powers are represented as modifier tags on the gate, and only realised at synthesis time. In your example, setting annotated=True in the control call will make this script work in linear time of N (edit: actually, it's quadratic in N because we create a gate with 1, then 2, ... N qubits, but the actual creation of the gate object doesn't scale exponentially)

That said, when it actually comes to synthesising the gates through transpile, you're still almost certainly going to see the super-linear blow up. Our arbitrary-control syntheses probably aren't the best they can be yet, but I think the general case is still going to scale quite a lot with the number of controls.

[jakelishman]

Just as an immediate copy-pastable example of the above:

from qiskit import QuantumCircuit

N = 100
sub_qc = QuantumCircuit(1)
sub_qc.x(0)

out = QuantumCircuit(N)
out.compose(sub_qc,range(sub_qc.num_qubits), inplace=True)

for kk in range(N-1):
    sub_qc = sub_qc.control(annotated=True)
    out.compose(sub_qc,range(sub_qc.num_qubits), inplace=True)

[jakelishman]

Fwiw, slightly better form for this would be to do:

from qiskit import QuantumCircuit

N = 100
sub_qc = QuantumCircuit(1)
sub_qc.x(0)
sub = sub_qc.to_gate()

out = QuantumCircuit(N)
out.append(sub, range(sub.num_qubits))

for kk in range(N-1):
    sub = sub.control(annotated=True)
    out.append(sub, range(sub.num_qubits))

compose is a circuit-inlining method, where a circuit represents a program. A single object in a circuit is a Gate (if unitary) or Instruction (if not), and that's the base blocking structure of the object and how it's pulled through the transpiler. Using the native block structure like that (rather than inlining things with compose) will be / should be better for performance longer term, especially as our things like synthesis of these gate annotations improves, because the tranpsiler will be able to retain the abstract/logical structure of the circuit for more longer, and do operations on large-scale abstract components, rather than a flattened structure caused by over-use of compose. compose is of course better when you want the structures to be merged / inlined, but I don't think this particular example is one of those.

[nonhermitian]

Ok thanks. I am trying to benchmark various aspects of Qiskit, and this one broke things, where as other frameworks can handle the controlled circuit.

Is there anyway for an user to find out what annotated=True does in the control? I cannot seem to find it. Also, if it prevents blow-up, why is it not on by default?

[jakelishman]

It's not on by default because that would have been a major breaking API change, and we're not confident that it's as well supported through the entire stack as the current form yet. It will become the default once it and its synthesis have matured a little more - I'd imagine changing the default of control will be one of the API breaks of Qiskit 2.0.

For example, at the moment, the multiple control form of annotated gate isn't merging the controlled modifiers into one, nor do the transpiler passes that synthesise the annotated forms of the gates, so we'll still effectively be doing the same looped calls you were underneath. That's not super hard to fix of course, just an indication of the newness of the feature in Qiskit.

What are you meaning by "any way for a user to find out what it does?"? It's a modifier, so it doesn't really do anything (in the sense of the eager synthesis of ControlledGate) does on the spot. How it gets synthesised to actual hardware depends (in theory, not yet in practice) on the basis gates and coupling constraints of the hardware, which isn't defined at the point of creating an abstract circuit, but would happen during compilation.

[nonhermitian]

Yeah, no I answered my own question when I tried to change the basis on the circuit and it just kept running.

It also modifies the circuit drawing, which is not too important, but unexpected.

[alexanderivrii]

Continuing with Jake's example, here are a few thoughts on the following synthesis step:

An expression of the form sub.control(annotated=True) ... .control(annotated=True) would actually combine all of the control modifiers into a single list, that is create an "annotated operation" whose "base operation" is sub and whose modifiers are the list [ControlModifier(1), ..., ControlModifier(1)].

For N=10, synthesizing this directly is very slow, but we do have a new transpiler pass OptimizeAnnotated in Qiskit 1.0 that canonicalizes the modifiers, that is replaces the list of modifiers by a single control modifier with multiple controls. We are still investigating how to best integrate it into the transpiler flow, so it's not on by default, but one would use this along the following lines:

from qiskit.transpiler.passes import OptimizeAnnotated
basis_gates = ['cx', 'id', 'u']
out = OptimizeAnnotated(basis_gates=basis_gates)(out)

The pass is recursive, descending into the definitions of custom gates, and it needs basis gates and equivalence library to know which definitions to examine and which to skip.

For N=10, the optimized circuit out is now susceptible to transpilation (i.e. to either transpile or to HighLevelSynthesis). However the approach still does not scale to much larger values of N. If I recall correctly (not too sure about this), our algorithm for synthesizing multiply-controlled gates without ancilla qubits produces exponentially many gates. And, needless to say, a synthesis algorithm that produces exponentially many gates requires exponential runtime.

One could do a bit better by replacing the code

sub_qc = QuantumCircuit(1)
sub_qc.x(0)
sub = sub_qc.to_gate()

by

sub = XGate()

in which case the synthesis algorithm would treat the annotated sub essentially as an MCX-gate, producing half as many gates and somewhat decreasing runtime, but unfortunately our synthesis algorithm ("mcx_gray") for MCX-gates without ancillas still produces exponentially many gates.

[ShellyGarion]

Indeed, it seems that the current synthesis algorithms for multi-controlled gates could be improved. See the discussion in #5872