Closed timelike curves make quantum and classical computing equivalent
While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to non-trivial insights into general relativity, quantum information and other areas. In this paper, we show that, if CTCs existed, quantum computers would be no more powerful than classical computers: bo...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Royal Society of London
2010
|
| Online Access: | http://hdl.handle.net/1721.1/52302 https://orcid.org/0000-0003-1333-4045 |
| _version_ | 1826191767690543104 |
|---|---|
| author | Aaronson, Scott Watrous, John |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Aaronson, Scott Watrous, John |
| author_sort | Aaronson, Scott |
| collection | MIT |
| description | While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to non-trivial insights into general relativity, quantum information and other areas. In this paper, we show that, if CTCs existed, quantum computers would be no more powerful than classical computers: both would have the (extremely large) power of the complexity class polynomial space (Graphic), consisting of all problems solvable by a conventional computer using a polynomial amount of memory. This solves an open problem proposed by one of us in 2005, and gives an essentially complete understanding of computational complexity in the presence of CTCs. Following the work of Deutsch, we treat a CTC as simply a region of spacetime where a ‘causal consistency’ condition is imposed, meaning that nature has to produce a (probabilistic or quantum) fixed point of some evolution operator. Our conclusion is then a consequence of the following theorem: given any quantum circuit (not necessarily unitary), a fixed point of the circuit can be (implicitly) computed in Graphic. This theorem might have independent applications in quantum information. |
| first_indexed | 2024-09-23T09:00:59Z |
| format | Article |
| id | mit-1721.1/52302 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:00:59Z |
| publishDate | 2010 |
| publisher | Royal Society of London |
| record_format | dspace |
| spelling | mit-1721.1/523022022-09-30T12:50:23Z Closed timelike curves make quantum and classical computing equivalent Aaronson, Scott Watrous, John Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Aaronson, Scott Aaronson, Scott While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to non-trivial insights into general relativity, quantum information and other areas. In this paper, we show that, if CTCs existed, quantum computers would be no more powerful than classical computers: both would have the (extremely large) power of the complexity class polynomial space (Graphic), consisting of all problems solvable by a conventional computer using a polynomial amount of memory. This solves an open problem proposed by one of us in 2005, and gives an essentially complete understanding of computational complexity in the presence of CTCs. Following the work of Deutsch, we treat a CTC as simply a region of spacetime where a ‘causal consistency’ condition is imposed, meaning that nature has to produce a (probabilistic or quantum) fixed point of some evolution operator. Our conclusion is then a consequence of the following theorem: given any quantum circuit (not necessarily unitary), a fixed point of the circuit can be (implicitly) computed in Graphic. This theorem might have independent applications in quantum information. 2010-03-04T18:53:22Z 2010-03-04T18:53:22Z 2009-02 2008-08 Article http://purl.org/eprint/type/SubmittedJournalArticle 1471-2946 0950-1207 http://hdl.handle.net/1721.1/52302 Aaronson, Scott, and John Watrous. “Closed timelike curves make quantum and classical computing equivalent.” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science 465.2102 (2009): 631-647. https://orcid.org/0000-0003-1333-4045 en_US http://dx.doi.org/10.1098/rspa.2008.0350 Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Royal Society of London arXiv |
| spellingShingle | Aaronson, Scott Watrous, John Closed timelike curves make quantum and classical computing equivalent |
| title | Closed timelike curves make quantum and classical computing equivalent |
| title_full | Closed timelike curves make quantum and classical computing equivalent |
| title_fullStr | Closed timelike curves make quantum and classical computing equivalent |
| title_full_unstemmed | Closed timelike curves make quantum and classical computing equivalent |
| title_short | Closed timelike curves make quantum and classical computing equivalent |
| title_sort | closed timelike curves make quantum and classical computing equivalent |
| url | http://hdl.handle.net/1721.1/52302 https://orcid.org/0000-0003-1333-4045 |
| work_keys_str_mv | AT aaronsonscott closedtimelikecurvesmakequantumandclassicalcomputingequivalent AT watrousjohn closedtimelikecurvesmakequantumandclassicalcomputingequivalent |