Optimal Hamiltonian Simulation by Quantum Signal Processing

被引:441
作者
Low, Guang Hao [1 ]
Chuang, Isaac L.
机构
[1] MIT, Dept Phys, Ctr Ultracold Atoms, Cambridge, MA 02139 USA
基金
美国国家科学基金会;
关键词
D O I
10.1103/PhysRevLett.118.010501
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
The physics of quantum mechanics is the inspiration for, and underlies, quantum computation. As such, one expects physical intuition to be highly influential in the understanding and design of many quantum algorithms, particularly simulation of physical systems. Surprisingly, this has been challenging, with current Hamiltonian simulation algorithms remaining abstract and often the result of sophisticated but unintuitive constructions. We contend that physical intuition can lead to optimal simulation methods by showing that a focus on simple single-qubit rotations elegantly furnishes an optimal algorithm for Hamiltonian simulation, a universal problem that encapsulates all the power of quantum computation. Specifically, we show that the query complexity of implementing time evolution by a d-sparse Hamiltonian H for time-interval t with error epsilon is O[td parallel to(H) over cap parallel to(max) + log (1/epsilon) / log (1/epsilon)], which matches lower bounds in all parameters. This connection is made through general three-step "quantum signal processing" methodology, comprised of (i) transducing eigenvalues of (H) over cap into a single ancilla qubit, (ii) transforming these eigenvalues through an optimal-length sequence of single-qubit rotations, and (iii) projecting this ancilla with near unity success probability.
引用
收藏
页数:5
相关论文
共 34 条
[1]  
Abramowitz M., 2013, Handbook of Mathematical Functions With Formulas, Graphs and Mathematical Tables, V(eds)
[2]  
AHARONOV A., 2003, P 35 ANN ACM S THEOR, P20, DOI DOI 10.1145/780542.780546
[3]  
[Anonymous], 2013, APPROXIMATION THEORY
[4]  
[Anonymous], P 41 ANN ACM S THEOR
[5]  
Berry D. W., 2015, FDN COMP SCI FOCS 20, P792
[6]   Efficient quantum algorithms for simulating sparse Hamiltonians [J].
Berry, Dominic W. ;
Ahokas, Graeme ;
Cleve, Richard ;
Sanders, Barry C. .
COMMUNICATIONS IN MATHEMATICAL PHYSICS, 2007, 270 (02) :359-371
[7]   Exponential improvement in precision for simulating sparse Hamiltonians [J].
Berry, Dominic W. ;
Childs, Andrew M. ;
Cleve, Richard ;
Kothari, Robin ;
Somma, Rolando D. .
STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2014, :283-292
[8]   Simulating Hamiltonian Dynamics with a Truncated Taylor Series [J].
Berry, Dominic W. ;
Childs, Andrew M. ;
Cleve, Richard ;
Kothari, Robin ;
Somma, Rolando D. .
PHYSICAL REVIEW LETTERS, 2015, 114 (09)
[9]  
Berry DW, 2012, QUANTUM INF COMPUT, V12, P29
[10]   Optimal Control at the Quantum Speed Limit [J].
Caneva, T. ;
Murphy, M. ;
Calarco, T. ;
Fazio, R. ;
Montangero, S. ;
Giovannetti, V. ;
Santoro, G. E. .
PHYSICAL REVIEW LETTERS, 2009, 103 (24)