Loading...
Please wait, while we are loading the content...
Similar Documents
Hamiltonian simulation with nearly optimal dependence on spectral norm
| Content Provider | Semantic Scholar |
|---|---|
| Author | Hao, G. |
| Copyright Year | 2018 |
| Abstract | We present a quantum algorithm for approximating the real time evolution e−iHt of an arbitrary d-sparse Hamiltonian to error , given black-box access to the positions and b-bit values of its non-zero matrix entries. The complexity of our algorithm is O((t √ d‖H‖1 2)/ ) queries and a factor O(b) more gates, which is shown to be optimal up to subpolynomial factors through a matching query lower bound. This provides a polynomial speedup in sparsity for the common case where the spectral norm ‖H‖ ≥ ‖H‖1 2 is known, and generalizes previous approaches which achieve optimal scaling, but with respect to more restrictive parameters. By exploiting knowledge of the spectral norm, our algorithm solves the black-box unitary implementation problem – O(d) queries suffice to approximate any d-sparse unitary in the black-box setting, which matches the quantum search lower bound of Ω( √ d) queries and improves upon prior art [Berry and Childs, QIP 2010] of Õ(d) queries. Combined with known techniques, we also solve systems of sparse linear equations with condition number κ using O((κ √ d)/ ) queries, which is a quadratic improvement in sparsity. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://export.arxiv.org/pdf/1807.03967 |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Approximation algorithm Arabic numeral 0 Black box Condition number Dependence Hamiltonian (quantum mechanics) Image scaling Linear equation MATCHING Polynomial Quantum algorithm Question (inquiry) Simulation Sparse matrix Speedup Test scaling |
| Content Type | Text |
| Resource Type | Article |
