Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with quantum computing:
TR00-078 | 18th July 2000
Jean-Pierre Seifert

Using fewer Qubits in Shor's Factorization Algorithm via Simultaneous Diophantine Approximation}

While quantum computers might speed up in principle
certain computations dramatically, in pratice, though
quantum computing technology is still in its infancy.
Even we cannot clearly envison at present what the
hardware of that machine will be like.
Nevertheless, we can be quite confident that it will be
more >>>

TR02-059 | 9th August 2002
Iordanis Kerenidis, Ronald de Wolf

Exponential Lower Bound for 2-Query Locally Decodable Codes

We prove exponential lower bounds on the length of 2-query
locally decodable codes. Goldreich et al. recently proved such bounds
for the special case of linear locally decodable codes.
Our proof shows that a 2-query locally decodable code can be decoded
with only 1 quantum query, and then ... more >>>

TR02-072 | 12th November 2002
Scott Aaronson

Quantum Lower Bound for Recursive Fourier Sampling

We revisit the oft-neglected 'recursive Fourier sampling' (RFS) problem, introduced by Bernstein and Vazirani to prove an oracle separation between BPP and BQP. We show that the known quantum algorithm for RFS is essentially optimal, despite its seemingly wasteful need to uncompute information. This implies that, to place BQP outside ... more >>>

TR03-005 | 28th December 2002
Scott Aaronson

Quantum Certificate Complexity

Given a Boolean function f, we study two natural generalizations of the certificate complexity C(f): the randomized certificate complexity RC(f) and the quantum certificate complexity QC(f). Using Ambainis' adversary method, we exactly characterize QC(f) as the square root of RC(f). We then use this result to prove the new relation ... more >>>

TR03-057 | 21st July 2003
Scott Aaronson

Lower Bounds for Local Search by Quantum Arguments

The problem of finding a local minimum of a black-box function is central
for understanding local search as well as quantum adiabatic algorithms.
For functions on the Boolean hypercube {0,1}^n, we show a lower bound of
Omega(2^{n/4}/n) on the number of queries needed by a quantum computer to
solve this ... more >>>

TR03-079 | 8th November 2003
Scott Aaronson

Multilinear Formulas and Skepticism of Quantum Computing

Several researchers, including Leonid Levin, Gerard 't Hooft, and
Stephen Wolfram, have argued that quantum mechanics will break down
before the factoring of large numbers becomes possible. If this is
true, then there should be a natural "Sure/Shor separator" -- that is,
a set of quantum ... more >>>

TR04-045 | 15th April 2004
Hartmut Klauck, Robert Spalek, Ronald de Wolf

Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs

A strong direct product theorem says that if we want to compute
k independent instances of a function, using less than k times
the resources needed for one instance, then our overall success
probability will be exponentially small in k.
We establish such theorems for the classical as well as ... more >>>

TR05-040 | 13th April 2005
Scott Aaronson

Oracles Are Subtle But Not Malicious

Theoretical computer scientists have been debating the role of
oracles since the 1970's. This paper illustrates both that oracles
can give us nontrivial insights about the barrier problems in
circuit complexity, and that they need not prevent us from trying to
solve those problems.

First, we ... more >>>

TR05-129 | 30th October 2005
Scott Aaronson

QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols

This paper introduces a new technique for removing existential quantifiers
over quantum states. Using this technique, we show that there is no way
to pack an exponential number of bits into a polynomial-size quantum
state, in such a way that the value of any one of those bits ... more >>>

TR06-055 | 10th April 2006
Scott Aaronson, Greg Kuperberg

Quantum Versus Classical Proofs and Advice

This paper studies whether quantum proofs are more powerful than
classical proofs, or in complexity terms, whether QMA=QCMA. We prove
two results about this question. First, we give a "quantum oracle
separation" between QMA and QCMA. More concretely, we show that any
quantum algorithm needs order sqrt(2^n/(m+1)) queries to find ... more >>>

