Sample-optimal tomography of quantum states
It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. This is the quantum analogue of the problem of estimating a probability distribution given some number of samples. Previously, it was known only that estimati...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery
2017
|
| Online Access: | http://hdl.handle.net/1721.1/110843 https://orcid.org/0000-0002-4420-4932 https://orcid.org/0000-0003-3220-7682 https://orcid.org/0000-0002-0094-9510 |
| _version_ | 1826201962036592640 |
|---|---|
| author | Ji, Zhengfeng Yu, Nengkun Haah, Jeongwan Wu, Xiaodi Harrow, Aram W. |
| author2 | Massachusetts Institute of Technology. Center for Theoretical Physics |
| author_facet | Massachusetts Institute of Technology. Center for Theoretical Physics Ji, Zhengfeng Yu, Nengkun Haah, Jeongwan Wu, Xiaodi Harrow, Aram W. |
| author_sort | Ji, Zhengfeng |
| collection | MIT |
| description | It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. This is the quantum analogue of the problem of estimating a probability distribution given some number of samples.
Previously, it was known only that estimating states to error є in trace distance required O(dr2/є2) copies for a d-dimensional density matrix of rank r. Here, we give a measurement scheme (POVM) that uses O( (dr/ δ ) ln(d/δ) ) copies to estimate ρ to error δ in infidelity. This implies O( (dr / є2)· ln(d/є) ) copies suffice to achieve error є in trace distance. For fixed d, our measurement can be implemented on a quantum computer in time polynomial in n. We also use the Holevo bound from quantum information theory to prove a lower bound of Ω(dr/є2)/ log(d/rє) copies needed to achieve error є in trace distance. This implies a lower bound Ω(dr/δ)/log(d/rδ) for the estimation error δ in infidelity. These match our upper bounds up to log factors. Our techniques can also show an Ω(r2d/δ) lower bound for measurement strategies in which each copy is measured individually and then the outcomes are classically post-processed to produce an estimate. This matches the known achievability results and proves for the first time that such “product” measurements have asymptotically suboptimal scaling with d and r. |
| first_indexed | 2024-09-23T11:59:44Z |
| format | Article |
| id | mit-1721.1/110843 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:59:44Z |
| publishDate | 2017 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | mit-1721.1/1108432023-02-26T04:06:54Z Sample-optimal tomography of quantum states Ji, Zhengfeng Yu, Nengkun Haah, Jeongwan Wu, Xiaodi Harrow, Aram W. Massachusetts Institute of Technology. Center for Theoretical Physics Massachusetts Institute of Technology. Department of Mathematics Massachusetts Institute of Technology. Department of Physics Massachusetts Institute of Technology. Laboratory for Nuclear Science Harrow, Aram W. Haah, Jeongwan Harrow, Aram W Wu, Xiaodi It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. This is the quantum analogue of the problem of estimating a probability distribution given some number of samples. Previously, it was known only that estimating states to error є in trace distance required O(dr2/є2) copies for a d-dimensional density matrix of rank r. Here, we give a measurement scheme (POVM) that uses O( (dr/ δ ) ln(d/δ) ) copies to estimate ρ to error δ in infidelity. This implies O( (dr / є2)· ln(d/є) ) copies suffice to achieve error є in trace distance. For fixed d, our measurement can be implemented on a quantum computer in time polynomial in n. We also use the Holevo bound from quantum information theory to prove a lower bound of Ω(dr/є2)/ log(d/rє) copies needed to achieve error є in trace distance. This implies a lower bound Ω(dr/δ)/log(d/rδ) for the estimation error δ in infidelity. These match our upper bounds up to log factors. Our techniques can also show an Ω(r2d/δ) lower bound for measurement strategies in which each copy is measured individually and then the outcomes are classically post-processed to produce an estimate. This matches the known achievability results and proves for the first time that such “product” measurements have asymptotically suboptimal scaling with d and r. Massachusetts Institute of Technology (MIT Pappalardo Fellowship in Physics) United States. Office of Naval Research (grant CCF-1111382) United States. Office of Naval Research (grant CCF-1111382) Natural Sciences and Engineering Research Council of Canada. Discovery Accelerator Supplements Program CRC Canadian Institute for Advanced Research United States. Army Research Office (contract W911NF-12-1-0486) National Science Foundation (U.S.) (Waterman Award) 2017-07-25T18:59:16Z 2017-07-25T18:59:16Z 2016-06 Article http://purl.org/eprint/type/ConferencePaper 9781450341325 http://hdl.handle.net/1721.1/110843 Haah, Jeongwan, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. “Sample-Optimal Tomography of Quantum States.” Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016 (2016). https://orcid.org/0000-0002-4420-4932 https://orcid.org/0000-0003-3220-7682 https://orcid.org/0000-0002-0094-9510 en_US https://doi.org/10.1145/2897518.2897585 Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery Harrow |
| spellingShingle | Ji, Zhengfeng Yu, Nengkun Haah, Jeongwan Wu, Xiaodi Harrow, Aram W. Sample-optimal tomography of quantum states |
| title | Sample-optimal tomography of quantum states |
| title_full | Sample-optimal tomography of quantum states |
| title_fullStr | Sample-optimal tomography of quantum states |
| title_full_unstemmed | Sample-optimal tomography of quantum states |
| title_short | Sample-optimal tomography of quantum states |
| title_sort | sample optimal tomography of quantum states |
| url | http://hdl.handle.net/1721.1/110843 https://orcid.org/0000-0002-4420-4932 https://orcid.org/0000-0003-3220-7682 https://orcid.org/0000-0002-0094-9510 |
| work_keys_str_mv | AT jizhengfeng sampleoptimaltomographyofquantumstates AT yunengkun sampleoptimaltomographyofquantumstates AT haahjeongwan sampleoptimaltomographyofquantumstates AT wuxiaodi sampleoptimaltomographyofquantumstates AT harrowaramw sampleoptimaltomographyofquantumstates |