Projection circuits are really large

[MDeiml]

With the current implementation, the projection circuits grow exponentially with the number of actual tree levels (that cannot be compressed into tensor factors). This is because the result of each child is uncomputed again after computing the result of the parent

unitaria/src/unitaria/subspace.py

Lines 384 to 386 in bf4bb21

	circuit = (
	circuit + tq.gates.X(target=flag, control=intermediate_flags) + tq.gates.X(target=flag) + circuit.adjoint()
	)

Subspace("000") & (Subspace("##") | (Subspace("#") | Subspace("0")))
circuit:
X(target=(2,))
X(target=(7,), control=(2,))
X(target=(7,), control=(2,))
X(target=(2,))
X(target=(1,), control=(2,))
X(target=(8,), control=(1, 2))
X(target=(8,), control=(1, 2))
X(target=(1,), control=(2,))
X(target=(0,), control=(1, 2))
X(target=(8,), control=(0, 1, 2))
X(target=(8,), control=(1, 2))
X(target=(0,), control=(1, 2))
X(target=(8,), control=(2,))
X(target=(7,), control=(8, 2))
X(target=(7,), control=(2,))
X(target=(8,), control=(2,))
X(target=(0,), control=(1, 2))
X(target=(8,), control=(1, 2))
X(target=(8,), control=(0, 1, 2))
X(target=(0,), control=(1, 2))
X(target=(1,), control=(2,))
X(target=(8,), control=(1, 2))
X(target=(8,), control=(1, 2))
X(target=(1,), control=(2,))
X(target=(7,))
X(target=(3,))
X(target=(4,))
X(target=(5,))
X(target=(6,), control=(7, 3, 4, 5))
X(target=(6,))
X(target=(5,))
X(target=(4,))
X(target=(3,))
X(target=(7,))
X(target=(1,), control=(2,))
X(target=(8,), control=(1, 2))
X(target=(8,), control=(1, 2))
X(target=(1,), control=(2,))
X(target=(0,), control=(1, 2))
X(target=(8,), control=(0, 1, 2))
X(target=(8,), control=(1, 2))
X(target=(0,), control=(1, 2))
X(target=(8,), control=(2,))
X(target=(7,), control=(2,))
X(target=(7,), control=(8, 2))
X(target=(8,), control=(2,))
X(target=(0,), control=(1, 2))
X(target=(8,), control=(1, 2))
X(target=(8,), control=(0, 1, 2))
X(target=(0,), control=(1, 2))
X(target=(1,), control=(2,))
X(target=(8,), control=(1, 2))
X(target=(8,), control=(1, 2))
X(target=(1,), control=(2,))
X(target=(2,))
X(target=(7,), control=(2,))
X(target=(7,), control=(2,))
X(target=(2,))

This is of course good to reduce the number of needed ancillas, but on real hardware the number of bits is not the limiting factor, rather the number of operations.

Subspaces corresponding to Subspace.from_dim are especially inefficient. In the above case corresponding to dim=7 it would have been enough to exclude the 111 case.

[MDeiml]

One solution, which we should probably consider at some point in any way, is to have a more sophisticated way of allocating ancillas. Maybe each node / subspace could communicate not only a minimum, but also a maximum number of ancillas that it would like.

The other, probably simpler solution is to improve the result for the from_dim case specifically. Concretely, in this case only one of the children matters, while the other is either full or empty.