浏览全部资源
扫码关注微信
Quantum algorithm for finding degrees
- Acta Scientiarum Naturalium Universitatis Sunyatseni Vol. 63, Issue 1, Pages: 1-9(2024)
- 作者机构：
中山大学计算机学院，广东 广州 510006
- 作者简介：
- 基金信息：
DOI：10.13471/j.cnki.acta.snus.2023A070
CLC： TP301.6Published：25 January 2024，
Published Online：18 December 2023，
Received：07 September 2023，
Accepted：02 November 2023
扫 描 看 全 文
郎健翔,李绿周.求图中点度数的量子算法[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
Views
24
下载量
0
CSCD
- L-PDFDownload
- Meta-XMLDownload
- BibTeXDownload
- EndnoteDownload
- RefMan Download
- NoteExpressDownload
- NoteFirstDownload
Publicity Resources
Related Articles
Related Author
Related Institution
- Postal code：510275
- Tel：020-84112585，84113223 Email：xuebaozr@mail.sysu.edu.cn
- Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09064830号-19
京公网安备11010802024621 - It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
- Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.
