Abstract
In classical computation, a “write-only memory” (WOM) is little more than an oxymoron, and the addition of a WOM to a (deterministic or probabilistic) classical computer brings no advantage. We demonstrate a setup where a quantum computer using a WOM can solve problems that neither a classical computer with a WOM nor a quantum computer without a WOM can solve, when all other resource bounds are equal. We also show that resource-bounded quantum reductions among computational problems are more powerful than their classical counterparts.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, New York (2009)
Ciamarra, M.P.: Quantum reversibility and a new model of quantum automaton. In: Freivalds, R. (ed.) FCT 2001. LNCS, vol. 2138, pp. 376–379. Springer, Heidelberg (2001)
Freivalds, R., Karpinski, M.: Lower space bounds for randomized computation. In: Shamir, E., Abiteboul, S. (eds.) ICALP 1994. LNCS, vol. 820, pp. 580–592. Springer, Heidelberg (1994)
Freivalds, R., Winter, A.J.: Quantum finite state transducers. In: Pacholski, L., Ružička, P. (eds.) SOFSEM 2001. LNCS, vol. 2234, pp. 233–242. Springer, Heidelberg (2001)
Jeandel, E.: Topological automata. Theory of Computing Systems 40(4), 397–407 (2007)
Kondacs, A., Watrous, J.: On the power of quantum finite state automata. In: FOCS 1997: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami, Florida, pp. 66–75 (1997)
Moore, C., Crutchfield, J.P.: Quantum automata and quantum grammars. Theoretical Computer Science 237(1-2), 275–306 (2000)
Paschen, K.: Quantum finite automata using ancilla qubits. Technical report, University of Karlsruhe (2000)
Pin, J.-E.: On the language accepted by finite reversible automata. In: Ottmann, T. (ed.) ICALP 1987. LNCS, vol. 267, pp. 237–249. Springer, Heidelberg (1987)
Rabin, M.O.: Probabilistic automata. Information and Control 6, 230–243 (1963)
Say, A.C.C., Yakaryilmaz, A.: Quantum function computation using sublogarithmic space (2010) (Poster presentation at QIP 2010)
Schöning, U., Pruim, R.: Gems of Theoretical Computer Science. Springer, Heidelberg (1998)
Watrous, J.: Space-bounded quantum computation. PhD thesis, University of Wisconsin - Madison, USA (1998)
Watrous, J.: On the complexity of simulating space-bounded quantum computations. Computational Complexity 12(1/2), 48–84 (2004)
Yao, A.C.-C.: Quantum circuit complexity. In: Proceedings of the 34th Annual Symposium on Foundations of Computer Science, pp. 352–361 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yakaryılmaz, A., Freivalds, R., Say, A.C.C., Agadzanyan, R. (2010). Quantum Computation with Devices Whose Contents Are Never Read. In: Calude, C.S., Hagiya, M., Morita, K., Rozenberg, G., Timmis, J. (eds) Unconventional Computation. UC 2010. Lecture Notes in Computer Science, vol 6079. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13523-1_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-13523-1_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13522-4
Online ISBN: 978-3-642-13523-1
eBook Packages: Computer ScienceComputer Science (R0)