Grover paieška ir jos juodosios dėžės apatinė riba
Tyrimų kontekstas
postgraduate concept · established · Patikros data 2026-10-10
Nestruktūruotai paieškai tarp N alternatyvų, turint koherentinį žymėjimo orakulą ir vieną pažymėtą elementą, amplitudės stiprinimas naudoja O(sqrt(N)) orakulo užklausų, kad sėkmės tikimybė būtų atskirta nuo nulio.
Esminės žinios
Nestruktūruotai paieškai tarp N alternatyvų, turint koherentinį žymėjimo orakulą ir vieną pažymėtą elementą, amplitudės stiprinimas naudoja O(sqrt(N)) orakulo užklausų, kad sėkmės tikimybė būtų atskirta nuo nulio. Šiame juodosios dėžės kvantinių užklausų modelyje galioja tokios pačios eilės apatinė riba. Palyginti su klasikine nestruktūruota užklausų paieška, pagreitėjimas yra kvadratinis, o ne eksponentinis kiekvienai paieškos užduočiai; orakulo konstravimas ir patikra gali lemti didžiąją tikrojo vykdymo laiko dalį.
Sąlygos ir taikymo ribos
- Aiškiai nurodytas standartinis vieno sprendinio pažadas, koherentinė prieiga prie orakulo ir skaičiuojamas išteklius.
- Kai žinoma, kad sprendinių yra daugiau, keičiasi sukimosi kampas; visiems atitikmenims rasti reikia papildomo darbo.
Šaltiniai · 2
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Autorius patikrino šį anglišką teiginį, pateiktą lygtį, jei ji yra, ir nurodytas prielaidas pagal šias šaltinių vietas: Kvantinės grandinės, Grover užklausų ir amplitudžių analizė, Shor periodo paieškos išteklių aptarimas; §IV: BQP ir išteklių bei orakulo modelis, §V: QMA pažadai ir 2-local Hamiltoniano teorema 8; istorinis apžvalginis straipsnis. Patikra apsiriboja užrašytais teiginiais; neteigiama, kad visiškai atkurtas įrodymas, pakartotinai atlikta programinė įrodymo patikra ar aprėpta visa literatūra.
2026-10-10 · Autoriaus atlikta šaltinio teksto, teiginio, lygties ir taikymo srities patikra; grafo sąsajų aprėptis nurodyta atskirai. Prieš užbaigiant šaką būtina atskira nepriklausoma turinio, šaltinių ir inventoriaus peržiūra.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- research-info-grover-query-speedup
- Versija
- research.1
- Struktūruotas žinyno įrašas
- Podiplominis ir tyrimų žinynas