We present classical simulation techniques for measure once quantum branching programs. For bounded error syntactic quantum branching program of width $w$ that computes a function with error $delta$ we present a classical deterministic branching program of the same length and width at most $(1+2/(1-2delta))^{2w}$ that computes the same function. Second technique is a classical stochastic simulation technique for bounded error and unbounded error quantum branching programs. Our result is that it is possible stochastically-classically simulate quantum branching programs with the same length and almost the same width, but we lost bounded error acceptance property.We present classical simulation techniques for measure once quantum branching programs. For bounded error syntactic quantum branching program of width $w$ that computes a function with error $delta$ we present a classical deterministic branching program of the same length and width at most $(1+2/(1-2delta))^{2w}$ that computes the same function. Second technique is a classical stochastic simulation technique for bounded error and unbounded error quantum branching programs. Our result is that it is possible stochastically-classically simulate quantum branching programs with the same length and almost the same width, but we lost bounded error acceptance property.

Language and Automata Theory and ApplicationsJan 1, 20080 citations

Quantum stochastic models

Stanley Gudder

Foundations of PhysicsJun 1, 19921 citation

Quantum stochastic optimization

Bruno Apolloni, C. Carvalho, D. de Falco

Stochastic Processes and their ApplicationsDec 1, 1989211 citations

We present classical simulation techniques for measure once quantum branching programs. For bounded error syntactic quantum branching program of width

w

that computes a function with error

delta

we present a classical deterministic branching program of the same length and width at most

(1+2/(1-2delta))^{2w}

that computes the same function. Second technique is a classical stochastic simulation technique for bounded error and unbounded error quantum branching programs. Our result is that it is possible stochastically-classically simulate quantum branching programs with the same length and almost the same width, but we lost bounded error acceptance property.