测试量子态集合的同一性：样本复杂性分析

测试量子态集合的同一性：样本复杂性分析

时间戳记：11年2023月8日上午05:XNUMX
源节点： 2269126

马可·法尼扎1, 拉斐尔·丹参2及 维托里奥·乔瓦内蒂3

1科学技术：Informació i Fenòmens Quantics，Departament de Física，巴塞罗那自治大学，08193 Bellaterra，西班牙。
2Scuola Normale Superiore，I-56127 比萨，意大利。
3NEST，Scuola Normale Superiore 和 Istituto Nanoscienze-CNR，I-56127 比萨，意大利。

觉得本文有趣或想讨论？ 在SciRate上发表评论或发表评论.

抽象

我们研究了在给定样本访问未知量子态集合的情况下测试该集合的身份的问题，每个状态以某种已知的概率出现。 我们证明，对于基数为 $N$ 的 $d$ 维量子态集合，样本复杂度为 $O(sqrt{N}d/epsilon^2)$，具有匹配的下界，最高可达乘法常数。 该检验是通过估计状态之间的均方希尔伯特-施密特距离而获得的，这要归功于 Bădescu、O'Donnell 和 Wright 对两个未知状态之间的希尔伯特-施密特距离估计量的适当概括。13].

特色图片：我们的模型适用的两种设置。 在 a) 中，独立源产生一个随机数，泊松分布，在 $T$ 时间内状态副本。 在b)中，测量过程准备标记状态，每个标记以一定的概率出现。

►BibTeX数据

►参考

[1] Gerardo Adesso、Thomas R. Bromley 和 Marco Cianciaruso，“量子相关性的测量和应用”《物理学杂志 A：数学和理论》49, 473001 (2016)。
https:/​/​doi.org/​10.1088/​1751-8113/​49/​47/​473001
的arXiv：1605.00806

[2] Jayadev Acharya、Ibrahim Issa、Nirmal V. Shende 和 Aaron B. Wagner，“估计量子熵”IEEE 信息论选定领域期刊 1, 454–468 (2020)。
https：/ / doi.org/ 10.1109 / JSAIT.2020.3015235
https://ieeexplore.ieee.org/document/9163139/​

[3] Jayadev Acharya 和 Constantinos Daskalakis “测试泊松二项式分布”第二十六届年度 ACM-SIAM 离散算法 1829-1840 研讨会论文集 (2015)。
https：/ / doi.org/10.1137/ 1.9781611973730.122
的arXiv：1507.05952

[4] Daiki Akimoto 和 Masahito Hayashi “量子环境中变点的判别”物理评论 A 83, 052328 (2011)。
https：/ / doi.org/ 10.1103 / PhysRevA.83.052328
的arXiv：1102.2555

[5] Robert Alicki、Slawomir Rudnicki 和 Slawomir Sadowski，“N n 级原子系统的乘积态的对称性”，数学物理杂志 29，1158–1162 (1988)。
https：/ / doi.org/10.1063/ 1.527958

[6] 白戈、吴亚东、朱彦、Masahito Hayashi 和 Giulio Chiribella，“量子因果揭开” npj Quantum Information 8, 69 (2022)。
https:/​/​doi.org/​10.1038/​s41534-022-00578-4
的arXiv：2109.13166

[7] Tuğkan Batu、Eldar Fischer、Lance Fortnow、Ravi Kumar、Ronitt Rubinfeld 和 Patrick White，“测试随机变量的独立性和同一性”第 42 届 IEEE 计算机科学基础研讨会论文集 442-451 (2001)。
https：///doi.org/10.1109/SFCS.2001.959920
https://ieeexplore.ieee.org/document/959920/​

[8] Dave Bacon、Isaac L. Chuang 和 Aram W. Harrow，“Schur 和 Clebsch-Gordan 变换的高效量子电路”物理评论快报 97, 170502 (2006)。
https：/ / doi.org/ 10.1103 / PhysRevLett.97.170502
的arXiv：0407082

[9] Sebastien Bubeck、Sitan Chen 和 Jerry Li，“纠缠对于最佳量子特性测试是必要的”2020 年 IEEE 第 61 届计算机科学基础年度研讨会 (FOCS) 692-703 (2020)。
https:/ / doi.org/ 10.1109/ FOCS46700.2020.00070
的arXiv：2004.07869

[10] Charles H. Bennett、Igor Devetak、Aram W. Harrow、Peter W. Shor 和 Andreas Winter，“模拟量子通道的量子逆香农定理和资源权衡”IEEE Transactions on Information Theory 60, 2926–2959 (2014)。
https：///doi.org/10.1109/TIT.2014.2309968
http:// / ieeeexplore.ieee.org/ document/ 6757002/

[11] E. Bagan、S. Iblisdir 和 R. Muñoz-Tapia，“相对态、量子轴和量子参考”，物理评论 A 73, 022341 (2006)。
https：/ / doi.org/ 10.1103 / PhysRevA.73.022341
的arXiv：0508187

[12] Stéphane Boucheron、Gábor Lugosi 和 Pascal Massart，“浓度不等式”牛津大学出版社（2013 年）。
https：///doi.org/10.1093/acprof：oso / 9780199535255.001.0001

[13] Costin Bădescu、Ryan O'Donnell 和 John Wright，“量子状态认证”第 51 届年度 ACM SIGACT 计算理论研讨会论文集 503-514 (2019)。
https：/ / doi.org/10.1145/ 3313276.3316344
的arXiv：1708.06002

[14] Stephen D. Bartlett、Terry Rudolph 和 Robert W. Spekkens，“相对量子信息的最佳测量”Physical Review A 70, 032321 (2004)。
https：/ / doi.org/ 10.1103 / PhysRevA.70.032321
的arXiv：0310009

[15] Harry Buhrman、Richard Cleve、John Watrous 和 Ronald de Wolf，“量子指纹”物理评论快报 87, 167902 (2001)。
https：/ / doi.org/ 10.1103 / PhysRevLett.87.167902
的arXiv：0102001

[16] Clement L. Canonne “分布测试调查：您的数据很大。 但它是蓝色的吗？” 计算理论 1, 1–100 (2020)。
https：///doi.org/10.4086/toc.gs.2020.009
http://www.theoryofcomputing.org/articles/gs009

[17] Siu-On Chan、Ilias Diakonikolas、Paul Valiant 和 Gregory Valiant，“测试离散分布接近度的最优算法”第二十五届 ACM-SIAM 离散算法年度研讨会论文集 1193-1203 (2014)。
https：/ / doi.org/10.1137/ 1.9781611973402.88
的arXiv：1308.3946

[18] 马蒂亚斯·克里斯坦德尔（Matthias Christandl）“二分量子态的结构——群论和密码学的见解”（2006）。
的arXiv：0604183

[19] Sitan Chen、Jerry Li 和 Ryan O'Donnell，“通过不连贯的测量实现实例最优状态认证”学习理论第三十届会议论文集 178, 2541–2596 (2022) https:/​/​proceedings.mlr.press /​v178/​chen22b.html。
的arXiv：2102.13098

[20] 托马斯·M·科弗和乔伊·A·托马斯“信息论要素”(2005)。
https：/ / doi.org/ 10.1002 / 047174882X

[21] Ilias Diakonikolas 和 Daniel M. Kane “测试离散分布属性的新方法”2016 年 IEEE 第 57 届计算机科学基础年度研讨会 (FOCS) 685–694 (2016)。
https：///doi.org/10.1109/FOCS.2016.78
的arXiv：1601.05557
http:// / ieeeexplore.ieee.org/ document/ 7782983/

[22] Ilias Diakonikolas、Daniel M. Kane 和 Vladimir Nikishkin，“测试结构化分布的同一性”2015 年第 1841 届 ACM-SIAM 离散算法年度研讨会论文集，1854-2015 年（XNUMX 年）。
https：/ / doi.org/10.1137/ 1.9781611973730.123

[23] M. Fanizza、M. Rosati、M. Skotiniotis、J. Calsamiglia 和 V. Giovannetti，“超越交换测试：量子态重叠的最优估计”物理评论快报 124, 060503 (2020)。
https：/ / doi.org/ 10.1103 / PhysRevLett.124.060503
的arXiv：1906.10639

[24] Marco Fanizza、Christoph Hirche 和 John Calsamiglia，“最快量子变点检测的终极极限”Phys。 莱特牧师。 131, 020602 (2023)。
https：/ / doi.org/ 10.1103 / PhysRevLett.131.020602
的arXiv：2208.03265

[25] Marco Fanizza、Farzad Kianvash 和 Vittorio Giovannetti，“去极化通道量子容量的量子标志和新界限”物理评论快报 125, 020503 (2020)。
https：/ / doi.org/ 10.1103 / PhysRevLett.125.020503
的arXiv：1911.01977

[26] Marco Fanizza、Farzad Kianvash 和 Vittorio Giovannetti，“通过可降解扩展估计高斯通道的量子和私有容量”Phys。 莱特牧师。 127, 210501 (2021)。
https：/ / doi.org/ 10.1103 / PhysRevLett.127.210501
的arXiv：2103.09569

[27] N. Gisinand S. Iblisdir“量子相对状态”欧洲物理杂志 D 39, 321–327 (2006)。
https：///doi.org/10.1140/epjd/e2006-00097-y
的arXiv：0507118

[28] Oded Goldreich“财产测试简介”剑桥大学出版社（2017 年）。
https：/ / doi.org/10.1017/ 9781108135252

[29] Oded Goldreichand Dana Ron“关于有界度图的测试扩展”(2011)。
https:/​/​doi.org/​10.1007/​978-3-642-22670-0_9

[30] Jeongwan Haah、Aram W. Harrow、Zhengfeng Ji、Xiaodi Wu 和 Nengkun Yu，“量子态的最佳样本层析成像”IEEE Transactions on Information Theory 63, 1-1 (2017)。
https：///doi.org/10.1109/TIT.2017.2719044
的arXiv：1508.01797
http:// / ieeeexplore.ieee.org/ document/ 7956181/

[31] Aram W. Harrow“相干经典通信和 Schur 变换在量子信息理论中的应用”（2005 年）。
的arXiv：0512255

[32] Masahito Hayashi、Bao-Sen Shi、Akihisa Tomita、Keiji Matsumoto、Yoshiyuki Tsuda 和 Yun-Kun Jiang，“自发参数下转换产生的纠缠态的假设检验”Phys。 修订版 A 74, 062321 (2006)。
https：/ / doi.org/ 10.1103 / PhysRevA.74.062321

[33] Masahito Hayashi“量子信息的群理论方法”施普林格国际出版（2017）。
https:/​/​doi.org/​10.1007/​978-3-319-45241-8

[34] Masahito Hayashi“量子理论的小组代表”施普林格国际出版（2017）。
https:/​/​doi.org/​10.1007/​978-3-319-44906-7

[35] Masahito Hayashi“量子信息论”施普林格柏林海德堡（2017）。
https:/​/​doi.org/​10.1007/​978-3-662-49725-8

[36] Masahito Hayashi 和 Keiji Matsumoto“量子通用可变长度源编码”物理评论 A 66, 022311 (2002)。
https：/ / doi.org/ 10.1103 / PhysRevA.66.022311
的arXiv：0202001

[37] Masahito Hayashi 和 Marco Tomamichel “相关检测和 Rényi 互信息的操作解释”《数学物理杂志》57, 102201 (2016)。
https：/ / doi.org/10.1063/ 1.4964755
的arXiv：1408.6894

[38] Masahito Hayashi、Akihisa Tomita 和 Keiji Matsumoto，“基于泊松分布框架的纠缠态测试统计分析”《新物理学杂志》10, 043029 (2008)。
https:/​/​doi.org/​10.1088/​1367-2630/​10/​4/​043029

[39] L. Hendersonand V. Vedral “经典、量子和总相关性” 物理学杂志 A：数学与通论 34, 6899–6905 (2001)。
https:/​/​doi.org/​10.1088/​0305-4470/​34/​35/​315
的arXiv：0105028

[40] M. Keyl“量子状态估计和大偏差”数学物理评论 18, 19–60 (2006)。
https：/ / doi.org/ 10.1142 / S0129055X06002565

[41] Farzad Kianvash、Marco Fanizza 和 Vittorio Giovannetti，“通过标记扩展限制量子容量”Quantum 6, 647 (2022)。
https:/​/​doi.org/​10.22331/​q-2022-02-09-647
的arXiv：2008.02461

[42] Martin Klieschand Ingo Roth“量子系统认证理论”PRX Quantum 2, 010201 (2021)。
https：/ / doi.org/ 10.1103 / PRXQuantum.2.010201
的arXiv：2010.05925

[43] Hari Krovi “一种高效的高维量子 Schur 变换” Quantum 3, 122 (2019)。
https:/​/​doi.org/​10.22331/​q-2019-02-14-122
的arXiv：1804.00055
https：///quantum-journal.org/papers/q-2019-02-14-122/

[44] M. Keyland RF Werner“估计密度算子的频谱”物理评论 A 64, 052311 (2001)。
https：/ / doi.org/ 10.1103 / PhysRevA.64.052311
的arXiv：0102027

[45] Lucien Le Cam“泊松二项式分布的近似定理。” 太平洋数学杂志 10, 1181–1197 (1960)。

[46] Felix Leditzky、Nilanjana Datta 和 Graeme Smith，“有用状态和纠缠蒸馏”IEEE Transactions on Information Theory 64, 4689–4708 (2018)。
https：///doi.org/10.1109/TIT.2017.2776907
的arXiv：1701.03081

[47] Erich L Lehmannand Joseph P Romano“检验统计假设”Springer Science & Business Media (2006)。

[48] Reut Levi、Dana Ron 和 Ronitt Rubinfeld，“测试分布集合的属性”计算理论 9, 295–347 (2013)。
https：///doi.org/10.4086/toc.2013.v009a008
https://theoryofcomputing.org/articles/v009a008

[49] Netanel H. Lindner、Petra F. Scudo 和 Dagmar Bruß，“相关信息的量子估计”International Journal of Quantum Information 4, 131–149 (2006)。
https：/ / doi.org/ 10.1142 / S0219749906001657
的arXiv：0506223

[50] Ashley Montanaro 和 Ronald de Wolf “量子特性测试调查”计算理论 1, 1–81 (2016)。
https：///doi.org/10.4086/toc.gs.2016.007
的arXiv：1310.2035
http://www.theoryofcomputing.org/articles/gs007

[51] Ryan O'Donnelland John Wright “量子频谱测试”第四十七届 ACM 计算理论年度研讨会论文集，14 月 17-529 日，538-2015 (XNUMX)。
https：/ / doi.org/10.1145/ 2746539.2746582
的arXiv：1501.05028

[52] Ryan O'Donnelland John Wright “高效量子断层扫描”第四十八届 ACM 计算理论年度研讨会论文集，19 月 21-899 日，912-2016 (XNUMX)。
https：/ / doi.org/10.1145/ 2897518.2897544
的arXiv：1508.01907

[53] Ryan O'Donnelland John Wright “高效量子断层扫描 II”第 49 届年度 ACM SIGACT 计算理论研讨会论文集 962-974 (2017)。
https：/ / doi.org/10.1145/ 3055399.3055454
的arXiv：1612.00034

[54] Harold Ollivierand Wojciech H Zurek“量子不和谐：相关量子性的测量”物理评论快报 88, 017901 (2001)。
https：/ / doi.org/ 10.1103 / PhysRevLett.88.017901
的arXiv：0105072

