The time complexity of a QNN

PennyLane Help
1

Hello, everyone!

I would like to calculate the time complexity of a Quantum Neural Network (QNN). For this, I consider the implementation of a QNN as a series of matrix multiplications.

Suppose we have matrix A (size a x b) and matrix B (size b x c). The time complexity of multiplying A and B is O(abc).
Referenced link: Matrix multiplication algorithm time complexity

Now, consider a 4-qubit QNN as shown below. The input state is a 2^q-dimensional vector (q=4), which is multiplied by a series of 2^q x2^q matrices (there are 11 such matrices, as the depth of the QNN is 11).

As a result, the time complexity is O(11 x 2^q x 2^q) = O(11 x 4q) = O(4^q), where q=4.
Does this derivation of time complexity seem correct?

I’d be happy to discuss this further and welcome any feedback!

image
image1400×500 33.4 KB

Name: PennyLane
Version: 0.34.0
- default.gaussian (PennyLane-0.34.0)
- default.mixed (PennyLane-0.34.0)
- default.qubit (PennyLane-0.34.0)
...
2

Hi @q36111095 ,

I don’t have an answer about the complexity but I hope someone else here can jump in with some ideas about it!

I did notice though that you’re using v0.34 of PennyLane. Our latest version is v0.38 so this could be a good opportunity to update it :smiley: