Sciencemag.cz
Doporučujeme
Současná věda, ale stejně tak i IT, technické obory nebo medicína jsou závislé na rychlém zpracování dat z vnějších zdrojů – zvukových záznamů, statických obrázků, dat ze senzorů. Pro toto zpracování se používá především tzv. rychlá Fourierova transformace. Rychlá Fourierova transformace je algoritmus, který výrazně snižuje výpočetní náročnost diskrétní Fourierovy transformace (v limitě se výpočetní složitost mění z kvadratické až na lineární). Tento algoritmus byl původně určen pro řešení parciálních diferenciálních rovnic, ale rychle se uplatnil i v dalších aplikacích včetně digitálního zpracování signálu. Pro některé úlohy s velkými objemy dat je však tato metoda stále příliš pomalá.
Vědci z Fyzikální fakulty Varšavské univerzity (vydala příslušnou tiskovou zprávu) ve spolupráci s University of Oxford a NIST nyní ukázali, že tzv. kvantová interference umožňuje rychlejší a přesnější zpracování velkých souborů dat. Po delší době tak známe nový efektivní kvantový algoritmus. Ve skutečnosti jich totiž od 90. let, kdy byl objeven Shorův (faktorizace) a Groverův (vyhledávání) algoritmus zase tolik nepřibylo, navíc se často týkají zase spíše speciálních záležitostí kvantové fyziky/chemie než obecné informatiky.
Nový algoritmus vychází z tzv. Kravčukovy transformace (pro další hledání v anglicky psaných zdrojích: Kravtchuk, ale i Kravtouck), což je metoda podobná rychlé Fourierově transformaci. Ta se pokládá za výhodnou především pro zpracování dat obsahujících hodně šumu, např. algoritmů pro počítačové vidění u robotů nebo autonomních vozidel. Podle nové studie dokáže Kravčukovu transformaci přitom efektivně vypočítat i nejjednodušší kvantová brána (hradlo) s dvěma interferujícími kvantovými stavy. Bránu lze realizovat jednoduchým zařízením, děličem paprsků, který proud fotonů rozděluje mezi dva výstupy. Výpočet Kravčukovy transformace se realizuje pomocí interakcí (nerozlišitelných) fotonů vstupujících do zařízení. Nastavení původních stavů fotonů (tj. samotné zadání úlohy/zakódování vstupních dat) i přečtení výsledku bylo třeba provádět na speciálním zařízení (Transmission Edge Sensors) fungujícím při teplotách blízko absolutní nuly. Zajímavé u přečtení výsledku je to, že tato doba vůbec nezáleží na tom, jak složitá byla původní úloha, tj. na velikosti sady vstupních dat. Výpočet je třeba ovšem opakovat řádově stokrát, nicméně „statistická povaha“ platí pro všechny kvantové počítače. Zde to však nevadí, protože vstupní laser dokáže vytvářet každou sekundu desítky miliony vstupních stavů z více fotonů.
Má jít o postup přímo revoluční: výpočetní složitost je konstantní (teoreticky – jiná věc asi bude se vstupním kódováním, eventuálně s potřebným počtem opakování měření v závislosti na velikosti vstupu), vše se realizuje jedinou operací implementovanou v jediném kvantovém hradlu. Kromě samotného výpočtu Kravčukovy transformace by se tento postup mohl uplatnit i speciálně v kvantové fotonice a pro vývoj dalších odvozených kvantových algoritmů. Varšavská univerzita již požádala o mezinárodní patent.
„Quantum interference enables constant-time quantum information processing,“ Science Advances (2019). DOI: 10.1126/sciadv.aau9674 https://advances.sciencemag.org/content/5/7/eaau9674
Zdroj: Phys.org a další
Poznámky PH:
Samozřejmě jako obvykle u kvantových počítačů je nejméně pochopitelný ze všeho samotný algoritmus…
Otázka: Co na takovéhle věci lze přesně patentovat?
