Thumbnail
Access Restriction
Open

Author Ablayev, Farid
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Quantum Branching Program ♦ Classical Simulation Complexity ♦ Error Acceptance Property ♦ Un-bounded Error Quantum ♦ Classical Stochastic Simulation Technique ♦ Simulate Quantum ♦ Second Technique ♦ Present Classical Simulation Technique ♦ Bounded Error Syntactic Quantum ♦ Bounded Error
Abstract 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 δ we present a classical deterministic branching program of the same length and width at most (1 + 2/(1 − 2δ))2w that computes the same function. Second technique is a classical stochastic simulation technique for bounded error and un-bounded 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. 1
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study