Hamiltonian simulation with optimal sample complexity
© 2017 Author(s). We investigate the sample complexity of Hamiltonian simulation: how many copies of an unknown quantum state are required to simulate a Hamiltonian encoded by the density matrix of that state? We show that the procedure proposed by Lloyd, Mohseni, and Rebentrost [Nat. Phys., 10(9):6...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Science and Business Media LLC
2021
|
| Online Access: | https://hdl.handle.net/1721.1/135697 |
| _version_ | 1826193230393245696 |
|---|---|
| author | Kimmel, S Lin, CYY Low, GH Ozols, M Yoder, TJ |
| author2 | Massachusetts Institute of Technology. Department of Physics |
| author_facet | Massachusetts Institute of Technology. Department of Physics Kimmel, S Lin, CYY Low, GH Ozols, M Yoder, TJ |
| author_sort | Kimmel, S |
| collection | MIT |
| description | © 2017 Author(s). We investigate the sample complexity of Hamiltonian simulation: how many copies of an unknown quantum state are required to simulate a Hamiltonian encoded by the density matrix of that state? We show that the procedure proposed by Lloyd, Mohseni, and Rebentrost [Nat. Phys., 10(9):631-633, 2014] is optimal for this task. We further extend their method to the case of multiple input states, showing how to simulate any Hermitian polynomial of the states provided. As applications, we derive optimal algorithms for commutator simulation and orthogonality testing, and we give a protocol for creating a coherent superposition of pure states, when given sample access to those states. We also show that this sample-based Hamiltonian simulation can be used as the basis of a universal model of quantum computation that requires only partial swap operations and simple single-qubit states. |
| first_indexed | 2024-09-23T09:35:44Z |
| format | Article |
| id | mit-1721.1/135697 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:35:44Z |
| publishDate | 2021 |
| publisher | Springer Science and Business Media LLC |
| record_format | dspace |
| spelling | mit-1721.1/1356972023-03-01T21:27:04Z Hamiltonian simulation with optimal sample complexity Kimmel, S Lin, CYY Low, GH Ozols, M Yoder, TJ Massachusetts Institute of Technology. Department of Physics © 2017 Author(s). We investigate the sample complexity of Hamiltonian simulation: how many copies of an unknown quantum state are required to simulate a Hamiltonian encoded by the density matrix of that state? We show that the procedure proposed by Lloyd, Mohseni, and Rebentrost [Nat. Phys., 10(9):631-633, 2014] is optimal for this task. We further extend their method to the case of multiple input states, showing how to simulate any Hermitian polynomial of the states provided. As applications, we derive optimal algorithms for commutator simulation and orthogonality testing, and we give a protocol for creating a coherent superposition of pure states, when given sample access to those states. We also show that this sample-based Hamiltonian simulation can be used as the basis of a universal model of quantum computation that requires only partial swap operations and simple single-qubit states. 2021-10-27T20:28:51Z 2021-10-27T20:28:51Z 2017-12-01 2019-04-24T14:41:05Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/135697 Kimmel, Shelby, et al. "Hamiltonian Simulation with Optimal Sample Complexity." Npj Quantum Information 3 (2017). en 10.1038/s41534-017-0013-7 npj Quantum Information Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf Springer Science and Business Media LLC Nature |
| spellingShingle | Kimmel, S Lin, CYY Low, GH Ozols, M Yoder, TJ Hamiltonian simulation with optimal sample complexity |
| title | Hamiltonian simulation with optimal sample complexity |
| title_full | Hamiltonian simulation with optimal sample complexity |
| title_fullStr | Hamiltonian simulation with optimal sample complexity |
| title_full_unstemmed | Hamiltonian simulation with optimal sample complexity |
| title_short | Hamiltonian simulation with optimal sample complexity |
| title_sort | hamiltonian simulation with optimal sample complexity |
| url | https://hdl.handle.net/1721.1/135697 |
| work_keys_str_mv | AT kimmels hamiltoniansimulationwithoptimalsamplecomplexity AT lincyy hamiltoniansimulationwithoptimalsamplecomplexity AT lowgh hamiltoniansimulationwithoptimalsamplecomplexity AT ozolsm hamiltoniansimulationwithoptimalsamplecomplexity AT yodertj hamiltoniansimulationwithoptimalsamplecomplexity |