Solving search problems by strongly simulating quantum circuits
Simulating quantum circuits using classical computers lets us analyse the inner workings of quantum algorithms. The most complete type of simulation, strong simulation, is believed to be generally inefficient. Nevertheless, several efficient strong simulation techniques are known for restricted fami...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Springer Nature
2013
|
| _version_ | 1797073933737918464 |
|---|---|
| author | Johnson, T Biamonte, J Clark, SR Jaksch, D |
| author_facet | Johnson, T Biamonte, J Clark, SR Jaksch, D |
| author_sort | Johnson, T |
| collection | OXFORD |
| description | Simulating quantum circuits using classical computers lets us analyse the inner workings of quantum algorithms. The most complete type of simulation, strong simulation, is believed to be generally inefficient. Nevertheless, several efficient strong simulation techniques are known for restricted families of quantum circuits and we develop an additional technique in this article. Further, we show that strong simulation algorithms perform another fundamental task: solving search problems. Efficient strong simulation techniques allow solutions to a class of search problems to be counted and found efficiently. This enhances the utility of strong simulation methods, known or yet to be discovered and extends the class of search problems known to be efficiently simulable. Relating strong simulation to search problems also bounds the computational power of efficiently strongly simulable circuits; if they could solve all problems in P this would imply that all problems in NP and #P could be solved in polynomial time. |
| first_indexed | 2024-03-06T23:29:01Z |
| format | Journal article |
| id | oxford-uuid:6b62a702-0b94-4e9c-8228-cea711ec1577 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T23:29:01Z |
| publishDate | 2013 |
| publisher | Springer Nature |
| record_format | dspace |
| spelling | oxford-uuid:6b62a702-0b94-4e9c-8228-cea711ec15772022-03-26T19:03:36ZSolving search problems by strongly simulating quantum circuitsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:6b62a702-0b94-4e9c-8228-cea711ec1577EnglishSymplectic Elements at OxfordSpringer Nature2013Johnson, TBiamonte, JClark, SRJaksch, DSimulating quantum circuits using classical computers lets us analyse the inner workings of quantum algorithms. The most complete type of simulation, strong simulation, is believed to be generally inefficient. Nevertheless, several efficient strong simulation techniques are known for restricted families of quantum circuits and we develop an additional technique in this article. Further, we show that strong simulation algorithms perform another fundamental task: solving search problems. Efficient strong simulation techniques allow solutions to a class of search problems to be counted and found efficiently. This enhances the utility of strong simulation methods, known or yet to be discovered and extends the class of search problems known to be efficiently simulable. Relating strong simulation to search problems also bounds the computational power of efficiently strongly simulable circuits; if they could solve all problems in P this would imply that all problems in NP and #P could be solved in polynomial time. |
| spellingShingle | Johnson, T Biamonte, J Clark, SR Jaksch, D Solving search problems by strongly simulating quantum circuits |
| title | Solving search problems by strongly simulating quantum circuits |
| title_full | Solving search problems by strongly simulating quantum circuits |
| title_fullStr | Solving search problems by strongly simulating quantum circuits |
| title_full_unstemmed | Solving search problems by strongly simulating quantum circuits |
| title_short | Solving search problems by strongly simulating quantum circuits |
| title_sort | solving search problems by strongly simulating quantum circuits |
| work_keys_str_mv | AT johnsont solvingsearchproblemsbystronglysimulatingquantumcircuits AT biamontej solvingsearchproblemsbystronglysimulatingquantumcircuits AT clarksr solvingsearchproblemsbystronglysimulatingquantumcircuits AT jakschd solvingsearchproblemsbystronglysimulatingquantumcircuits |