TR06-106 | 18th August 2006
Scott Aaronson

The Learnability of Quantum States

Traditional quantum state tomography requires a number of measurements that grows exponentially with the number of qubits n. But using ideas from computational learning theory, we show that "for most practical purposes" one can learn a state using a number of measurements that grows only linearly with n. Besides possible ... more >>>

TR07-013 | 6th February 2007
Andris Ambainis, Joseph Emerson

Quantum t-designs: t-wise independence in the quantum world

A t-design for quantum states is a finite set of quantum states with the property of simulating the Haar-measure on quantum states w.r.t. any test that uses at most t copies of a state. We give efficient constructions for approximate quantum t-designs for arbitrary t.

We then show that an ... more >>>

TR08-017 | 16th December 2007
Thomas Watson, Dieter van Melkebeek

A Quantum Time-Space Lower Bound for the Counting Hierarchy

We obtain the first nontrivial time-space lower bound for quantum algorithms solving problems related to satisfiability. Our bound applies to MajSAT and MajMajSAT, which are complete problems for the first and second levels of the counting hierarchy, respectively. We prove that for every real $d$ and every positive real $\epsilon$ ... more >>>

TR08-051 | 4th April 2008
Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor

The Power of Unentanglement

The class QMA(k), introduced by Kobayashi et al., consists
of all languages that can be verified using k unentangled quantum
proofs. Many of the simplest questions about this class have remained
embarrassingly open: for example, can we give any evidence that k
quantum proofs are more powerful than one? Can ... more >>>

TR08-067 | 4th June 2008
Scott Aaronson

On Perfect Completeness for QMA

Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult, by using ideas from real analysis to give a "quantum oracle" relative to which QMA and QMA1 ... more >>>

TR08-092 | 26th August 2008
Scott Aaronson, John Watrous

Closed Timelike Curves Make Quantum and Classical Computing Equivalent

While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to nontrivial insights in general relativity, quantum information, and other areas. In this paper we show that if CTCs existed, then quantum computers would be no more powerful than classical computers: both would have the ... more >>>

TR09-102 | 21st October 2009
Andrew Drucker, Ronald de Wolf

Quantum Proofs for Classical Theorems

Alongside the development of quantum algorithms and quantum complexity theory in recent years, quantum techniques have also proved instrumental in obtaining results in classical (non-quantum) areas. In this paper we survey these results and the quantum toolbox they use.

more >>>

TR10-110 | 14th July 2010
Ben Reichardt

Span programs and quantum query algorithms

Quantum query complexity measures the number of input bits that must be read by a quantum algorithm in order to evaluate a function. Hoyer et al. (2007) have generalized the adversary semi-definite program that lower-bounds quantum query complexity. By giving a matching algorithm, we show that the general adversary lower ... more >>>

TR10-147 | 22nd September 2010
Dieter van Melkebeek, Thomas Watson

Time-Space Efficient Simulations of Quantum Computations

Revisions: 1

We give two time- and space-efficient simulations of quantum computations with
intermediate measurements, one by classical randomized computations with
unbounded error and the other by quantum computations that use an arbitrary
fixed universal set of gates. Specifically, our simulations show that every
language solvable by a bounded-error quantum algorithm running ... more >>>

TR10-165 | 4th November 2010
Dmitry Gavinsky, Tsuyoshi Ito

Quantum Fingerprints that Keep Secrets

We introduce a new type of cryptographic primitive that we call hiding fingerprinting. No classical fingerprinting scheme is hiding. We construct quantum hiding fingerprinting schemes and argue their optimality.

more >>>

TR10-191 | 9th December 2010
Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland

Symmetry-assisted adversaries for quantum state generation

We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem. This problem encompasses both, the computation of partial or total functions and the preparation of target quantum states. There has been hope for quite some time that quantum ... more >>>

TR11-043 | 25th March 2011
Scott Aaronson

