Complexity measure for continuous-time quantum algorithms
Dominik Janzing, T. Beth · Physical Review A · 2001
We consider unitary dynamical evolutions on n qubits caused by time-dependent pair-interaction Hamiltonians and show that the running time of a parallelized two-qubit gate network simulating the evolution is given by the time integral over the chromatic index of the interaction graph. This defines complexity measures of continuous and discrete quantum algorithms, which are in exact one-to-one correspondence. We prove a lower bound on the complexity of those multiparticle states, which show quantum superpositions on the macroscopic scale.