Streaming universal distortion-free entanglement concentration (2009)
Blume-Kohout, Robin, Croke, Sarah, Gottesman, Daniel
This paper presents a streaming (sequential) protocol for universal entanglement concentration at the Shannon bound. Alice and Bob begin with N identical (but unknown) two-qubit pure states, each...
Gottesman, Daniel, Irani, Sandy
We study the complexity of a class of problems involving satisfying constraints which remain the same under translations in one or more spatial directions. In this paper, we show hardness of a...
An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation (2009)
Quantum states are very delicate, so it is likely some sort of quantum error correction will be necessary to build reliable quantum computers. The theory of quantum error-correcting codes has some...
Entanglement vs. gap for one-dimensional spin systems (2009)
Gottesman, Daniel, Hastings, M. B.
We study the relationship between entanglement and spectral gap for local Hamiltonians in one dimension. The area law for a one-dimensional system states that for the ground state, the entanglement...
Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority (2008)
Ben-Or, Michael, Crépeau, Claude, Gottesman, Daniel, Hassidim, Avinatan, Smith, Adam
Secret sharing and multiparty computation (also called "secure function evaluation") are fundamental primitives in modern cryptography, allowing a group of mutually distrustful players to perform...
Michael Ben-Or, Greg Kuperberg, and Boris Tsirelson for helpful discussions, and to (2008)
Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, Yuval Peres, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
Howard Barnum, Claude Crepeau, Daniel Gottesman, Adam Smith
Authentication is a well-studied area of classical cryptography: a sender A and a receiver B sharing a classical private key want to exchange a classical message with the guarantee that the message...
Claude Cr Epeau, Daniel Gottesman, Adam Smith
Secure multi-party computing, also called secure function evaluation, has been extensively studied in classical cryptography. We consider the extension of this task to computation with quantum inputs...
Claude Crepeau, Daniel Gottesman, Adam Smith
Authentication is a well-studied area of classical cryptography: a sender A and a receiver B sharing a classical private key want to exchange a message with the guarantee that the message has not...
The power of quantum systems on a line (2007)
Aharonov, Dorit, Gottesman, Daniel, Irani, Sandy, Kempe, Julia
We study the computational strength of quantum particles (each of finite dimensionality) arranged on a line. First, we prove that it is possible to perform universal adiabatic quantum computation...
Accuracy threshold for postselected quantum computation (2007)
Aliferis, Panos, Gottesman, Daniel, Preskill, John
We prove an accuracy threshold theorem for fault-tolerant quantum computation based on error detection and postselection. Our proof provides a rigorous foundation for the scheme suggested by Knill,...
Fault-Tolerant Quantum Computation (2007)
I give a brief overview of fault-tolerant quantum computation, with an emphasis on recent work and open questions.
GHZ extraction yield for multipartite stabilizer states (2006)
Bravyi, Sergey, Fattal, David, Gottesman, Daniel
Let |Psi> be an arbitrary stabilizer state distributed between three remote parties, such that each party holds several qubits. Let S be a stabilizer group of |Psi>. We show that |Psi> can be...
Quantum error-correcting codes (2006)
Quantum Information, Computation and Complexity * Programme at the Institut Henri Poincaré, January 4th April 7th, 2006 * Organizers: Ph.Grangier, M.Santha and D.L.Shepelyansky * Lectures have...
Quantum error-correcting codes (2006)
Quantum Information, Computation and Complexity * Programme at the Institut Henri Poincaré, January 4th April 7th, 2006 * Organizers: Ph.Grangier, M.Santha and D.L.Shepelyansky * Lectures have...
Quantum Statistics with Classical Particles (2005)
Indistinguishability of particles is normally considered to be an inherently quantum property which cannot be possessed by a classical theory. However, Saunders has argued that this is incorrect, and...
Quantum Error Correction and Fault-Tolerance (2005)
I give an overview of the basic concepts behind quantum error correction and quantum fault tolerance. This includes the quantum error correction conditions, stabilizer codes, CSS codes, transversal...
Classicality in discrete Wigner functions (2005)
Cormick, Cecilia, Galvao, Ernesto F., Gottesman, Daniel, Paz, Juan Pablo, Pittenger, Arthur O.
Gibbons et al. [Phys. Rev. A 70, 062101(2004)] have recently defined a class of discrete Wigner functions W to represent quantum states in a Hilbert space with finite dimension. We show that the only...
Quantum accuracy threshold for concatenated distance-3 codes (2005)
Aliferis, Panos, Gottesman, Daniel, Preskill, John
We prove a new version of the quantum threshold theorem that applies to concatenation of a quantum code that corrects only one error, and we use this theorem to derive a rigorous lower bound on the...
GHZ extraction yield for multipartite stabilizer states (2005)
Bravyi, Sergey, Fattal, David, Gottesman, Daniel
Let $|\Psi>$ be an arbitrary stabilizer state distributed between three remote parties, such that each party holds several qubits. Let $S$ be a stabilizer group of $|\Psi>$. We show that $|\Psi>$ can...
Approximate Quantum Error-Correcting Codes and Secret Sharing Schemes (2005)
Crepeau, Claude, Gottesman, Daniel, Smith, Adam
It is a standard result in the theory of quantum error-correcting codes that no code of length n can fix more than n/4 arbitrary errors, regardless of the dimension of the coding and encoded Hilbert...
Thoughts on noise and quantum computing (2005)
Gil Kalai, Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
Michael Ben-Or, Greg Kuperberg, and Boris Tsirelson for helpful discussions, and to (2005)
Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, Yuval Peres, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
Approximate Quantum ErrorCorrecting Codes and Secret Sharing Schemes (2005)
Claude Crépeau, Daniel Gottesman, Adam Smith
Abstract. It is a standard result in the theory of quantum error-correcting codes that no code of length n can fix more than n/4 arbitrary errors, regardless of the dimension of the coding and...
Stabilizer codes and quantum error correction (2004)
Controlling operational errors and decoherence is one of the major challenges facing the field of quantum computation and other attempts to create specified many-particle entangled states. The field...
Improved Simulation of Stabilizer Circuits (2004)
Aaronson, Scott, Gottesman, Daniel
The Gottesman-Knill theorem says that a stabilizer circuit -- that is, a quantum circuit consisting solely of CNOT, Hadamard, and phase gates -- can be simulated efficiently on a classical computer....
Comment on "The black hole final state" (2004)
Gottesman, Daniel, Preskill, John
Horowitz and Maldacena have suggested that the unitarity of the black hole S-matrix can be reconciled with Hawking's semiclassical arguments if a final-state boundary condition is imposed at the...
ACKNOWLEDGEMENTS iii Acknowledgements (2004)
Daniel Gottesman, The Members, Particularly David Beckman, John Cortese
COPYRIGHT ii c ○ 2004
Comment on "The black hole final state" (2003)
Gottesman, Daniel, Preskill, John
Horowitz and Maldacena have suggested that the unitarity of the black hole S-matrix can be reconciled with Hawking's semiclassical arguments if a final-state boundary condition is imposed at the...
The Minimum Distance Problem for Two-Way Entanglement Purification (2003)
Ambainis, Andris, Gottesman, Daniel
Entanglement purification takes a number of noisy EPR pairs and processes them to produce a smaller number of more reliable pairs. If this is done with only a forward classical side channel, the...
Security of quantum key distribution with imperfect devices (2002)
Gottesman, Daniel, Lo, Hoi-Kwong, Lütkenhaus, Norbert, Preskill, John
We prove the security of the Bennett-Brassard (BB84) quantum key distribution protocol in the case where the source and detector are under the limited control of an adversary. Our proof applies when...
Quantum states cannot be cloned. I show how to extend this property to classical messages encoded using quantum states, a task I call "uncloneable encryption." An uncloneable encryption scheme has...
Secure Multi-party Quantum Computing (2002)
Crepeau, Claude, Gottesman, Daniel, Smith, Adam
Secure multi-party computing, also called "secure function evaluation", has been extensively studied in classical cryptography. We consider the extension of this task to computation with quantum...
Authentication of Quantum Messages (2002)
Barnum, Howard, Crepeau, Claude, Gottesman, Daniel, Smith, Adam, Tapp, Alain
Authentication is a well-studied area of classical cryptography: a sender S and a receiver R sharing a classical private key want to exchange a classical message with the guarantee that the message...
Measurability of Wilson loop operators (2002)
Beckman, David, Gottesman, Daniel, Kitaev, Alexei, Preskill, John
We show that the nondemolition measurement of a spacelike Wilson loop operator W(C) is impossible in a relativistic non-Abelian gauge theory. In particular, if two spacelike-separated magnetic flux...
Byzantine Agreement Secure Against Faulty Majorities From Scratch (2002)
Matthias Fitzi, Daniel Gottesman, Martin Hirt, Thomas Holenstein, Adam Smith
It is well-known that n players, connected only by pairwise secure channels, can achieve Byzantine agreement only if the number t of cheaters satises t n=3, even with respect to computational...
Authentication of quantum messages (2002)
Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam Smith
Authentication is a well-studied area of classical cryptography: a sender A and a receiver B sharing a classical secret key want to exchange a classical message with the guarantee that the message...
Detectable Byzantine Agreement Secure against Faulty Majorities (2002)
Matthias Fitzi, Daniel Gottesman, Adam Smith, Thomas Holenstein, Martin Hirt
BA6C@D2FE(G2)HJI:;GK8&LF4NMONA@@B8NOP2F8QRA@:5KTSKTIBG$3=L"6C354"8U4"8NONVLF8 OPEBG$@B@8N:54NMOG @WG OPE3;8&X8ZY[K\G$@2F35@B8JG$]$LF8&8N^_8N@2`A@:5Ka3=b92FEB8c@V^cSd8&L...
From Quantum Cheating to Quantum Security (2001)
Gottesman, Daniel, Lo, Hoi-Kwong
For thousands of years, code-makers and code-breakers have been competing for supremacy. Their arsenals may soon include a powerful new weapon: quantum mechanics. We give an overview of quantum...
Causal and localizable quantum operations (2001)
Beckman, David, Gottesman, Daniel, Nielsen, M. A., Preskill, John
We examine constraints on quantum operations imposed by relativistic causality. A bipartite superoperator is said to be localizable if it can be implemented by two parties (Alice and Bob) who share...
Measurability of Wilson loop operators (2001)
Beckman, David, Gottesman, Daniel, Kitaev, Alexei, Preskill, John
We show that the nondemolition measurement of a spacelike Wilson loop operator W(C) is impossible in a relativistic non-Abelian gauge theory. In particular, if two spacelike-separated magnetic flux...
Encoding a qubit in an oscillator (2001)
Gottesman, Daniel, Kitaev, Alexei, Preskill, John
Quantum error-correcting codes are constructed that embed a finite-dimensional code space in the infinite-dimensional Hilbert space of a system described by continuous quantum variables. These codes...
Proof of security of quantum key distribution with two-way classical communications (2001)
Gottesman, Daniel, Lo, Hoi-Kwong
Shor and Preskill have provided a simple proof of security of the standard quantum key distribution scheme by Bennett and Brassard (BB84) by demonstrating a connection between key distribution and...
Quantum Digital Signatures (2001)
Gottesman, Daniel, Chuang, Isaac
We present a quantum digital signature scheme whose security is based on fundamental principles of quantum physics. It allows a sender (Alice) to sign a message in such a way that the signature can...
Causal and localizable quantum operations (2001)
Beckman, David, Gottesman, Daniel, Nielsen, M. A., Preskill, John
We examine constraints on quantum operations imposed by relativistic causality. A bipartite superoperator is said to be localizable if it can be implemented by two parties (Alice and Bob) who share...
Secure quantum key distribution using squeezed states (2001)
Gottesman, Daniel, Preskill, John
We prove the security of a quantum key distribution scheme based on transmission of squeezed quantum states of a harmonic oscillator. Our proof employs quantum error-correcting codes that encode a...
Secure quantum key distribution using squeezed states (2000)
Gottesman, Daniel, Preskill, John
We prove the security of a quantum key distribution scheme based on transmission of squeezed quantum states of a harmonic oscillator. Our proof employs quantum error-correcting codes that encode a...
Encoding a qubit in an oscillator (2000)
Gottesman, Daniel, Kitaev, Alexei, Preskill, John
Quantum error-correcting codes are constructed that embed a finite-dimensional code space in the infinite-dimensional Hilbert space of a system described by continuous quantum variables. These codes...
A quantum analog of Huffman coding (2000)
Braunstein, Samuel L., Fuchs, Christopher A., Gottesman, Daniel, Lo, Hoi-Kwong
We analyze a generalization of Huffman coding to the quantum case. In particular, we notice various difficulties in using instantaneous codes for quantum communication. Nevertheless, for the storage...
An Introduction to Quantum Error Correction (2000)
Quantum states are very delicate, so it is likely some sort of quantum error correction will be necessary to build reliable quantum computers. The theory of quantum error-correcting codes has some...
On the Theory of Quantum Secret Sharing (1999)
I present a variety of results on the theory of quantum secret sharing. I show that any mixed state quantum secret sharing scheme can be derived by discarding a share from a pure state scheme, and...
Quantum Teleportation is a Universal Computational Primitive (1999)
Gottesman, Daniel, Chuang, Isaac L.
We present a method to create a variety of interesting gates by teleporting quantum bits through special entangled states. This allows, for instance, the construction of a quantum computer based on...
Fault-Tolerant Quantum Computation with Local Gates (1999)
I discuss how to perform fault-tolerant quantum computation with concatenated codes using local gates in small numbers of dimensions. I show that a threshold result still exists in three, two, or one...
How to share a quantum secret (1999)
Cleve, Richard, Gottesman, Daniel, Lo, Hoi-Kwong
We investigate the concept of quantum secret sharing. In a ((k,n)) threshold scheme, a secret quantum state is divided into n shares such that any k of those shares can be used to reconstruct the...
The Heisenberg Representation of Quantum Computers (1998)
Since Shor's discovery of an algorithm to factor numbers on a quantum computer in polynomial time, quantum computation has become a subject of immense interest. Unfortunately, one of the key features...
A quantum analog of Huffman coding (1998)
Braunstein, Samuel L., Fuchs, Christopher A., Gottesman, Daniel, Lo, Hoi-Kwong
We analyze a generalization of Huffman coding to the quantum case. In particular, we notice various difficulties in using instantaneous codes for quantum communication. Nevertheless, for the storage...
Fault-Tolerant Quantum Computation with Higher-Dimensional Systems (1998)
Instead of a quantum computer where the fundamental units are 2-dimensional qubits, we can consider a quantum computer made up of d-dimensional systems. There is a straightforward generalization of...
Theory of fault-tolerant quantum computation (1998)
In order to use quantum error-correcting codes to improve the performance of a quantum computer, it is necessary to be able to perform operations fault-tolerantly on encoded states. I present a...
Stabilizer Codes and Quantum Error Correction (1997)
Controlling operational errors and decoherence is one of the major challenges facing the field of quantum computation and other attempts to create specified many-particle entangled states. The field...
Stabilizer codes and quantum error correction (1997)
Controlling operational errors and decoherence is one of the major challenges facing the field of quantum computation and other attempts to create specified many-particle entangled states. The field...
A Theory of Fault-Tolerant Quantum Computation (1997)
In order to use quantum error-correcting codes to actually improve the performance of a quantum computer, it is necessary to be able to perform operations fault-tolerantly on encoded states. I...
Efficient computations of encodings for quantum error correction (1997)
Richard Cleve, Daniel Gottesman
We show how, given any set of generators of the stabilizer of a quantum code, an efficient gate array that computes the codewords can be constructed. For an n-qubit code whose stabilizer has d...
EFFICIENT COMPUTATIONS OF ENCODINGS FOR QUANTUM ERROR CORRECTION (1996)
Cleve, Richard, Gottesman, Daniel
We show how, given any set of generators of the stabilizer of a quantum code, an efficient gate array that computes the codewords can be constructed. For an In-qubit code whose stabilizer has Id...
EFFICIENT COMPUTATIONS OF ENCODINGS FOR QUANTUM ERROR CORRECTION (1996)
Cleve, Richard, Gottesman, Daniel
We show how, given any set of generators of the stabilizer of a quantum code, an efficient gate array that computes the codewords can be constructed. For an In-qubit code whose stabilizer has Id...
I describe a method for pasting together certain quantum error-correcting codes that correct one error to make a single larger one-error quantum code. I show how to construct codes encoding 7 qubits...
Efficient Computations of Encodings for Quantum Error Correction (1996)
Cleve, Richard, Gottesman, Daniel
We show how, given any set of generators of the stabilizer of a quantum code, an efficient gate array that computes the codewords can be constructed. For an n-qubit code whose stabilizer has d...
A Class of Quantum Error-Correcting Codes Saturating the Quantum Hamming Bound (1996)
I develop methods for analyzing quantum error-correcting codes, and use these methods to construct an infinite class of codes saturating the quantum Hamming bound. These codes encode $k=n-j-2$ qubits...
Traversable Wormholes and Black Hole Complementarity (1994)
Black hole complementarity is incompatible with the existence of traversable wormholes. In fact, traversable wormholes cause problems for any theory where information comes out in the Hawking...