Research

Solving search problems by strongly simulating quantum circuits


Reference:

Johnson, T. H., Biamonte, J. D., Clark, S. R. and Jaksch, D., 2013. Solving search problems by strongly simulating quantum circuits. Scientific Reports, 3, 1235.

Related documents:

[img] Other (Solving search problems by strongly simulating quantum circuits)
Download (2206kB)
    [img]
    Preview
    PDF (Published Version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
    Download (595kB) | Preview

      Official URL:

      http://dx.doi.org/10.1038/srep01235

      Abstract

      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 $\mathrm{P}$ this would imply the collapse of the complexity hierarchy $\mathrm{P} \subseteq \mathrm{NP} \subseteq # \mathrm{P}$.

      Details

      Item Type Articles
      CreatorsJohnson, T. H., Biamonte, J. D., Clark, S. R. and Jaksch, D.
      DOI10.1038/srep01235
      Uncontrolled Keywordsquant-ph
      DepartmentsFaculty of Science > Physics
      RefereedYes
      StatusPublished
      ID Code47352
      Additional Information9 pages, 3 figures

      Export

      Actions (login required)

      View Item

      Document Downloads

      More statistics for this item...