科学研究
报告题目:

布尔函数的精确量子查询算法

报告人:

郑盛根(鹏城实验室)

报告时间:

报告地点:

腾讯会议ID:467 267 018 会议密码:1106

报告摘要:

所有n位布尔函数的精确经典查询复杂度被证明都为n.在量子查询复杂度方面上,早在1998年,Beals等(FOCS’98)证明了n位的与函数(AND)的精确量子查询复杂度也为n.所以学者们一般认为,在精确查询算法方面上,只是对某些特殊的布尔函数,量子相对于经典才会有优势。我们证明了除和AND函数同构的布尔函数之外,其它n位布尔函数的精确量子查询复杂度都小于n。也就是说几乎所有n位布尔函数的精确量子查询复杂度都小于n。这个结果使我们对精确量子算法的优势在广度上有了新的认识。同时,我们将一次精确查询算法进行刻画和对DJ算法进行了推广。