Vi anser kvanttid komplexiteten i alla par kortaste vägar (APSP) problem och några av dess varianter. Den triviala klassiska algoritmen för APSP och mest alla par sökvägar problem körs i O(n 3 ) tid, medan den triviala algoritmen i kvantinställningen körs i Õ(n 2.5 ) tid, med Grover sökning. Ett stort öppet problem i klassiska algoritmer är att erhålla en verkligt subkubisk tidsalgoritm för APSP, dvs. En algoritm som körs i O(n 3−ε ) tid för konstant ε > 0. För att närma sig detta problem har många riktigt subkubiska tid klassiska algoritmer utformats för APSP och dess varianter för strukturerade ingångar. Några exempel på sådana problem är APSP i geometriskt viktade grafer, grafer med små heltal kant vikter eller ett litet antal vikter incident till varje vertex, och alla par tidigaste ankomst problem. I detta dokument ser vi över dessa problem i kvantinställningen och får den första nontrivial (dvs. O(n 2.5−ε ) tid) kvantalgoritmer för problemen.
APSP och APBP kan enkelt beräknas i tid O(n 2.5 ) på kvantdatorer REF.
Quantum algorithms for shortest paths problems in structured instances
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Physics']}