License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-13107
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1310/
Ablayev, Farid

Classical Simulation Complexity of Quantum Branching Programs

pdf-format:
Dokument 1.pdf (172 KB) Dokument 2.pdf (212 KB)
pdf gepackt:
Dokument1.zip (329 KB)

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:DSP:2008:1310,
  author =	{Farid Ablayev},
  title =	{Classical Simulation Complexity of  Quantum  Branching Programs},
  booktitle =	{Algebraic Methods in Computational Complexity},
  year =	{2008},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  number =	{07411},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1310},
  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 Published by LZI