`Diagonal` from circuit library should not use inputs that scale exponentially.

[nonhermitian]

What should we add?

Currently the Diagonal circuit in the circuit library requires a NumPy array, or list that can be cast to a NumPy array, with $2^{N}$ elements, where $N$ is the number of qubits. As this is not scalable, a different input format should be found, e.g. a dict and or function, that contains / generates only the needed components.

[Raghav-Bell]

Please assign this issue to me.

[Cryoris]

Thanks for offering your support @Raghav-Bell.

Looking at the implementation, the current circuit generation iterates over the entire diagonal and to scales exponentially in number of qubits. With a sparse input this could potentially be optimized, you could e.g. have a look at the references paper https://arxiv.org/pdf/quant-ph/0406176.pdf (Theorem 7) or @ajavadia might have some insights.

If it's not possible, I think it would be important to point this hidden scaling out to users by adding a note in the documentation.

[Raghav-Bell]

@Cryoris After going through the reference, our diagonal unitary implementation is one of the efficient algorithm. But these references are quite old, some of the new reference demonstrated more optimized solution (some tradeoffs). One of which is stated below : This Efficient quantum circuits for diagonal unitaries without ancillas paper discusses approximate implementation of diagonal unitaries which requires polynomial number of gates as compared exponential (~2^n) number of gates in our current implementation. I don't know will it work or not. Kindly help me out with this.

[Cryoris]

The paper you're referencing seems to be implementing an approximation to the diagonal function. It would be an interesting project to implement this algorithm, but we should still keep the original one as an exact (but costly) version. If you're interested, we can implement the Walsh-based diagonal circuit as synthesis method.

For this PR we should restrict to updating only the input type.

[Raghav-Bell]

np.ndarray() is much faster & takes less memory as compared to dict . (see Looking up large sets of keys: dictionary vs. NumPy array) . But we can try rust-numpy crate or can add warning for exponential complexity.

[Cryoris]

I think the suggestion is to enable sparse inputs. For example, assume we want to add a phase of -1 on state $|5\rangle$ on 3 qubits. Right now we would have to do

diag = [1, 1, 1, 1, 1, -1, 1, 1]
circuit = Diagonal(diag)

but the idea would be to allow

diag = {5: -1}
circuit = Diagonal(diag)

This would become especially handy as the number of qubits increases.

[Raghav-Bell]

I have changed only unitest for now. I will add more tests after review.

[jakelishman]

Fwiw, the problem here is most likely not limited to specifying inputs in a manner that scales, it's also that the Diagonal gate would need to be able to use a sparse internal representation as well, otherwise we've not really solved the problem. That becomes a little bit more of a problem for how the format would subsequently be exposed via .params, since it will have very non-trivial impacts on how the gate would be serialised and handled by other parts of the Qiskit stack.

[jakelishman]

Come to think of it: Paul, what's the use case you're expecting here where there's a huge diagonal operator where the sparsity isn't already inherent in most of the affected qubits undergoing the identity (in which case the operator is a small-$n$ number of qubits and the dense storage is quite appropriate)? I'm assuming you've got a use-case for that, but just to be sure.

[jakelishman]

Also, last comment: the difficulties with managing the two types of internal state might mean that it's easier for us to handle if we introduce a new class such as SparseDiagonal that can have a completely different structure for its params field. I'm not a huge fan of that solution either tbh, but I'm just throwing it out there for comments by Paul and Julien about what might be better for their uses. Certainly the separate class is easier to manage as a library developer, since it would use a completely different internal data storage format, but it's not so great for users.

That said, consumers of our data structures are also our users, so there's likely a trade-off to be made.

[nonhermitian]

So I do not have an use case in particular, but I was pointed to Diagonal as a way to define Grover oracles. However, the requirement of a dense NumPy array for the $2^{N}$ diagonals makes that a no-go since the classical compute side of things would break before the quantum. As such, there needs to be a way to insert a sparse representation that populates only a small subset of diagonals with nonzero values.

[jakelishman]

And to be clear: this is a non-zero sparsity structure that's not inherently caused by most of the qubits undergoing the identity (since we can already represent that in a truly sparse manner)?