Search results for "Quantum capacity"

2014

Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate. First, we show that for any problem that is invariant under permuting inputs and outputs (like the collision or the element distinctness problems), the quantum query complexity is at least the 9 th root of the classical randomized query complexity. This resolves a conjecture of Watrous from 2002. Second, inspired by recent work of O’Donnell et al. and Dinur et al., we conjecture that every bounded low-degree polynomial has a “highly influential” …

Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding

2014

Quantum zero-knowledge proofs and quantum proofs of knowledge are inherently difficult to analyze because their security analysis uses rewinding. Certain cases of quantum rewinding are handled by the results by Watrous (SIAM J Comput, 2009) and Unruh (Eurocrypt 2012), yet in general the problem remains elusive. We show that this is not only due to a lack of proof techniques: relative to an oracle, we show that classically secure proofs and proofs of knowledge are insecure in the quantum setting. More specifically, sigma-protocols, the Fiat-Shamir construction, and Fischlin's proof system are quantum insecure under assumptions that are sufficient for classical security. Additionally, we show…

Superlinear advantage for exact quantum algorithms

2012

A quantum algorithm is exact if, on any input data, it outputs the correct answer with certainty (probability 1). A key question is: how big is the advantage of exact quantum algorithms over their classical counterparts: deterministic algorithms. For total Boolean functions in the query model, the biggest known gap was just a factor of 2: PARITY of N inputs bits requires $N$ queries classically but can be computed with N/2 queries by an exact quantum algorithm. We present the first example of a Boolean function f(x_1, ..., x_N) for which exact quantum algorithms have superlinear advantage over the deterministic algorithms. Any deterministic algorithm that computes our function must use N qu…

Routing quantum information in spin chains

2013

Two different models for performing efficiently routing of a quantum state are presented. Both cases involve an XX spin chain working as data bus and additional spins that play the role of sender and receivers, one of which is selected to be the target of the quantum state transmission protocol via a coherent quantum coupling mechanism making use of local/global magnetic fields. Quantum routing is achieved, in the first of the models considered, by weakly coupling the sender and the receiver to the data bus. In the second model, strong magnetic fields acting on additional spins located between the sender/receiver and the data bus allow us to perform high fidelity routing.

Teleportation-induced correlated quantum channels.

2009

Quantum teleportation of a n-qubit state performed using as entangled resource a general bipartite state of 2n qubits instead of n Bell states is equivalent to a correlated Pauli channel. This provides a new characterization of such channels in terms of many-body correlation functions of the teleporting media. Our model is then generalized to the Continuous Variable case. We show that this new representation provides a relatively simple method for determining whether a correlated quantum channel is able to reliably convey quantum messages by studying the entanglement properties of the teleportation mediating system.

Transition behavior in the channel capacity of two-quibit channels with memory

2004

We prove that a general upper bound on the maximal mutual information of quantum channels is saturated in the case of Pauli channels with an arbitrary degree of memory. For a subset of such channels we explicitly identify the optimal signal states. We show analytically that for such a class of channels entangled states are indeed optimal above a given memory threshold.

Approximate quantum error correction for generalized amplitude damping errors

2014

We present analytic estimates of the performances of various approximate quantum error correction schemes for the generalized amplitude damping (GAD) qubit channel. Specifically, we consider both stabilizer and nonadditive quantum codes. The performance of such error-correcting schemes is quantified by means of the entanglement fidelity as a function of the damping probability and the non-zero environmental temperature. The recovery scheme employed throughout our work applies, in principle, to arbitrary quantum codes and is the analogue of the perfect Knill-Laflamme recovery scheme adapted to the approximate quantum error correction framework for the GAD error model. We also analytically re…

Creating quantum correlations through local non-unitary memoryless channels

2012

We show that two qubits, initially in a fully classical state, can develop significant quantum correlations as measured by the quantum discord (QD) under the action of a local memoryless noise (specifically we consider the case of a Markovian amplitude-damping channel). This is analytically proven after deriving in a compact form the QD for the class of separable states involved in such a process. We provide a picture in the Bloch sphere that unambiguously highlights the physical mechanism behind the effect regardless of the specific measure of QCs adopted.

Accumulation of entanglement in a continuous variable memory

2007

We study the accumulation of entanglement in a memory device built out of two continuous variable (CV) systems. We address the case of a qubit mediating an indirect joint interaction between the CV systems. We show that, in striking contrast with respect to registers built out of bidimensional Hilbert spaces, entanglement superior to a single ebit can be efficiently accumulated in the memory, even though no entangled resource is used. We study the protocol in an immediately implementable setup, assessing the effects of the main imperfections.

Surface entanglement in quantum spin networks

2013

We study the ground-state entanglement in systems of spins forming the boundary of a quantum spin network in arbitrary geometries and dimensionality. We show that as long as they are weakly coupled to the bulk of the network, the surface spins are strongly entangled, even when distant and non directly interacting, thereby generalizing the phenomenon of long-distance entanglement occurring in quantum spin chains. Depending on the structure of the couplings between surface and bulk spins, we discuss in detail how the patterns of surface entanglement can range from multi-pair bipartite to fully multipartite. In the context of quantum information and communication, these results find immediate …