Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Ablayev, Farid License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-13107

Classical Simulation Complexity of Quantum Branching Programs

pdf gepackt: (329 KB)


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

  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 =		{},
  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
Seminar: 07411 - Algebraic Methods in Computational Complexity
Issue date: 2008
Date of publication: 23.01.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI