We present a polynomial quantum algorithm for the Abelian stabilizer problem
which includes both factoring and the discrete logarithm. Thus we extend famous
Shor's results. Our method is based on a procedure for measuring an eigenvalue
of a unitary operator. Another application of this
procedure is a polynomial ... more >>>

Adleman, DeMarrais, and Huang introduced the
nondeterministic quantum polynomial-time complexity class NQP as an
analogue of NP. It is known that, with restricted amplitudes, NQP is
characterized in terms of the classical counting complexity class
C_{=}P. In this paper we prove that, with unrestricted amplitudes,
NQP indeed coincides with the ... more >>>

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 >>>

We propose definitions of $\QAC^0$, the quantum analog of the
classical class $\AC^0$ of constant-depth circuits with AND and OR
gates of arbitrary fan-in, and $\QACC^0[q]$, the analog of the class
$\ACC^0[q]$ where $\Mod_q$ gates are also allowed. We show that it is
possible to make a `cat' state on ... more >>>

We establish a lower bound of $\Omega{(\sqrt{n})}$ on the bounded-error quantum query complexity of read-once Boolean functions, providing evidence for the conjecture that $\Omega(\sqrt{D(f)})$ is a lower bound for all Boolean functions.Our technique extends a result of Ambainis, based on the idea that successful computation of a function requires ``decoherence'' ... more >>>

Advice is supplementary information that enhances the computational
power of an underlying computation. This paper focuses on advice that
is given in the form of a pure quantum state. The notion of advised
quantum computation has a direct connection to non-uniform quantum
circuits and tally languages. The paper examines the ... more >>>

We initiate the study of quantifying the quantumness of
a quantum circuit by the number of gates that do not preserve
the computational basis, as a means to understand the nature
of quantum algorithmic speedups.
Intuitively, a reduction in the quantumness requires
an increase in the amount of classical computation, ... more >>>

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HM_n: Alice gets as input a string x in {0,1}^n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple (i,j,b) ... more >>>

This paper introduces a framework for quantum exact learning via queries, the so-called quantum protocol. It is shown that usual protocols in the classical learning setting have quantum counterparts. A combinatorial notion, the general halving dimension, is also introduced. Given a quantum protocol and a target concept class, the general ... more >>>

We develop quantum fingerprinting technique for constructing quantum
branching programs (QBPs), which are considered as circuits with an
ability to use classical bits as control variables.

We demonstrate our approach constructing optimal quantum ordered
binary decision diagram (QOBDD) for $MOD_m$ and $DMULT_n$ Boolean
functions. The construction of our technique also ... more >>>

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 >>>

We construct public-key cryptosystems that are secure assuming the
\emph{worst-case} hardness of approximating the length of a shortest
nonzero vector in an $n$-dimensional lattice to within a small
$\poly(n)$ factor. Prior cryptosystems with worst-case connections
were based either on the shortest vector problem for a \emph{special
class} of lattices ... more >>>

We prove the following surprising result: given any quantum state rho on n qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of two-qubit interactions), such that any ground state of H can be used to simulate rho on all quantum circuits of fixed polynomial size. ... more >>>

We study the power of classical and quantum algorithms equipped with nonuniform advice, in the form of a coin whose bias encodes useful information. This question takes on particular importance in the quantum case, due to a surprising result that we prove: a quantum finite automaton with just two states ... more >>>

Communication complexity of XOR functions $f (x \oplus y)$ has attracted increasing attention in recent years, because of its connections to Fourier analysis, and its exhibition of exponential separations between classical and quantum communication complexities of total functions.However, the complexity of certain basic functions still seems elusive especially in the ... more >>>

Weighted counting problems are a natural generalization of counting problems where a weight is associated with every computational path and the goal is to compute the sum of the weights of all paths (instead of computing the number of accepting paths). We present a structured view on weighted counting by ... more >>>

Although polynomial-time probabilistic Turing machines can utilize uncomputable transition probabilities to recognize uncountably many languages with bounded error when allowed to use logarithmic space, it is known that such ``magic coins'' give no additional computational power to constant-space versions of those machines. We show that adding a few quantum bits ... more >>>

We present two results in structural complexity theory concerned with the following interrelated
topics: computation with postselection/restarting, closed timelike curves (CTCs), and
approximate counting. The first result is a new characterization of the lesser known complexity
class BPP_path in terms of more familiar concepts. Precisely, BPP_path is the class of ... more >>>

In 2011, Aaronson gave a striking proof, based on quantum linear optics, showing that the problem of computing the permanent of a matrix is #P-hard. Aaronson's proof led naturally to hardness of approximation results for the permanent, and it was arguably simpler than Valiant's seminal proof of the same fact ... more >>>

In this paper we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of PAC learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results.

1) Hardness of learning ... more >>>

We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property $\Pi$ and reject ... more >>>

Relational problems (those with many possible valid outputs) are different from decision problems, but it is easy to forget just how different. This paper initiates the study of FBQP/qpoly, the class of relational problems solvable in quantum polynomial-time with the help of polynomial-sized quantum advice, along with its analogues for ... more >>>

In this note, we observe that quantum logspace computations are verifiable by classical logspace algorithms, with unconditional security. More precisely, every language in BQL has an information-theoretically secure) streaming proof with a quantum logspace prover and a classical logspace verifier. The prover provides a polynomial-length proof that is streamed to ... more >>>

Quantum computers are expected to revolutionize our ability to process information. The advancement from classical to quantum computing is a product of our advancement from classical to quantum physics -- the more our understanding of the universe grows, so does our ability to use it for computation. A natural question ... more >>>