Quantum computation with devices whose contents are never read

Details Quantum computation with devices whose contents are never read Quantum computation with devices whose contents are never read

2010-11-04

arxiv.org/abs/1011.1201v1

Computer Science

Computational Complexity

32 pages, a preliminary version of this work was presented in the 9th International Conference on Unconventional Computation (

Scientific paper

In classical computation, a "write-only memory" (WOM) is little more than an oxymoron, and the addition of WOM to a (deterministic or probabilistic) classical computer brings no advantage. We prove that quantum computers that are augmented with WOM can solve problems that neither a classical computer with WOM nor a quantum computer without WOM can solve, when all other resource bounds are equal. We focus on realtime quantum finite automata, and examine the increase in their power effected by the addition of WOMs with different access modes and capacities. Some problems that are unsolvable by two-way probabilistic Turing machines using sublogarithmic amounts of read/write memory are shown to be solvable by these enhanced automata.

Affiliated with

Also associated with

No associations

Rating

Quantum computation with devices whose contents are never read does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum computation with devices whose contents are never read, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum computation with devices whose contents are never read will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-146448