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 $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.
BibTeX - Entry
@InProceedings{ablayev:DagSemProc.07411.3,
author = {Ablayev, Farid},
title = {{Classical Simulation Complexity of Quantum Branching Programs}},
booktitle = {Algebraic Methods in Computational Complexity},
pages = {1--10},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2008},
volume = {7411},
editor = {Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2008/1310},
URN = {urn:nbn:de:0030-drops-13107},
doi = {10.4230/DagSemProc.07411.3},
annote = {Keywords: Quantum algorithms, Branching Programs, Complexity}
}
|
Keywords: |
|
Quantum algorithms, Branching Programs, Complexity |
|
Collection: |
|
07411 - Algebraic Methods in Computational Complexity |
|
Issue Date: |
|
2008 |
|
Date of publication: |
|
23.01.2008 |
Creative Commons Attribution 4.0 International license (CC BY 4.0)