Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with quantum information:
TR05-038 | 10th April 2005
Ran Raz

Quantum Information and the PCP Theorem

We show how to encode $2^n$ (classical) bits $a_1,...,a_{2^n}$
by a single quantum state $|\Psi \rangle$ of size $O(n)$ qubits,
such that:
for any constant $k$ and any $i_1,...,i_k \in \{1,...,2^n\}$,
the values of the bits $a_{i_1},...,a_{i_k}$ can be retrieved
from $|\Psi \rangle$ by a one-round Arthur-Merlin interactive ... 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 >>>

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

TR18-044 | 5th March 2018
Alessandro Chiesa, Michael Forbes, Tom Gur, Nicholas Spooner

Spatial Isolation Implies Zero Knowledge Even in a Quantum World

Revisions: 1

Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable physical assumption: if the provers are spatially isolated, ... more >>>

TR19-060 | 18th April 2019
Scott Aaronson, Guy Rothblum

Gentle Measurement of Quantum States and Differential Privacy

In differential privacy (DP), we want to query a database about $n$ users, in a way that "leaks at most $\varepsilon$ about any individual user," even conditioned on any outcome of the query. Meanwhile, in gentle measurement, we want to measure $n$ quantum states, in a way that "damages the ... more >>>

ISSN 1433-8092 | Imprint