uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Drawing from hats by noise-based logic
Texas A&M Univ, Dept Elect Engn, College Stn, TX 77843 USA..
Texas A&M Univ, Dept Elect Engn, College Stn, TX 77843 USA..
Uppsala University, Disciplinary Domain of Science and Technology, Technology, Department of Engineering Sciences, Solid State Physics.
2017 (English)In: International Journal of Parallel, Emergent and Distributed Systems, ISSN 1744-5760, E-ISSN 1744-5779, Vol. 32, no 3, 244-251 p.Article in journal (Refereed) Published
Abstract [en]

We utilize the asymmetric random telegraph wave-based instantaneous noise-base logic scheme to represent the problem of drawing numbers from a hat, and we consider two identical hats with the first 2(N) integer numbers. In the first problem, Alice secretly draws an arbitrary number from one of the hats, and Bob must find out which hat is missing a number. In the second problem, Alice removes a known number from one of the hats and another known number from the other hat, and Bob must identify these hats. We show that, when the preparation of the hats with the numbers is accounted for, the noise-based logic scheme always provides an exponential speed-up and/ or it requires exponentially smaller computational complexity than deterministic alternatives. Both the stochasticity and the ability to superpose numbers are essential components of the exponential improvement.

Place, publisher, year, edition, pages
2017. Vol. 32, no 3, 244-251 p.
Keyword [en]
Noise-based logic, random algorithms, superposition, computational complexity
National Category
Computer Sciences Engineering and Technology
Identifiers
URN: urn:nbn:se:uu:diva-331959DOI: 10.1080/17445760.2016.1140168ISI: 000406068600002OAI: oai:DiVA.org:uu-331959DiVA: diva2:1151039
Available from: 2017-10-20 Created: 2017-10-20 Last updated: 2017-11-01Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Granqvist, Claes Göran

Search in DiVA

By author/editor
Granqvist, Claes Göran
By organisation
Solid State Physics
In the same journal
International Journal of Parallel, Emergent and Distributed Systems
Computer SciencesEngineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 30 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf