Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed

Despite intensive research, the physical origin of the speed-up offered by quantum algorithms remains mysterious. No general physical quantity, like, for instance, entanglement, can be singled out as the essential useful resource. Here we report a close connection between the trace speed and the quantum speed-up in Grover's search algorithm implemented with pure and pseudo-pure states. For a noiseless algorithm, we find a one-to-one correspondence between the quantum speed-up and the maximal trace speed that occurs during the algorithm operations. For time-dependent partial depolarization and for interrupted Grover searches, the speed-up can be bounded by the maximal trace speed. Our results quantify the quantum speed-up with a physical resource that is experimentally measurable and related to multipartite entanglement and quantum coherence.