Alexei Kitaev

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

Tomoyuki Yamakami, Andrew Chi-Chih Yao

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

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

Cristopher Moore

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

Howard Barnum, Michael Saks

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

Harumichi Nishimura, Tomoyuki Yamakami

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

Yaoyun Shi

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

Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis

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

Jorge Castro

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

Farid Ablayev, Alexander Vasiliev

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

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

Chris Peikert

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

Scott Aaronson, Andrew Drucker

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

Scott Aaronson, Andrew Drucker

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

Yang Liu, Shengyu Zhang

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

Cassio P. de Campos, Georgios Stamoulis, Dennis Weyland

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

A. C. Cem Say, Abuzer Yakaryilmaz

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

Ryan O'Donnell, A. C. Cem Say

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

Daniel Grier, Luke Schaeffer

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

Srinivasan Arunachalam, Alex Bredariol Grilo, Aarthi Sundaram

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

Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler

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

Scott Aaronson, Harry Buhrman, William Kretschmer

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

Uma Girish, Ran Raz, Wei Zhan

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