License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2013.244
URN: urn:nbn:de:0030-drops-43249
Go to the corresponding LIPIcs Volume Portal

SaiToh, Akira

Realistic Cost for the Model of Coherent Computing

30.pdf (0.5 MB)


For the model of so-called coherent computing recently proposed by Yamamoto et al. [Y. Yamamoto et al., New Gen. Comput. 30 (2012) 327-355], a theoretical analysis of the success probability is given. Although it was claimed as their prospect that the Ising spin configuration problem would be efficiently solvable in the model, here it is shown that the probability of finding a desired spin configuration decreases exponentially in the number of spins for certain hard instances. The model is thus physically unfeasible for solving the problem within a polynomial cost.

BibTeX - Entry

  author =	{Akira SaiToh},
  title =	{{Realistic Cost for the Model of Coherent Computing}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{244--253},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Simone Severini and Fernando Brandao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-43249},
  doi =		{10.4230/LIPIcs.TQC.2013.244},
  annote =	{Keywords: Reliability, Laser-network computing, Computational complexity}

Keywords: Reliability, Laser-network computing, Computational complexity
Collection: 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)
Issue Date: 2013
Date of publication: 13.11.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI