Kvantumos bonyolultsági osztályok
A következő kvantumalgoritmusok szeminárium témája:
Téma
- Cím: Kvantumos bonyolultsági osztályok
- Előadó: Csatári Jakab
Koordináták
- Időpont: 2023. május 19. péntek, 10:15 - 11:15
- Helyszín: IB134-es terem (BME I épület, 1. emelet, SZIT tanszéken belül)
Absztrakt
Egy idei cikk egyik eredményét dolgoznám fel, ami arról szól hogy relációs bonyolultsági osztályokat hogyan érint kvantum vs klasszikus advice string.
A cikk: A Qubit, a Coin, and an Advice String Walk Into a Relational Problem - Scott Aaronson, Harry Buhrman, William Kretschmer (https://arxiv.org/abs/2302.10332)
És az első eredményükről szeretnék beszélni, az FBQP/poly és FBQP/qpoly közötti szeparációról.