Konferans bildirisi Açık Erişim

Quantum Computation with Devices Whose Contents Are Never Read

2010    Yakaryilmaz, Abuzer; Freivalds, Rusins; Say, A. C. Cem; Agadzanyan, Ruben

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.