Limit probabilities for random sparse bit strings.
Local transition functions of quantum Turing machines
Local Transition Functions of Quantum Turing Machines
Foundations of the notion of quantum Turing machines are investigated. According to Deutsch's formulation, the time evolution of a quantum Turing machine is to be determined by the local transition function. In this paper, the local transition functions are characterized for fully general quantum Turing machines, including multi-tape quantum Turing machines, extending the results due to Bernstein and Vazirani.
Lower bounds on the complexity of real-time branching programs