求图中点度数的量子算法
Quantum algorithm for finding degrees
- 中山大学学报(自然科学版)(中英文) 2024年63卷第1期 页码：1-9
- 作者机构：
中山大学计算机学院，广东 广州 510006
- 作者简介：
郎健翔（1999年生），男；研究方向：量子计算；E-mail：langjx3@mail2.sysu.edu.cn
李绿周（1981年生），男；研究方向：量子计算；E-mail：lilvzh@mail.sysu.edu.cn
- 基金信息：国家自然科学基金(62272492);广东省基础与应用基础研究基金(2020B1515020050)
DOI：10.13471/j.cnki.acta.snus.2023A070
中图分类号： TP301.6纸质出版日期：2024-01-25，
网络出版日期：2023-12-18，
收稿日期：2023-09-07，
录用日期：2023-11-02
扫 描 看 全 文
郎健翔,李绿周.求图中点度数的量子算法[J].中山大学学报(自然科学版)(中英文),2024,63(01):1-9.
LANG Jianxiang,LI Lüzhou.Quantum algorithm for finding degrees[J].Acta Scientiarum Naturalium Universitatis Sunyatseni,2024,63(01):1-9.
郎健翔,李绿周.求图中点度数的量子算法[J].中山大学学报(自然科学版)(中英文),2024,63(01):1-9. DOI： 10.13471/j.cnki.acta.snus.2023A070.
LANG Jianxiang,LI Lüzhou.Quantum algorithm for finding degrees[J].Acta Scientiarum Naturalium Universitatis Sunyatseni,2024,63(01):1-9. DOI： 10.13471/j.cnki.acta.snus.2023A070.
摘要
本文探讨了图属性测试问题的量子加速：对于给定的图和整数
<math id="M1"><mi>k</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229717&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229714&type=
1.43933344
2.28600001
，图中是否存在一个度数为
<math id="M2"><mi>k</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229717&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229714&type=
1.43933344
2.28600001
的顶点？该问题的量子复杂度在邻接矩阵oracle模型下被证明为
<math id="M3"><mi mathvariant="normal">𝒪</mi><mfenced separators="|"><mrow><mi>N</mi><mroot><mrow><mi>k</mi></mrow><mrow/></mroot></mrow></mfenced></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229668&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229665&type=
12.95400047
5.41866684
，而其经典复杂度为
<math id="M4"><mi mathvariant="normal">Ω</mi><mfenced separators="|"><mrow><msup><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup></mrow></mfenced></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229674&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229671&type=
8.97466660
3.80999994
，其中
<math id="M5"><mi>N</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229682&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229679&type=
2.28600001
2.28600001
是图中顶点的数量. 为了证明该结果，得出了一个技术性结论，即对于给定的函数
<math id="M6"><mi>g</mi><mtext> </mtext><mo>:</mo><mtext> </mtext><mfenced open="[" close="]" separators="|"><mrow><mi>N</mi></mrow></mfenced><mo>→</mo><mo stretchy="false">{</mo><mn mathvariant="normal">0
1</mn><mo stretchy="false">}</mo></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229689&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229686&type=
22.18266678
3.30200005
和整数
<math id="M7"><mi>k</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229717&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229714&type=
1.43933344
2.28600001
，存在一个量子算法可以在
<math id="M8"><mi mathvariant="normal">𝒪</mi><mfenced separators="|"><mrow><mroot><mrow><mi>N</mi><mi>k</mi></mrow><mrow/></mroot></mrow></mfenced></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229702&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229699&type=
12.19200039
5.41866684
次查询内判定
<math id="M9"><mfenced open="|" close="|" separators="|"><mrow><mfenced open="{" close="}" separators="|"><mrow><mi>x</mi><mo>:</mo><mi>g</mi><mfenced separators="|"><mrow><mi>x</mi></mrow></mfenced><mo>=</mo><mn mathvariant="normal">1</mn></mrow></mfenced></mrow></mfenced></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229711&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229706&type=
18.88066673
4.57200003
是否等于
<math id="M10"><mi>k</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229717&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229714&type=
1.43933344
2.28600001
.文中的结果基于量子奇异值变换（QSVT）和有误差输入的量子搜索技术.
Abstract
Quantum speedups for the graph property testing problem is studied： For a given graph and an integer
<math id="M11"><mi>k</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229782&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229779&type=
1.69333339
2.62466669
， does the graph have a vertex of degree
<math id="M12"><mi>k</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229782&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229779&type=
1.69333339
2.62466669
？ The quantum complexity of this problem is proven to be
<math id="M13"><mi mathvariant="normal">𝒪</mi><mfenced separators="|"><mrow><mi>N</mi><mroot><mrow><mi>k</mi></mrow><mrow/></mroot></mrow></mfenced></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229737&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229734&type=
15.15533447
6.34999990
under the adjacency matrix oracle model， whereas its classical complexity is
<math id="M14"><mi mathvariant="normal">Ω</mi><mfenced separators="|"><mrow><msup><mrow><mi>N</mi></mrow><mrow><mn mathvariant="normal">2</mn></mrow></msup></mrow></mfenced></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229744&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229740&type=
10.41399956
4.31799984
， where
<math id="M15"><mi>N</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229750&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229747&type=
2.62466669
2.62466669
is the number of vertexes in the graph. In order to prove the result， a technical result that there exists a quantum algorithm for deciding whether
<math id="M16"><mfenced open="|" close="|" separators="|"><mrow><mfenced open="{" close="}" separators="|"><mrow><mi>x</mi><mtext> </mtext><mo>:</mo><mtext> </mtext><mi>g</mi><mfenced separators="|"><mrow><mi>x</mi></mrow></mfenced><mo>=</mo><mn mathvariant="normal">1</mn></mrow></mfenced></mrow></mfenced></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229757&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229753&type=
23.53733444
5.33400011
equals
<math id="M17"><mi>k</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229782&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229779&type=
1.69333339
2.62466669
or not in
<math id="M18"><mi mathvariant="normal">𝒪</mi><mfenced separators="|"><mrow><mroot><mrow><mi>N</mi><mi>k</mi></mrow><mrow/></mroot></mrow></mfenced></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229770&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229767&type=
14.22399998
6.34999990
queries， for a given function
<math id="M19"><mi>g</mi><mo>:</mo><mtext> </mtext><mfenced open="[" close="]" separators="|"><mrow><mi>N</mi></mrow></mfenced><mo>→</mo><mo stretchy="false">{</mo><mn mathvariant="normal">0
1</mn><mo stretchy="false">}</mo></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229777&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229773&type=
25.06133461
3.80999994
and an integer
<math id="M20"><mi>k</mi></math>
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229782&type=
https://html.publish.founderss.cn/rc-pub/api/common/picture?pictureId=53229779&type=
1.69333339
2.62466669
is obtained. These results are based on the techniques of quantum singular value transformation（QSVT） and quantum search on bounded-error inputs.
关键词
量子奇异值变换量子算法图属性测试
Keywords
quantum singular value transformationquantum algorithmgraph property testing
references
AARONSON S， BEN-DAVID S， KOTHARI R， et al， 2021. Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem［C］//Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing， 6 C： 1330-1342.
AMBAINIS A， BALODIS K， IRAIDS J， et al， 2020. Quantum lower and upper bounds for 2d-grid and Dyck language［C］//45th International Symposium on Mathematical Foundations of Computer Science， 8.
BALASUBRAMANIAN R， RAMAN V， SRINIVASARAGAVAN G， 1997. Finding scores in tournaments［J］. J Algorithms， 24（2）： 380-394.
BERETTA L， NARDINI F M， TRANI R， et al， 2019. An optimal algorithm to find champions of tournament graphs［C］//International Symposium on String Processing and Information Retrieval： 267-273.
BRASSARD G， HOYER P， MOSCA M， et al， 2002. Quantum amplitude amplification and estimation［J］. Contemp Math， 305： 53-74.
BUHRMAN H， CLEVE R， de WOLF R， et al， 1999. Bounds for small-error and zero-error quantum algorithms［C］//Proceedings of the 40th Annual Symposium on Foundations of Computer Science： 358-368.
DEY P， 2017. Query complexity of tournament solutions［C］//Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence， 31（1）： 2992-2998.
GILYÉN A， SU Y， LOW G H， et al， 2019. Quantum singular value transformation and beyond： Exponential improvements for quantum matrix arithmetics［C］//Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing：193-204.
GOLDREICH O， 2017. Introduction to property testing［M］. Cambridge： Cambridge University Press.
GOYAL D， JAYAPAUL V， RAMAN V， 2020. Elusiveness of finding degrees［J］. Discrete Appl Math， 286： 128-139.
GUTIN G， MERTZIOS G B， REIDL F， 2018. Searching for maximum out-degree vertices in tournaments［EB/OL］. arXiv：1801.04702.
HØYER P， MOSCA M， de WOLF R， 2003. Quantum search on bounded-error inputs［M］//Baeten J C M， et al， Eds. Automata， Languages and Programming. Heidelberg： Springer， 291-299.
KULKARNI R， PODDER S， 2015. Quantum query complexity of subgraph isomorphism and homomorphism［EB/OL］. arXiv： 1509.06361.
LOW G H， CHUANG I L， 2017. Hamiltonian simulation by uniform spectral amplification［EB/OL］. arXiv： 1707.05391.
MAGNIEZ F， SANTHA M， SZEGEDY M， 2007. Quantum algorithms for the triangle problem［J］. SIAM J Comput， 37（2）： 413-424.
MARTYN J M， ROSSI Z M， TAN A K， et al， 2021. Grand unification of quantum algorithms［J］. PRX Quantum， 2（4）： 040203.
MONTANARO A， de WOLF R， 2016. A survey of quantum property testing［J］. Theory Comput， 7： 1-81.
ROSENBERG A L， 1973. On the time required to recognize properties of graphs： A problem［J］. ACM SIGACT News， 5（4）： 15-16.
SUN X， YAO A C， ZHANG S， 2004. Graph properties and circular functions： How low can quantum query complexity go？［C］//Proceedings of 19th IEEE Annual Conference on Computational Complexity： 286-293.
YODER T J， LOW G H， CHUANG I L， 2014. Fixed-point quantum search with an optimal number of queries［J］. Phys Rev Lett， 113（21）： 210501.
0
浏览量
24
下载量
0
CSCD
- 网络PDF下载
- Meta-XML下载
- BibTeX下载
- Endnote下载
- RefMan 下载
- NoteExpress下载
- NoteFirst下载
关联资源
相关文章
相关作者
相关机构
- 地址：广州市海珠区新港西路135号 中山大学南校园东北区311栋 邮编：510275
- 联系电话：020-84112585，84113223 Email：xuebaozr@mail.sysu.edu.cn
- 技术支持由北京北大方正电子有限公司提供 京ICP备09064830号-19
京公网安备11010802024621 - 本系统建议在Chrome、 IE9+ 以上版本浏览器阅读本站内容，360浏览器请切换至极速模式
- Cookies帮助我们提供服务并提供个性化体验。使用本网站，即表示您同意我们使用Cookies
