Drawing from hats by noise-based logic

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 ha...

Full description

Saved in:
Bibliographic Details
Published in:International journal of parallel, emergent and distributed systems emergent and distributed systems, 2017-05, Vol.32 (3), p.244-251
Main Authors: Zhang, Bruce, Kish, Laszlo Bela, Granqvist, Claes-Göran
Format: Article
Language:English
Subjects:
computational complexity
Noise
Noise-based logic
Numbers
random algorithms
superposition
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1744-5760
1744-5779
1744-5779
DOI:10.1080/17445760.2016.1140168