基于量子算法的量子态层析新方案
|
摘要
在经典信息可有效制备为量子态和量子算法可物理实现的条件下,深入研究了量子算法如何有效改善基于线性回归估计的量子态层析算法的时间复杂度问题.在已有的量子算法基础上,形成了量子态层析的新方案.与现有的经典算法相比,本文所提方案需要引入量子态制备和额外的测量环节,但能显著降低量子态层析的时间复杂度.对于维数为d的待重构密度矩阵,当所用的量子算法涉及的矩阵的条件数κ和估计精度ε的倒数的复杂度均为O(poly log d),且所需同时制备的量子态数目规模是O(d)时,本方案可将量子态层析整体算法的时间复杂度从O(d~4)降为O(dpoly log d).
Recently, we try to answer the following question: what will happen to our life if quantum computers can be physically realized. In this research, we explore the impact of quantum algorithms on the time complexity of quantum state tomography based on the linear regression algorithm if quantum states can be efficiently prepared by classical information and quantum algorithms can be implemented on quantum computers. By studying current quantum algorithms based on quantum singular value decomposition(SVE) of calculating matrix multiplication, solving linear equations and eigenvalue and eigenstate estimation and so on, we propose a novel scheme to complete the mission of quantum state tomography. We show the calculation based on our algorithm as an example at last. Although quantum state preparations and extra measurements are indispensable in our quantum algorithm scheme compared with the existing classical algorithm, the time complexity of quantum state tomography can be remarkably declined. For a quantum system with dimension d,the entire quantum scheme can reduce the time complexity of quantum state tomography from O(d~4) to O(dpoly log d) when both the condition number κ of related matrices and the reciprocal of precision ε are O(poly log d), and quantum states of the same order O(d) can be simultaneously prepared. This is in contrast to the observation that quantum algorithms can reduce the time complexity of quantum state tomography to O(d~3) when quantum states can not be efficiently prepared. In other words, the preparing of quantum states efficiently has become a bottleneck constraining the quantum acceleration.
Recently, we try to answer the following question: what will happen to our life if quantum computers can be physically realized. In this research, we explore the impact of quantum algorithms on the time complexity of quantum state tomography based on the linear regression algorithm if quantum states can be efficiently prepared by classical information and quantum algorithms can be implemented on quantum computers. By studying current quantum algorithms based on quantum singular value decomposition(SVE) of calculating matrix multiplication, solving linear equations and eigenvalue and eigenstate estimation and so on, we propose a novel scheme to complete the mission of quantum state tomography. We show the calculation based on our algorithm as an example at last. Although quantum state preparations and extra measurements are indispensable in our quantum algorithm scheme compared with the existing classical algorithm, the time complexity of quantum state tomography can be remarkably declined. For a quantum system with dimension d,the entire quantum scheme can reduce the time complexity of quantum state tomography from O(d~4) to O(dpoly log d) when both the condition number κ of related matrices and the reciprocal of precision ε are O(poly log d), and quantum states of the same order O(d) can be simultaneously prepared. This is in contrast to the observation that quantum algorithms can reduce the time complexity of quantum state tomography to O(d~3) when quantum states can not be efficiently prepared. In other words, the preparing of quantum states efficiently has become a bottleneck constraining the quantum acceleration.
引文
[1]Teo Y S 2016 Introduction to quantum-state estimation(Singapore:World Scientific Press)ppl-5,23-31
[2]Haffner H,Hansel W,Roos C,et al 2005 Nature 438 643
[3]James D F V,Kwiat P G,Munro W J,et al.2001 Phys.Rezv.A 64 052312
[4]Qi B,Hou Z,Li L,et al.2013 Sci. Rep.3 3496
[5]Hou Z,Zhong H-S,Tian Y,et al.2016 New J.Phys.18083036
[6]Blume-Kohout R 2010 Phys.Rev.Lett.105 200504
[7]Teo Y S,Zhu H,Englert B G,et al.2011 Phys.Rev.Lett.107 020404
[8]Blume-Kohout R 2010 New J.Phys.12 043034
[9]Huszar F,Houlsby N M T 2012 Phys.Rev.A 85 052120
[10]Shor P W 1999 SIREV 41 303
[11]Abrams D S,Lloyd S 1999 Phys.Rev.Lett.83 5162
[12]Harrow A W,Hassidim A,Lloyd S 2009 Phys.Rev.Lett.103150502
[13]Wiebe N,Braun D,Lloyd S 2012 Phys.Rev.Lett.109 050505
[14]Lu S C,Zheng Y,Wang X T,Wu R B 2017 Contl. Theor.Appl.34 1429(in Chinese)[陆思聪,郑昱,王晓霆,吴热冰2017控制理论与应用34 1429]
[15]Smolin J A,Gambetta J M,Smith G 2012 Phys.Rev.Lett.108 070502
[16]Shao C 2018 arXiv preprint arXiv:1803 01601
[17]Wossnig L,Zhao Z K,Prakash A 2018 Phys.Rev.Lett.120050502
[18]H?yer P,Neerbek J,Shi Y 2002 Algorithmica 34 429
[19]Cheng S T,Wang C Y 2006 IEEE Trans.Circuits Syst.I:Reg.Papers 53 316
[20]Kerenidis I,Prakash A 2017 Proceedings of 8th Innovations in Theoretical Computer Science Conference Berkeley,CA,USA,January 9-11,2017 p1
[21]Nielsen M A,Chuang I L 2010 Quantum Computation and Quantum Information(10th Anniversary Edition)(Cambridge:Cambridge University Press)pp185-188
[2]Haffner H,Hansel W,Roos C,et al 2005 Nature 438 643
[3]James D F V,Kwiat P G,Munro W J,et al.2001 Phys.Rezv.A 64 052312
[4]Qi B,Hou Z,Li L,et al.2013 Sci. Rep.3 3496
[5]Hou Z,Zhong H-S,Tian Y,et al.2016 New J.Phys.18083036
[6]Blume-Kohout R 2010 Phys.Rev.Lett.105 200504
[7]Teo Y S,Zhu H,Englert B G,et al.2011 Phys.Rev.Lett.107 020404
[8]Blume-Kohout R 2010 New J.Phys.12 043034
[9]Huszar F,Houlsby N M T 2012 Phys.Rev.A 85 052120
[10]Shor P W 1999 SIREV 41 303
[11]Abrams D S,Lloyd S 1999 Phys.Rev.Lett.83 5162
[12]Harrow A W,Hassidim A,Lloyd S 2009 Phys.Rev.Lett.103150502
[13]Wiebe N,Braun D,Lloyd S 2012 Phys.Rev.Lett.109 050505
[14]Lu S C,Zheng Y,Wang X T,Wu R B 2017 Contl. Theor.Appl.34 1429(in Chinese)[陆思聪,郑昱,王晓霆,吴热冰2017控制理论与应用34 1429]
[15]Smolin J A,Gambetta J M,Smith G 2012 Phys.Rev.Lett.108 070502
[16]Shao C 2018 arXiv preprint arXiv:1803 01601
[17]Wossnig L,Zhao Z K,Prakash A 2018 Phys.Rev.Lett.120050502
[18]H?yer P,Neerbek J,Shi Y 2002 Algorithmica 34 429
[19]Cheng S T,Wang C Y 2006 IEEE Trans.Circuits Syst.I:Reg.Papers 53 316
[20]Kerenidis I,Prakash A 2017 Proceedings of 8th Innovations in Theoretical Computer Science Conference Berkeley,CA,USA,January 9-11,2017 p1
[21]Nielsen M A,Chuang I L 2010 Quantum Computation and Quantum Information(10th Anniversary Edition)(Cambridge:Cambridge University Press)pp185-188