Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Applied and Industrial Mathematics

On simulating the quantum and classical branching programs

Aida Gainutdinova

Published Mar 1, 2007• 1 citation
Publisher

Abstract

The complexity classes defined on the basis of branching programs are considered. Some basic relations are established between the complexity classes defined by the probabilistic and quantum branching programs (measure-once, as well as measure-many), computing with bounded or unbounded error. To prove these relations, we developed a method of “linear simulation” of a quantum branching program and a method of “quantum simulation” of a probabilistic branching program.

DOI
10.1134/s1990478907010048

Related papers

On computational power of classical and quantum branching programs

Farid Mansurovich Ablayev

We present a classical stochastic simulation technique of quantum Branching programs. This technique allows to prove the following relations among complexity classes: PrQP-BP &subuline; PP-BP and BQP-BP &subuline; PP-BP. Here BPP-BP and PP-BP stands for the classes of functions computable with bounded error and unbounded error respectively by stochastic branching program of polynomial size. BQP-BP and PrQP-BP stands the classes of functions computable with bounded error and unbounded error respectively by quantum branching program of polynomial size. Second. We present two different types, of complexity lower bounds for quantum nonuniform automata (OBDDs). We call them "metric" and "entropic" lower bounds in according to proof technique used. We present explicit Boolean functions that show that these lower bounds are tight enough. We show that when considering "almost all Boolean functions" on n variables our entropic lower bounds gives exponential (2c(δ)(n-log n)) lower bound for the width of quantum OBDDs depending on the error δ allowed.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 24, 2006•2 citations

Classical Simulation Complexity of Quantum Branching Programs

Farid Mansurovich Ablayev

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 Applications•Jan 1, 2008•0 citations

Relationships between quantum and classical space-bounded complexity classes

John Watrous

This paper investigates the relative power of space-bounded quantum and classical (probabilistic) computational models. The following relationships are proved. 1. Any probabilistic Turing machine (PTM) which runs in space s and which halts absolutely (i.e. halts with certainty after a finite number of steps) can be simulated in space O(s) by a quantum Turing machine (QTM). If the PTM operates with bounded error, then the QTM may be taken to operate with bounded error as well, although the QTM may not halt absolutely in this case. In the unbounded error case, the QTM may be taken to halt absolutely. 2. Any QTM running in space s can be simulated by an unbounded error PTM running in space O(s). No assumptions on the probability of error or Turing time for the QTM are required, but it is assumed that all transition amplitudes of the quantum machine are rational. It follows that unbounded error, space O(s) bounded quantum Turing machines and probabilistic Turing machines are equivalent in power. This implies that any space s QTM can be simulated deterministically in space O(s/sup 2/), and further that any (unbounded-error) QTM running in log-space can be simulated in NC/sup 2/ We also consider quantum analogues of nondeterministic and one-sided error probabilistic space-bounded classes, and prove some simple relationships regarding these classes.

IEEE Conference on Computational Complexity (CCC)•Nov 27, 2002•13 citations

Computing quantum hashing in the model of quantum branching programs

Farid Mansurovich Ablayev, Marat Ablayev, Alexander Vasiliev

We investigate the branching program complexity of quantum hashing. We consider a quantum hash function that maps elements of a finite field into quantum states. We require that this function is preimage-resistant and collision-resistant.We consider two complexity measures for Quantum Branching Programs (QBP): a number of qubits and a number of compu-tational steps. We show that the quantum hash function can be computed efficiently. Moreover, we prove that such QBP construction is optimal. That is, we prove lower bounds that match the constructed quantum hash function computation.

AIP conference proceedings•Jan 1, 2018•3 citations

Quantum complexity theory

Ethan Bernstein, Umesh V. Vazirani

