Stephen A. Fenner, Frederic Green, Steven Homer, Randall Pruim

It is shown that determining whether a quantum computation

has a non-zero probability of accepting is at least as hard as the

polynomial time hierarchy. This hardness result also applies to

determining in general whether a given quantum basis state appears

with nonzero amplitude in a superposition, or whether a ...
more >>>

Chris Pollett, Farid Ablayev, Cristopher Moore, Chris Pollett

We prove upper and lower bounds on the power of quantum and stochastic

branching programs of bounded width. We show any NC^1 language can

be accepted exactly by a width-2 quantum branching program of

polynomial length, in contrast to the classical case where width 5 is

necessary unless \NC^1=\ACC. ...
more >>>

Andris Ambainis, William Gasarch, Aravind Srinivasan, Andrey Utis

Alice and Bob want to know if two strings of length $n$ are

almost equal. That is, do they differ on at most $a$ bits?

Let $0\le a\le n-1$.

We show that any deterministic protocol, as well as any

error-free quantum protocol ($C^*$ version), for this problem

requires at ...
more >>>

Farid Ablayev, Airat Khasianov, Alexander Vasiliev

We consider Generalized Equality, the Hidden Subgroup,

and related problems in the context of quantum Ordered Binary

Decision Diagrams. For the decision versions of considered problems

we show polynomial upper bounds in terms of quantum OBDD width. We

apply a new modification of the fingerprinting technique and present

the algorithms ...
more >>>

Airat Khasianov

We consider the \emph{Hidden Subgroup} in the context of quantum \emph{Ordered Binary Decision Diagrams}.

We show several lower bounds for this function.

In this paper we also consider a slightly more general definition of the

hidden subgroup problem (in contrast to that in \cite{khashsp1}). It turns out that ...
more >>>

Shalev Ben-David

We construct a total Boolean function $f$ satisfying

$R(f)=\tilde{\Omega}(Q(f)^{5/2})$, refuting the long-standing

conjecture that $R(f)=O(Q(f)^2)$ for all total Boolean functions.

Assuming a conjecture of Aaronson and Ambainis about optimal quantum speedups for partial functions,

we improve this to $R(f)=\tilde{\Omega}(Q(f)^3)$.

Our construction is motivated by the Göös-Pitassi-Watson function

but does not ...
more >>>