Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > QUANTUM:
Reports tagged with quantum:
TR05-026 | 15th February 2005
Scott Aaronson

#### NP-complete Problems and Physical Reality

Can NP-complete problems be solved efficiently in the physical universe?
I survey proposals including soap bubbles, protein folding, quantum
quantum-mechanical nonlinearities, hidden variables, relativistic time
dilation, analog computing, Malament-Hogarth spacetimes, quantum
gravity, closed timelike curves, and "anthropic computing." The ... more >>>

TR06-086 | 25th July 2006
Dmytro Gavinsky, Julia Kempe, Ronald de Wolf

#### Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function

We give an exponential separation between one-way quantum and classical communication complexity for a Boolean function. Earlier such a separation was known only for a relation. A very similar result was obtained earlier but independently by Kerenidis and Raz [KR06]. Our version of the result gives an example in the ... more >>>

TR06-087 | 25th July 2006
Iordanis Kerenidis, Ran Raz

#### The one-way communication complexity of the Boolean Hidden Matching Problem

We give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for ... more >>>

TR10-186 | 2nd December 2010
Bill Fefferman, Ronen Shaltiel, Chris Umans, Emanuele Viola

#### On beating the hybrid argument

The {\em hybrid argument}
allows one to relate
the {\em distinguishability} of a distribution (from
uniform) to the {\em
predictability} of individual bits given a prefix. The
argument incurs a loss of a factor $k$ equal to the
bit-length of the
distributions: $\epsilon$-distinguishability implies only
$\epsilon/k$-predictability. ... more >>>

TR12-140 | 27th October 2012
Mark Zhandry

#### How to Construct Quantum Random Functions

Revisions: 2

In the presence of a quantum adversary, there are two possible definitions of security for a pseudorandom function. The first, which we call standard-security, allows the adversary to be quantum, but requires queries to the function to be classical. The second, quantum-security, allows the adversary to query the function on ... more >>>

TR13-154 | 29th October 2013
Martin Schwarz, Maarten Van den Nest

#### Simulating Quantum Circuits with Sparse Output Distributions

We show that several quantum circuit families can be simulated efficiently classically if it is promised that their output distribution is approximately sparse i.e. the distribution is close to one where only a polynomially small, a priori unknown subset of the measurement probabilities are nonzero. Classical simulations are thereby obtained ... more >>>

TR15-173 | 29th October 2015
Martin Schwarz

#### An exponential time upper bound for Quantum Merlin-Arthur games with unentangled provers

We prove a deterministic exponential time upper bound for Quantum Merlin-Arthur games with k unentangled provers. This is the first non-trivial upper bound of QMA(k) better than NEXP and can be considered an exponential improvement, unless EXP=NEXP. The key ideas of our proof are to use perturbation theory to reduce ... more >>>

TR19-107 | 29th July 2019
Zachary Remscrim

#### The Power of a Single Qubit: Two-way Quantum/Classical Finite Automata and the Word Problem for Linear Groups

Revisions: 1

The two-way quantum/classical finite automaton (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA, with a single qubit, can recognize, with one-sided bounded-error, the language $L_{eq}=\{a^m b^m |m \in \mathbb{N}\}$ in ... more >>>

TR19-182 | 9th December 2019
Zachary Remscrim

Revisions: 1

The two-way finite automaton with quantum and classical states (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA with only a single-qubit can recognize the language $L_{pal}=\{w \in \{a,b\}^*:w \text{ is ... more >>> TR21-087 | 22nd June 2021 Uma Girish, Ran Raz #### Eliminating Intermediate Measurements using Pseudorandom Generators Revisions: 1 We show that quantum algorithms of time T and space$S \ge \log T$with intermediate measurements can be simulated by quantum algorithms of time$T\cdot \mathrm{poly}(S)$and space$O(S\cdot \log T)$without intermediate measurements. The best simulations prior to this work required either$\Omega(T)\$ space (by the deferred measurement ... more >>>

ISSN 1433-8092 | Imprint