A Linear-Optical Proof that the Permanent is #P-Hard

One of the crown jewels of complexity theory is Valiant's 1979 theorem that computing the permanent of an n*n matrix is #P-hard. Here we show that, by using the model of linear-optical quantum computing---and in particular, a universality theorem due to Knill, Laflamme, and Milburn---one can give a different and ... more >>>

TR11-108 | 8th August 2011
Scott Aaronson

Why Philosophers Should Care About Computational Complexity

Revisions: 2

One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory---the field that studies the ... more >>>

TR12-136 | 26th October 2012
Dan Boneh, Mark Zhandry

Quantum-Secure Message Authentication Codes

Revisions: 2

We construct the first Message Authentication Codes (MACs) that are existentially unforgeable against a quantum chosen message attack. These chosen message attacks model a quantum adversary’s ability to obtain the MAC on a superposition of messages of its choice. We begin by showing that a quantum secure PRF is sufficient ... more >>>

TR12-170 | 30th November 2012
Scott Aaronson, Travis Hance

Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent

Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an n×n matrix A. The algorithm runs in O(n^2/?^2) time, and approximates Per(A) to within ±?||A||^n additive error. A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices. ... more >>>

TR13-164 | 28th November 2013
Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian

Weak Parity

We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2+eps fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that ... more >>>

TR14-181 | 19th December 2014
Scott Aaronson, Adam Bouland, Joseph Fitzsimons, Mitchell Lee

The space "just above" BQP

We explore the space "just above" BQP by defining a complexity class PDQP (Product Dynamical Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform measurements that do not collapse the ... more >>>

TR15-066 | 20th April 2015
Scott Aaronson, Daniel Grier, Luke Schaeffer

The Classification of Reversible Bit Operations

We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversible-computing analogue of Post's lattice, a central result in mathematical ... more >>>

TR15-203 | 13th December 2015
Scott Aaronson, Shalev Ben-David

Sculpting Quantum Speedups

Given a problem which is intractable for both quantum and classical algorithms, can we find a sub-problem for which quantum algorithms provide an exponential advantage? We refer to this problem as the "sculpting problem." In this work, we give a full characterization of sculptable functions in the query complexity setting. ... more >>>

TR16-039 | 15th March 2016
Adam Bouland, Laura Mancinska, Xue Zhang

Complexity Classification of Two-Qubit Commuting Hamiltonians

We classify two-qubit commuting Hamiltonians in terms of their computational complexity. Suppose one has a two-qubit commuting Hamiltonian $H$ which one can apply to any pair of qubits, starting in a computational basis state. We prove a dichotomy theorem: either this model is efficiently classically simulable or it allows one ... more >>>

TR16-146 | 18th September 2016
Scott Aaronson, Mohammad Bavarian, Giulio Gueltrini

Computability Theory of Closed Timelike Curves

We ask, and answer, the question of what's computable by Turing machines equipped with time travel into the past: that is, closed timelike curves or CTCs (with no bound on their size). We focus on a model for CTCs due to Deutsch, which imposes a probabilistic consistency condition to avoid ... more >>>

TR17-176 | 15th November 2017
Kamil Khadiev, Aliya Khadiev, Alexander Knop

Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies

In this paper, we study quantum OBDD model, it is a restricted version of read-once quantum branching programs, with respect to "width" complexity. It is known that the maximal gap between deterministic and quantum complexities is exponential. But there are few examples of functions with such a gap. We present ... more >>>

TR18-099 | 19th May 2018
Scott Aaronson

PDQP/qpoly = ALL

We show that combining two different hypothetical enhancements to quantum computation---namely, quantum advice and non-collapsing measurements---would let a quantum computer solve any decision problem whatsoever in polynomial time, even though neither enhancement yields extravagant power by itself. This complements a related result due to Raz. The proof uses locally decodable ... more >>>

ISSN 1433-8092 | Imprint