[55] Liam Paninski“给定非常稀疏采样的离散数据的基于巧合的均匀性测试”IEEE Transactions on Information Theory 54, 4750–4755 (2008)。
https：///doi.org/10.1109/TIT.2008.928987
http:// / ieeeexplore.ieee.org/ document/ 4626074/

[56] Gael Sentís、John Calsamiglia 和 Ramon Munoz-Tapia，“量子变化点的精确识别”物理评论快报 119 (2017)。
https：/ / doi.org/ 10.1103 / PhysRevLett.119.140506
的arXiv：1707.07769

[57] Gael Sentís、Emilio Bagan、John Calsamiglia、Giulio Chiribella 和 Ramon Munoz-Tapia，“量子变化点”物理评论快报 117 (2016)。
https：/ / doi.org/ 10.1103 / PhysRevLett.117.150502
的arXiv：1605.01916

[58] Gael Sentís、Esteban Martínez-Vargas 和 Ramon Muñoz-Tapia，“精确识别量子变化点的在线策略”Physical Review A 98, 052305 (2018)。
https：/ / doi.org/ 10.1103 / PhysRevA.98.052305
的arXiv：1802.00280

[59] Graeme Smith、John A. Smolin 和 Andreas Winter，“对称侧通道的量子容量”IEEE Transactions on Information Theory 54, 4208–4217 (2008)。
https：///doi.org/10.1109/TIT.2008.928269
的arXiv：0607039

[60] Igal Sasonand Sergio Verdu “$f$ -发散不等式”IEEE Transactions on Information Theory 62, 5973–6006 (2016)。
https：///doi.org/10.1109/TIT.2016.2603151
的arXiv：1508.00335
https://ieeexplore.ieee.org/document/7552457/​

[61] Gregory Valiant 和 Paul Valiant“自动不等式证明器和实例最优身份测试”2014 年 IEEE 第 55 届计算机科学基础年度研讨会 51-60 (2014)。
https：///doi.org/10.1109/FOCS.2014.14
https://ieeexplore.ieee.org/document/6978989/​

[62] 王鑫“追求量子通信的基本极限”IEEE Transactions on Information Theory 67, 4524–4532 (2021)。
https：///doi.org/10.1109/TIT.2021.3068818
的arXiv：1912.00931
https://ieeexplore.ieee.org/document/9386074/​

[63] 于能坤“量子态的样本高效身份测试和独立性测试”第十二届理论计算机科学创新会议（ITCS 12）2021，185：11–1：11（20）。
https：///doi.org/10.4230/LIPIcs.ITCS.2021.11
的arXiv：1904.03218
https:/ / drops.dagstuhl.de/ opus/ volltexte/ 2021/ 13550

[64] Nengkun Yu“泡利测量对量子身份测试的几乎严格样本复杂性分析”IEEE Transactions on Information Theory 69, 5060–5068 (2023)。
https：///doi.org/10.1109/TIT.2023.3271206
的arXiv：2009.11518

被引用

[1] 李高和能坤于，“量子马尔可夫链的最优断层扫描样本”， 的arXiv：2209.02240, (2022).

[2] Marco Fanizza、Michalis Skotiniotis、John Calsamiglia、Ramon Muñoz-Tapia 和 Gael Sentís，“量子数据学习的通用算法”， EPL（欧洲物理学快报）140 2，28001（2022）.

以上引用来自 SAO / NASA广告 （最近成功更新为2023-09-13 12:15:38）。 该列表可能不完整，因为并非所有发布者都提供合适且完整的引用数据。

On Crossref的引用服务 找不到有关引用作品的数据（上一次尝试2023-09-13 12:15:37）。

该论文发表在《量子》杂志上 国际知识共享署名署名4.0（CC BY 4.0） 执照。 版权归原始版权持有者所有，例如作者或其所在机构。

时间戳记：

更多来自 量子杂志