Abstrakt. Detta papper använder ett kraftfullt argument, som kallas ett algoritmiskt argument, för att bevisa lägre gränser för kvantfrågan komplexitet av en flera block beställd sökproblem där, med tanke på ett block nummer i, vi ska hitta en plats för ett mål sökord i en beställd lista över ith blocket. Bortsett från mycket studerade polynom och motståndare metoder för kvantförfrågan komplexitet lägre gränser, vårt argument visar att flera block beställda sökning behöver ett stort antal icke adaptiva orakel frågor på en svart-box modell av kvantberäkning som också kompletteras med råd. Vårt argument tillämpas också på begreppen beräknings komplexitetsteori: kvant sanningstabell reducerbarhet och kvant sanningstabell autoreducerbarhet. Nyckelord: algoritmiskt argument, frågekomplexitet, icke adaptiv fråga, rådgivning, kvantberäkning, beställd sökning Ett viktigt bidrag av detta papper är demonstrationen av ett kraftfullt argument, som vi hänvisar till algoritmiskt argument, för att bevisa en lägre gräns för den icke adaptiva frågekomplexiteten för ett flerblocksbeställd sökproblem på rekommenderad kvantberäkning. I litteraturen, kvantförfrågan komplexitet lägre gränser har bevisats av klassiska motståndare metoder [11], polynom metoder [8], och kvant motståndare metoder [5, 7, 27]. Varje metod har sin egen styrka och fördelar över sin enkelhet, klarhet och fingerfärdighet. Ett algoritmiskt argument skiljer sig emellertid i grunden från dessa metoder på ett konstruktivt sätt. Ett grundläggande schema för vårt algoritmiska argument illustreras enligt följande: vi (i) börjar med det felaktiga antagandet att en kvantalgoritm A med låg frågekomplexitet existerar, (ii) definierar ett kompressionssystem E som kodar varje ingång s av fast längd i en kortare sträng E(s), och (iii) bevisar den en-till-enhet E genom att konstruera en avkodningsalgoritm från A som unikt extraherar s från E(s), vilket leder till en iögonfallande motsägelse mot duvhålsprincipen †. I den här artikeln bygger vi en klassisk algoritm som avkodar E(s) genom att simulera A på ett deterministiskt sätt. Därför drar vi slutsatsen att alla kvantalgoritmer bör kräva hög fråge komplexitet. När ytterligare modeller "uniforma" kvantberäkning kan vi använda resursbunden Kolmogorov komplexitet som ett tekniskt verktyg i stället för duvhålsprincipen. Vi tillämpar vårt algoritmiska argument för att få en ny icke adaptiv frågekomplexitet lägre bunden på en frågekalkylmodell, känd som en quantumdator (som ibland kallas ett kvantnätverk [8] ), där en fråga är en viktig metod för att få tillgång till information som lagras utanför datorn. Det minsta antalet sådana frågor, känd som frågan komplexitet, mäter den minsta mängden information som krävs för att avsluta den önskade beräkningen. Fråga komplexitet lägre gränser på olika kvant beräkningsmodeller har studerats för många problem, inklusive beställd sökning [4, 18, 24, 27], obeställd sökning [5, 8, 9, 11], element särskiljbarhet [6, 17, 36], och kollision [1, 6, 36]. En kvantdator i black-box börjar med ett fast initialtillstånd (t.ex., 0 · · 0 ), får tillgång till en given källa x (som kallas "orakel") genom frågor-"vad är binärvärdet på plats i x?"-och ger en önskad lösning med liten felsannolikhet. Om någon fråga (utom den första) väljs enligt svaren på sina tidigare frågor, är en sådan frågemönster konventionellt kallas adaptiv. Adaptive
För det andra, i REF, ger Nishimura och Yamakami lägre gränser på den icke adaptiva kvantförfrågan komplexitet av en flera block variant av den beställda sökproblem.
An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation
{'venue': 'Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science (MFCS2004), Lecture Notes in Computer Science 3153, pp. 827-838, 2004', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics']}