Tomoyuki Yamakami, Harumichi Nishimura

Quantum finite automata have been studied intensively since

their introduction in late 1990s as a natural model of a

quantum computer with finite-dimensional quantum memory space.

This paper seeks their direct application

to interactive proof systems in which a mighty quantum prover

communicates with a ...
more >>>

Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steve Homer

Abstract:We define and construct efficient depth-universal and almost-size-universal quantum circuits. Such circuits can be viewed as general-purpose simulators for central classes of quantum circuits and can be used to capture the computational power of the circuit class being simulated. For depth we construct universal circuits whose depth is the same ... more >>>

Uma Girish, Ran Raz, Wei Zhan

We give a quantum logspace algorithm for powering contraction matrices, that is, matrices with spectral norm at most 1. The algorithm gets as an input an arbitrary $n\times n$ contraction matrix $A$, and a parameter $T \leq poly(n)$ and outputs the entries of $A^T$, up to (arbitrary) polynomially small additive ... more >>>

Bill Fefferman, Zachary Remscrim

A foundational result in the theory of quantum computation known as the ``principle of safe storage'' shows that it is always possible to take a quantum circuit and produce an equivalent circuit that makes all measurements at the end of the computation. While this procedure is time efficient, meaning that ... more >>>