Abstract. In this paper we study quantum computation from a complexity theoretic viewpoint. Our rst result is the existence of an ecient universal quantum Turing machine in Deutsch’s model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97{117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specied. We prove that O(log T) bits of precision suce to support a T step computation. This justies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the rst formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church{Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class BPP. The class BQP of languages that are eciently decidable (with small error-probability) on a quantum Turing machine satises BPP ⊆ BQP ⊆ P]P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1993•1,413 citations

Quantum Complexity Theory

Ethan Bernstein, Umesh V. Vazirani

In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that $O(\log T)$ bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.

SIAM Journal on Computing•Oct 1, 1997•1,635 citations
The complexity classes defined on the basis of branching programs are considered. Some basic relations are established between the complexity classes defined by the probabilistic and quantum branching programs (measure-once, as well as measure-many), computing with bounded or unbounded error. To prove these relations, we developed a method of “linear simulation” of a quantum branching program and a method of “quantum simulation” of a probabilistic branching program.
We present a classical stochastic simulation technique of quantum Branching programs. This technique allows to prove the following relations among complexity classes: PrQP-BP &subuline; PP-BP and BQP-BP &subuline; PP-BP. Here BPP-BP and PP-BP stands for the classes of functions computable with bounded error and unbounded error respectively by stochastic branching program of polynomial size. BQP-BP and PrQP-BP stands the classes of functions computable with bounded error and unbounded error respectively by quantum branching program of polynomial size. Second. We present two different types, of complexity lower bounds for quantum nonuniform automata (OBDDs). We call them "metric" and "entropic" lower bounds in according to proof technique used. We present explicit Boolean functions that show that these lower bounds are tight enough. We show that when considering "almost all Boolean functions" on n variables our entropic lower bounds gives exponential (2c(δ)(n-log n)) lower bound for the width of quantum OBDDs depending on the error δ allowed.
We present classical simulation techniques for measure once quantum branching programs. For bounded error syntactic quantum branching program of width www that computes a function with error deltadeltadelta we present a classical deterministic branching program of the same length and width at most (1+2/(1−2delta))2w(1+2/(1-2delta))^{2w}(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.
This paper investigates the relative power of space-bounded quantum and classical (probabilistic) computational models. The following relationships are proved. 1. Any probabilistic Turing machine (PTM) which runs in space s and which halts absolutely (i.e. halts with certainty after a finite number of steps) can be simulated in space O(s) by a quantum Turing machine (QTM). If the PTM operates with bounded error, then the QTM may be taken to operate with bounded error as well, although the QTM may not halt absolutely in this case. In the unbounded error case, the QTM may be taken to halt absolutely. 2. Any QTM running in space s can be simulated by an unbounded error PTM running in space O(s). No assumptions on the probability of error or Turing time for the QTM are required, but it is assumed that all transition amplitudes of the quantum machine are rational. It follows that unbounded error, space O(s) bounded quantum Turing machines and probabilistic Turing machines are equivalent in power. This implies that any space s QTM can be simulated deterministically in space O(s/sup 2/), and further that any (unbounded-error) QTM running in log-space can be simulated in NC/sup 2/ We also consider quantum analogues of nondeterministic and one-sided error probabilistic space-bounded classes, and prove some simple relationships regarding these classes.
We investigate the branching program complexity of quantum hashing. We consider a quantum hash function that maps elements of a finite field into quantum states. We require that this function is preimage-resistant and collision-resistant.We consider two complexity measures for Quantum Branching Programs (QBP): a number of qubits and a number of compu-tational steps. We show that the quantum hash function can be computed efficiently. Moreover, we prove that such QBP construction is optimal. That is, we prove lower bounds that match the constructed quantum hash function computation.
Abstract. In this paper we study quantum computation from a complexity theoretic viewpoint. Our rst result is the existence of an ecient universal quantum Turing machine in Deutsch’s model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97{117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specied. We prove that O(log T) bits of precision suce to support a T step computation. This justies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the rst formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church{Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class BPP. The class BQP of languages that are eciently decidable (with small error-probability) on a quantum Turing machine satises BPP ⊆ BQP ⊆ P]P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that O(log⁡T)O(\log T)O(logT) bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.