Eigenpath traversal by phase randomization (2009)
Boixo, Sergio, Knill, Emanuel, Somma, Rolando
A computation in adiabatic quantum computing is implemented by traversing a path of nondegenerate eigenstates of a continuous family of Hamiltonians. We introduce a method that traverses a...
Restrictions on Transversal Encoded Quantum Gate Sets (2008)
Transversal gates play an important role in the theory of fault-tolerant quantum computation due to their simplicity and robustness to noise. By definition, transversal operators do not couple...
Optimal Quantum Measurements of Expectation Values of Observables (2006)
Knill, Emanuel, Ortiz, Gerardo, Somma, Rolando D.
Experimental characterizations of a quantum system involve the measurement of expectation values of observables for a preparable state |psi> of the quantum system. Such expectation values can be...
Somma, Rolando, Barnum, Howard, Ortiz, Gerardo, Knill, Emanuel
We consider quantum computational models defined via a Lie-algebraic theory. In these models, specified initial states are acted on by Lie-algebraic quantum gates and the expectation values of Lie...
Random decoupling schemes for quantum dynamical control and error suppression (2005)
Viola, Lorenza, Knill, Emanuel
We present a general control-theoretic framework for constructing and analyzing random decoupling schemes, applicable to quantum dynamical control of arbitrary finite-dimensional composite systems....
Entanglement as an Observer-Dependent Concept: An Application to Quantum Phase Transitions (2004)
Ortiz, Gerardo, Somma, Rolando, Barnum, Howard, Knill, Emanuel, Viola, Lorenza
This paper addresses the following main question: Do we have a theoretical understanding of entanglement applicable to a full variety of physical settings? It is clear that not only the assumption of...
Entanglement beyond subsystems (2004)
Viola, Lorenza, Barnum, Howard, Knill, Emanuel, Ortiz, Gerardo, Somma, Rolando
We present a notion of generalized entanglement which goes beyond the conventional definition based on quantum subsystems. This is accomplished by directly defining entanglement as a property of...
Nature and Measure of Entanglement in Quantum Phase Transitions (2004)
Somma, Rolando, Ortiz, Gerardo, Barnum, Howard, Knill, Emanuel, Viola, Lorenza
Characterizing and quantifying quantum correlations in states of many-particle systems is at the core of a full understanding of phase transitions in matter. In this work, we continue our...
The quantum query complexity of the hidden subgroup problem is polynomial (2004)
Ettinger, Mark, Hoyer, Peter, Knill, Emanuel
We present a quantum algorithm which identifies with certainty a hidden subgroup of an arbitrary finite group G in only a polynomial (in log |G|) number of calls to the oracle. This is exponentially...
A subsystem-independent generalization of entanglement (2003)
Barnum, Howard, Knill, Emanuel, Ortiz, Gerardo, Somma, Rolando, Viola, Lorenza
We introduce a generalization of entanglement based on the idea that entanglement is relative to a distinguished subspace of observables rather than a distinguished subsystem decomposition. A pure...
Quantum Simulations of Physics Problems (2003)
Somma, Rolando, Ortiz, Gerardo, Knill, Emanuel, Gubernatis, James
If a large Quantum Computer (QC) existed today, what type of physical problems could we efficiently simulate on it that we could not simulate on a classical Turing machine? In this paper we argue...
A note on verification procedures for quantum noiseless subsystems (2003)
Viola, Lorenza, Knill, Emanuel
We establish conditions under which the experimental verification of quantum error-correcting behavior against a linear set of error operators $\ce$ suffices for the verification of noiseless...
Exploring Noiseless Subsystems via Nuclear Magnetic Resonance (2002)
Fortunato, Evan M., Viola, Lorenza, Pravia, Marco A., Knill, Emanuel, Laflamme, Raymond, Havel, Timothy F., ...
Noiseless subsystems offer a general and efficient method for protecting quantum information in the presence of noise that has symmetry properties. A paradigmatic class of error models displaying...
Robust dynamical decoupling with bounded controls (2002)
Viola, Lorenza, Knill, Emanuel
We propose a general procedure for implementing dynamical decoupling without requiring arbitrarily strong, impulsive control actions. This is accomplished by designing continuous decoupling...
Constructing Qubits in Physical Systems (2001)
Viola, Lorenza, Knill, Emanuel, Laflamme, Raymond
The notion of a qubit is ubiquitous in quantum information processing. In spite of the simple abstract definition of qubits as two-state quantum systems, identifying qubits in physical systems is...
Nonbinary Quantum Stabilizer Codes (2000)
Ashikhmin, Alexei, Knill, Emanuel
We define and show how to construct nonbinary quantum stabilizer codes. Our approach is based on nonbinary error bases. It generalizes the relationship between selforthogonal codes over $GF_{4}$ and...
A Study of Quantum Error Correction by Geometric Algebra and Liquid-State NMR Spectroscopy (2000)
Sharf, Yehuda, Cory, David G., Somaroo, Shyamal S., Havel, Timothy F., Knill, Emanuel, Laflamme, Raymond
Quantum error correcting codes enable the information contained in a quantum state to be protected from decoherence due to external perturbations. Applied to NMR, quantum coding does not alter normal...
Dynamical Generation of Noiseless Quantum Subsystems (2000)
Viola, Lorenza, Knill, Emanuel, Lloyd, Seth
We present control schemes for open quantum systems that combine decoupling and universal control methods with coding procedures. By exploiting a general algebraic approach, we show how appropriate...
Quantum error detection I: Statement of the problem (2000)
Alexei E. Ashikhmin, Er M. Barg, Emanuel Knill, Simon N. Litsyn
Abstract—This paper is devoted to the problem of error detection with quantum codes.We show that it is possible to give a consistent definition of the undetected error event. To prove this, we...
Theory of Quantum Error Correction for General Noise (1999)
Knill, Emanuel, Laflamme, Raymond, Viola, Lorenza
Quantum error correction protects quantum information against environmental noise. When using qubits, a measure of quality of a code is the maximum number of errors that it is able to correct. We...
Quantum Error Detection I: Statement of the Problem (1999)
Ashikhmin, Alexei, Barg, Alexander, Knill, Emanuel, Litsyn, Simon
I. This paper is devoted to the problem of error detection with quantum codes. In the first part we examine possible problem settings for quantum error detection. Our goal is to derive a functional...
Universal Control of Decoupled Quantum Systems (1999)
Viola, Lorenza, Lloyd, Seth, Knill, Emanuel
It is shown that if one can perform a restricted set of fast manipulations on a quantum system, one can implement a large class of dynamical evolutions by effectively removing or introducing selected...
Hidden Subgroup States are Almost Orthogonal (1999)
Ettinger, Mark, Hoyer, Peter, Knill, Emanuel
It is well known that quantum computers can efficiently find a hidden subgroup $H$ of a finite Abelian group $G$. This implies that after only a polynomial (in $\log |G|$) number of calls to the...
Hidden Subgroup States are Almost Orthogonal (1999)
Mark Ettinger, Peter Høyer, Emanuel Knill
It is well known that quantum computers can efficiently find a hidden subgroup H of a finite Abelian group G. This implies that after only a polynomial (in log jGj) number of calls to the oracle...
Dynamical Decoupling of Open Quantum Systems (1998)
Viola, Lorenza, Knill, Emanuel, Lloyd, Seth
We propose a novel dynamical method for beating decoherence and dissipation in open quantum systems. We demonstrate the possibility of filtering out the effects of unwanted (not necessarily known)...
David Wolpert, Emanuel Knill, Tal Grossman
In this paper we analyze the average behavior of the Bayes-optimal and Gibbs learning algorithms. We do this both for off-training-set error and conventional IID error (for which test sets overlap...
Effective Pure States for Bulk Quantum Computation (1997)
Knill, Emanuel, Chuang, Isaac, Laflamme, Raymond
In bulk quantum computation one can manipulate a large number of indistinguishable quantum computers by parallel unitary operations and measure expectation values of certain observables with limited...
Resilient Quantum Computation: Error Models and Thresholds (1997)
Knill, Emanuel, Laflamme, Raymond, Zurek, Wojciech H.
Recent research has demonstrated that quantum computers can solve certain types of problems substantially faster than the known classical algorithms. These problems include factoring integers and...
Concatenated Quantum Codes (1996)
Knill, Emanuel, Laflamme, Raymond
One of the main problems for the future of practical quantum computing is to stabilize the computation against unwanted interactions with the environment and imperfections in the applied operations....
A Theory of Quantum Error-Correcting Codes (1996)
Knill, Emanuel, Laflamme, Raymond
Quantum Error Correction will be necessary for preserving coherent states against noise and other unwanted interactions in quantum computation and communication. We develop a general theory of...
A Theory of Quantum Error-Correcting Codes (1996)
Emanuel Knill, Raymond Laflamme
Quantum Error Correction will be necessary for preserving coherent states against noise and other unwanted interactions in quantum computation and communication. We develop a general theory of...
Accuracy Threshold for Quantum Computation (1996)
Emanuel Knill, Raymond Laflamme, Wojciech Zurek
We have previously [11] shown that for quantum memories and quantum communication, a state can be transmitted over arbitrary distances with error ffl provided each gate has error at most cffl. We...
Families of Sets with Locally Bounded Width (1996)
A family of sets F is locally k-wide if and only if the width (as a poset ordered by inclusion) of F x = fU 2 F j x 2 Ug is at most k for every x. The directed covering graph of a locally 1-wide...
David H. Wolpert, Emanuel Knill, Tal Grossman
In this paper we analyze the average behavior of the Bayes-optimal and Gibbs learning algorithms. We do this both for off-training-set error and conventional IID error (for which test sets overlap...
Restricted Routing and Wide Diameter of the Cycle Prefix Network (1996)
Vance Faber, Emanuel Knill, Mail Stop B
The cycle prefix network is a Cayley coset digraph based on sequences over an alphabet which has been proposed as a vertex symmetric communication network. This network has been shown to have many...
An analysis of Bennett's pebble game (1995)
Bennett's pebble game was introduced to obtain better time/space tradeoffs in the simulation of standard Turing machines by reversible ones. So far only upper bounds for the tradeoff based on the...
Group testing problems in experimental molecular biology (1995)
Knill, Emanuel, Muthukrishnan, S.
In group testing, the task is to determine the distinguished members of a set of objects L by asking subset queries of the form ``does the subset Q of L contain a distinguished object?'' The primary...
Efficient pooling designs for library screening (1994)
Bruno, William J., Knill, Emanuel, Balding, David J., Bruce, D. C., Doggett, N. A., Sawhill, W. W., ...
We describe efficient methods for screening clone libraries, based on pooling schemes which we call ``random $k$-sets designs''. In these designs, the pools in which any clone occurs are equally...
Notes on the connectivity of Cayley coset digraphs (1994)
Hamidoune's connectivity results for hierarchical Cayley digraphs are extended to Cayley coset digraphs and thus to arbitrary vertex transitive digraphs. It is shown that if a Cayley coset digraph...
Generalized degrees and densities for families of sets (1994)
Let F be a family of subsets of {1,2,...,n}. The width-degree of an element x in at least one member of F is the width of the family {U in F | x in U}. If F has maximum width-degree at most k, then F...
Lower bounds for identifying subset members with subset queries (1994)
An instance of a group testing problem is a set of objects $\cO$ and an unknown subset $P$ of $\cO$. The task is to determine $P$ by using queries of the type ``does $P$ intersect $Q$'', where $Q$ is...
Inverting sets and the packing problem (1994)
Faber, Vance, Goldberg, Mark, Knill, Emanuel, Spencer, Thomas
Given a set $V$, a subset $S$, and a permutation $\pi$ of $V$, we say that $\pi$ permutes $S$ if $\pi (S) \cap S = \emptyset$. Given a collection $\cS = \{V; S_1,\ldots , S_m\}$, where $S_i \subseteq...
Invertible families of sets of bounded degree (1994)
Let H = (H,V) be a hypergraph with edge set H and vertex set V. Then hypergraph H is invertible iff there exists a permutation pi of V such that for all E belongs to H(edges) intersection of(pi(E)...
Graph generated union-closed families of sets (1994)
Let G be a graph with vertices V and edges E. Let F be the union-closed family of sets generated by E. Then F is the family of subsets of V without isolated points. Theorem: There is an edge e...
Restricted routing and wide diameter of the cycle prefix network (1994)
Chen, William Y. C., Faber, Vance, Knill, Emanuel
The cycle prefix network is a Cayley coset digraph based on sequences over an alphabet which has been proposed as a vertex symmetric communication network. This network has been shown to have many...
Invertible Families of Sets of Bounded Degree (1994)
Let H = (H; V ) be a hypergraph with edge set H and vertex set V . Then H is invertible iff there exists a permutation ß of V such that for all E 2 H, ß(E) " E = ;. H is invertibility critical...
Graph Generated Union-closed Families of Sets (1993)
Let G be a graph with vertices V and edges E. Let F = f S e2E e j E ` Eg be the union-closed family of sets generated by E. Then F is the family of subsets of V without isolated points. Theorem:...
Let P be a poset. A subset A of P is a k-family iff A contains no (k+1)- element chain. For i 1, let A i be the set of elements of A at depth i \Gamma 1 in A. The k-families of P can be ordered by...
Notes on The Connectivity of Cayley Coset Digraphs (1993)
. Hamidoune's connectivity results [11] for hierarchical Cayley digraphs are extended to Cayley coset digraphs and thus to arbitrary vertex transitive digraphs. It is shown that if a Cayley...
The Size of k-pseudotrees (1992)
Emanuel Knill, Andrzej Ehrenfeucht, David Haussler, Mailstop K
Let X be a finite set. A k-pseudotree on X is a family F of subsets of X such that: (i) X 2 F and for every x 2 X, fxg 2 F ; (ii) for every U 2 F there exists an x 2 U such that if V 2 F and x 2 V ,...
Generalized degrees and densities for families of sets /--by Emanuel Knill. (1991)
Thesis (Ph. D.)--University of Colorado, 1991.
Off-Training-Set Error for the Gibbs and the Bayes Optimal Generalizers
Tal Grossman, Emanuel Knill, David Wolpert
In this paper we analyze the average off-training-set behavior of the Bayes-optimal and Gibbs learning algorithms. We do this by exploiting the concept of refinement, which concerns the relationship...