Quantifying computational advantage of Grover’s algorithm with the trace speed
Abstract 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 an...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | article |
| Language: | EN |
| Published: |
Nature Portfolio
2021
|
| Subjects: | |
| Online Access: | https://doaj.org/article/d6b0b61ac3d9426e9f5be5d58874ebfa |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Abstract 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 polarization of the pseudo-pure state, which can be connected to a wide class of quantum statistical speeds. For time-dependent partial depolarization and for interrupted Grover searches, the speed-up is specifically bounded by the maximal trace speed that occurs during the algorithm operations. Our results quantify the quantum speed-up with a physical resource that is experimentally measurable and related to multipartite entanglement and quantum coherence. |
|---|