论文标题：Quantum speedup and limitations on matroid property problems

期刊：Frontiers of Computer Science

作者：Xiaowei HUANG , Jingquan LUO , Lvzhou LI

发表时间：20 Apr 2023

DOI： 10.1007/s11704-023-3130-9

微信链接：点击此处阅读微信文章

针对一些基础拟阵问题（包括计算拟阵的围长、圈数目、基数目、平面数目和超平面数目，以及判定是否是均匀拟阵、欧拉拟阵和铺拟阵）的量子查询复杂度和量子算法，中山大学李绿周教授团队撰写了研究论文：关于拟阵问题的量子加速及局限性。

文章信息

标 题：

Quantum speedup and limitations on matroid property problems

引用格式：

Xiaowei HUANG, Jingquan LUO, Lvzhou LI. Quantum speedup and limitations on matroid property problems. Front. Comput. Sci., 2024, 18(4): 184905

阅读原文：

文章概述

文章旨在研究量子计算在解决拟阵问题上加速的可能性，在拟阵问题上寻找能够体现量子优势的问题结构，扩展量子计算的应用范围。

技术步骤

通过运用量子敌手法（Quantum Adversary Method）来求拟阵问题的量子查询复杂度的下界；然后基于量子搜索算法（Grover‘s Algorithm）设计相应的量子算法。

实验结果

结论表明，在如下基础拟阵问题上有量子加速的可能，相比经典至多有开平方的加速。

Frontiers of Computer Science

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办、SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，双月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华教授，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；入选“中国科技期刊卓越行动计划项目”。

《前沿》系列英文学术期刊

由教育部主管、高等教育出版社主办的《前沿》（Frontiers）系列英文学术期刊，于2006年正式创刊，以网络版和印刷版向全球发行。系列期刊包括基础科学、 、工程技术和人文社会科学四个主题，是我国覆盖学科最广泛的英文学术期刊群，其中12种被SCI收录，其他也被A&HCI、Ei、MEDLINE或相应学科国际权威检索系统收录，具有一定的国际学术影响力。系列期刊采用在线优先出版方式，保证文章以最快速度发表。

中国学术前沿期刊网

http://journal.hep.com.cn