Efficient distributed quantum computing
We provide algorithms for efficiently moving and addressing quantum memory in parallel. These imply that the standard circuit model can be simulated with a low overhead by a more realistic model of a distributed quantum computer. As a result, the circuit model can be used by algorithm designers with...
| Main Authors: | , , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Royal Society, The
2014
|
| Online Access: | http://hdl.handle.net/1721.1/88440 https://orcid.org/0000-0003-3220-7682 |
| _version_ | 1826203411045941248 |
|---|---|
| author | Beals, Robert Brierley, Stephen Gray, Oliver Harrow, Aram W. Kutin, Samuel Linden, Noah Shepherd, Dan Stather, Mark |
| author2 | Massachusetts Institute of Technology. Center for Theoretical Physics |
| author_facet | Massachusetts Institute of Technology. Center for Theoretical Physics Beals, Robert Brierley, Stephen Gray, Oliver Harrow, Aram W. Kutin, Samuel Linden, Noah Shepherd, Dan Stather, Mark |
| author_sort | Beals, Robert |
| collection | MIT |
| description | We provide algorithms for efficiently moving and addressing quantum memory in parallel. These imply that the standard circuit model can be simulated with a low overhead by a more realistic model of a distributed quantum computer. As a result, the circuit model can be used by algorithm designers without worrying whether the underlying architecture supports the connectivity of the circuit. In addition, we apply our results to existing memory-intensive quantum algorithms. We present a parallel quantum search algorithm and improve the time–space trade-off for the element distinctness and collision finding problems. |
| first_indexed | 2024-09-23T12:36:33Z |
| format | Article |
| id | mit-1721.1/88440 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:36:33Z |
| publishDate | 2014 |
| publisher | Royal Society, The |
| record_format | dspace |
| spelling | mit-1721.1/884402022-10-01T10:02:11Z Efficient distributed quantum computing Beals, Robert Brierley, Stephen Gray, Oliver Harrow, Aram W. Kutin, Samuel Linden, Noah Shepherd, Dan Stather, Mark Massachusetts Institute of Technology. Center for Theoretical Physics Harrow, Aram W. We provide algorithms for efficiently moving and addressing quantum memory in parallel. These imply that the standard circuit model can be simulated with a low overhead by a more realistic model of a distributed quantum computer. As a result, the circuit model can be used by algorithm designers without worrying whether the underlying architecture supports the connectivity of the circuit. In addition, we apply our results to existing memory-intensive quantum algorithms. We present a parallel quantum search algorithm and improve the time–space trade-off for the element distinctness and collision finding problems. National Science Foundation (U.S.) (Grant 0916400) National Science Foundation (U.S.) (Grant 0829937) National Science Foundation (U.S.) (Grant 0803478) United States. Defense Advanced Research Projects Agency (DARPA QuEST contract FA9550-09-1-0044) United States. Intelligence Advanced Research Projects Activity (DoI NBC contract no. D11PC20167) 2014-07-18T14:47:15Z 2014-07-18T14:47:15Z 2013-02 Article http://purl.org/eprint/type/JournalArticle 1364-5021 1471-2946 http://hdl.handle.net/1721.1/88440 Beals, R., S. Brierley, O. Gray, A. W. Harrow, S. Kutin, N. Linden, D. Shepherd, and M. Stather. “Efficient Distributed Quantum Computing.” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 469, no. 2153 (February 20, 2013): 20120686–20120686. https://orcid.org/0000-0003-3220-7682 en_US http://dx.doi.org/10.1098/rspa.2012.0686 Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Royal Society, The arXiv |
| spellingShingle | Beals, Robert Brierley, Stephen Gray, Oliver Harrow, Aram W. Kutin, Samuel Linden, Noah Shepherd, Dan Stather, Mark Efficient distributed quantum computing |
| title | Efficient distributed quantum computing |
| title_full | Efficient distributed quantum computing |
| title_fullStr | Efficient distributed quantum computing |
| title_full_unstemmed | Efficient distributed quantum computing |
| title_short | Efficient distributed quantum computing |
| title_sort | efficient distributed quantum computing |
| url | http://hdl.handle.net/1721.1/88440 https://orcid.org/0000-0003-3220-7682 |
| work_keys_str_mv | AT bealsrobert efficientdistributedquantumcomputing AT brierleystephen efficientdistributedquantumcomputing AT grayoliver efficientdistributedquantumcomputing AT harrowaramw efficientdistributedquantumcomputing AT kutinsamuel efficientdistributedquantumcomputing AT lindennoah efficientdistributedquantumcomputing AT shepherddan efficientdistributedquantumcomputing AT stathermark efficientdistributedquantumcomputing |