Complexity and Time

Understand

For any quantum algorithm given by a path in the space of unitary operators we define the computational complexity as the typical computational time associated with the path.

• This time is defined using a quantum time estimator associated with the path.
• This quantum time estimator is fully characterized by the Lyapunov generator of the path and the corresponding quantum Fisher information.
• The computational metric associated with this definition of computational complexity leads to a natural characterization of cost factors on the Lie algebra generators.