Non-locality and Communication Complexity (2009)
Buhrman, Harry, Cleve, Richard, Massar, Serge, De Wolf, Ronald
Quantum information processing is the emerging field that defines and realizes computing devices that make use of quantum mechanical principles, like the superposition principle, entanglement, and...
Discrete-Query Quantum Algorithm for NAND Trees (2009)
Childs, Andrew M., Cleve, Richard, Jordan, Stephen P., Yonge-Mallo, David
This is a comment on the article “A Quantum Algorithm for the Hamiltonian NAND Tree” by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, Theory of Computing 4 (2008) 169--190. That paper gave a...
Quantum entanglement and the communication complexity of the inner product function (2009)
Richard Cleve, Wim Van Dam, Michael Nielsen
4 Universit'e de Montr'ealk
Notes on Bell’s Theorem and Communication Complexity (2008)
For a discussion of Bell’s Theorem from a data processing perspective, we refer the reader to [4, 3]. 1 Also, an excellent survey of quantum communication complexity can be found in [2]. 2 Both [4,...
Abstract We give new bounds on the circuit complexity of the quan-tum Fourier transform (QFT). We give an upper bound of O(log n + log log(1=")) on the circuit depth for comput-ing an...
Quantum Lower Bounds for the Goldreich-Levin Problem (2008)
Mark Adcock, Richard Cleve, Kazuo Iwama, Raymond Putra, Shigeru Yamashita
At the heart of the Goldreich-Levin Theorem is the problem of determining an n-bit string a by making queries to two oracles, referred to as IP (inner product) and EQ (equivalence). The IP oracle, on...
Abstract Devices General Terms Theory (2008)
Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, Daniel A. Spielman
We construct a black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time...
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald De Wolf
quant-ph/9802049 v3
Martingales, collective coin flipping and discrete control processes (Extended Abstract) (2007)
Richard Cleve, Russell Impagliazzo
We show that for any martingale X 0; X 1; : : : ; Xn with X 0 = 1
Harry Buhrman, Richard Cleve, John Watrous, Ronald De Wolf
Classical ngerprinting associates with each string a shorter string (its ngerprint), such that, with high probability, any two distinct strings can be distinguished by comparing their ngerprints...
Harry Buhrman, Richard Cleve, John Watrous, Ronald De Wolf
Classical ngerprinting associates with each string a shorter string (its ngerprint), such that, with high probability, any two distinct strings can be distinguished by comparing their ngerprints...
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald De Wolf, Name Robert Beals, ...
A preliminary version of this paper was presented at FOCS'98 [Beals et al. 1998]. HB and RdW are partially supported by EU fth framework program QAIP, IST-1999-11234. RC and MM gratefully...
Quantum Algorithms for Evaluating MIN-MAX Trees (2007)
Cleve, Richard, Gavinsky, Dmitry, Yeung, David L.
We present a bounded-error quantum algorithm for evaluating Min-Max trees. For a tree of size N our algorithm makes N^{1/2+o(1)} comparison queries, which is close to the optimal complexity for this...
Cleve, Richard, Gavinsky, Dmitry, Jain, Rahul
We show that, for any language in NP, there is an entanglement-resistant constant-bit two-prover interactive proof system with a constant completeness vs. soundness gap. The previously proposed...
Discrete-query quantum algorithm for NAND trees (2007)
Childs, Andrew M., Cleve, Richard, Jordan, Stephen P., Yeung, David
Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for evaluating NAND trees that runs in time O(sqrt(N log N)) in the Hamiltonian query model. In this note, we point out that their...
Quantum algorithms for hamiltonian simulation (2007)
Berry, Dominic W, Ahokas, Graeme, Cleve, Richard
Research and development in the pioneering field of quantum computing involve just about every facet of science and engineering, including the significant areas of mathematics and physics. Based on...
Richard Cleve, Dmitry Gavinsky, Rahul Jain
We show that, for any language in NP, there is an entanglement-resistant constant-bit two-prover interactive proof system with a constant completeness vs. soundness gap. The previously proposed...
Strong Parallel Repetition Theorem for Quantum XOR Proof Systems (2006)
Cleve, Richard, Slofstra, William, Unger, Falk, Upadhyay, Sarvagya
We consider a class of two-prover interactive proof systems where each prover returns a single bit to the verifier and the verifier's verdict is a function of the XOR of the two bits received. We...
Exact and Approximate Unitary 2-Designs: Constructions and Applications (2006)
Dankert, Christoph, Cleve, Richard, Emerson, Joseph, Livine, Etera
We consider an extension of the concept of spherical t-designs to the unitary group in order to develop a unified framework for analyzing the resource requirements of randomized quantum algorithms....
New Limits on Fault-Tolerant Quantum Computation (2006)
Buhrman, Harry, Cleve, Richard, Laurent, Monique, Linden, Noah, Schrijver, Alexander, Unger, Falk
We show that quantum circuits cannot be made fault-tolerant against a depolarizing noise level of approximately 45%, thereby improving on a previous bound of 50% (due to Razborov). Our precise...
Nonlocality and communication complexity (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...
Nonlocality and communication complexity (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...
Efficient quantum algorithms for simulating sparse Hamiltonians (2005)
Berry, Dominic W., Ahokas, Graeme, Cleve, Richard, Sanders, Barry C.
We present an efficient quantum algorithm for simulating the evolution of a sparse Hamiltonian H for a given time t in terms of a procedure for computing the matrix entries of H. In particular, when...
Classical and quantum fingerprinting with shared randomness and one-sided error (2005)
Horn, Rolf T., Scott, A. J., Walgate, Jonathan, Cleve, Richard, Lvovsky, A. I., Sanders, Barry C.
Within the simultaneous message passing model of communication complexity, under a public-coin assumption, we derive the minimum achievable worst-case error probability of a classical fingerprinting...
Classical and quantum fingerprinting with shared randomness and one-sided error (2005)
Rolf T, Horn, Scott, Andrew James, Walgate, Jonathan, Cleve, Richard, Lvovski, A. I., Sanders, Barry C.
Within the simultaneous message passing model of communication complexity, under a public-coin assumption, we derive the minimum achievable worst-case error probability of a classical fingerprinting...
Classical and quantum fingerprinting with shared randomness and one-sided error (2005)
Rolf T, Horn, Scott, Andrew James, Walgate, Jonathan, Cleve, Richard, Lvovski, A. I., Sanders, Barry C.
Within the simultaneous message passing model of communication complexity, under a public-coin assumption, we derive the minimum achievable worst-case error probability of a classical fingerprinting...
Classical and quantum fingerprinting with shared randomness and one-sided error (2005)
Rolf T, Horn, Scott, Andrew James, Walgate, Jonathan, Cleve, Richard, Lvovski, A. I., Sanders, Barry C.
Within the simultaneous message passing model of communication complexity, under a public-coin assumption, we derive the minimum achievable worst-case error probability of a classical fingerprinting...
Consequences and Limits of Nonlocal Strategies (2004)
Cleve, Richard, Hoyer, Peter, Toner, Benjamin, Watrous, John
This paper investigates various aspects of the nonlocal effects that can arise when entangled quantum information is shared between two parties. A natural framework for studying nonlocality is that...
Consequences and limits of nonlocal strategies (2004)
Richard Cleve, Peter Høyer, Benjamin Toner, John Watrous
This paper investigates various aspects of the nonlocal effects that can arise when entangled quantum information is shared between two parties. A natural framework for studying nonlocality is that...
Exponential algorithmic speedup by quantum walk (2002)
Childs, Andrew M., Cleve, Richard, Deotto, Enrico, Farhi, Edward, Gutmann, Sam, Spielman, Daniel A.
We construct an oracular (i.e., black box) problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time...
Sharp Quantum versus Classical Query Complexity Separations (2002)
We obtain the strongest separation between quantum and classical query complexity known to date---specifically, we define a black-box problem that requires exponentially many queries in the classical...
A quantum Goldreich-Levin theorem with cryptographic applications (2001)
We investigate the Goldreich-Levin Theorem in the context of quantum information. This result is a reduction from the computational problem of inverting a one-way function to the problem of...
Buhrman, Harry, Cleve, Richard, Watrous, John, De Wolf, Ronald
Classical fingerprinting associates with each string a shorter string (its fingerprint), such that, with high probability, any two distinct strings can be distinguished by comparing their...
Quantum Entanglement and Communication Complexity (2001)
Harry Buhrman, Richard Cleve, Van Dam
Abstract. We consider a variation of the communication complexity scenario, where the parties are supplied with an extra resource: particles in an entangled quantum state. We note that...
Harry Buhrman, Richard Cleve, John Watrous, Ronald De Wolf
Classical fingerprinting associates with each string a shorter string (its fingerprint), such that, with high probability, any two distinct strings can be distinguished by comparing their...
Sharp quantum vs. classical query complexity separations (2001)
We obtain the strongest separation between quantum and classical query complexity known to date|specically, we dene a black-box problem that requires exponentially many queries in the classical...
A Quantum Goldreich-Levin Theorem with Cryptographic Applications (2001)
We investigate the Goldreich-Levin Theorem in the context of quantum information. This result is a reduction from the computational problem of inverting a one-way function to the problem of...
Quantum Entanglement and Communication Complexity (2001)
Harry Buhrman, Harry Buhrman, Richard Cleve, Richard Cleve
See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting: BRICS
Quantum Entanglement and Communication Complexity (2001)
Harry Buhrman, Richard Cleve, Van Dam
Abstract. We consider a variation of the communication complexity scenario, where the parties are supplied with an extra resource: particles in an entangled quantum state. We note that “quantum...
Sharp Quantum vs. Classical Query Complexity Separations (2000)
De Beaudrap, J. Niel, Cleve, Richard, Watrous, John
We obtain the strongest separation between quantum and classical query complexity known to date -- specifically, we define a black-box problem that requires exponentially many queries in the...
Classical simulation of quantum entanglement without local hidden variables (2000)
Massar, Serge, Bacon, Dave, Cerf, Nicolas, Cleve, Richard
Recent work has extended Bell's theorem by quantifying the amount of communication required to simulate entangled quantum systems with classical information. The general scenario is that a bipartite...
Experimental Realization of an Order-Finding Algorithm with an NMR Quantum Computer (2000)
Vandersypen, Lieven M. K., Steffen, Matthias, Breyta, Gregory, Yannoni, Costantino S., Cleve, Richard, Chuang, Isaac L.
We report the realization of a nuclear magnetic resonance (NMR) quantum computer which combines the quantum Fourier transform (QFT) with exponentiated permutations, demonstrating a quantum algorithm...
Fast parallel circuits for the quantum Fourier transform (2000)
We give new bounds on the circuit complexity of the quantum Fourier transform (QFT). We give an upper bound of O(log n + log log (1/epsilon)) on the circuit depth for computing an approximation of...
The query complexity of order-finding (2000)
We consider the problem where is an unknown permutation on f0; 1; : : : ; 2 n
Fast parallel circuits for the quantum Fourier transform (2000)
We give new bounds on the circuit complexity of the quantum Fourier transform (QFT). We give an upper bound of O(log n + log log(1=")) on the circuit depth for computing an approximation of...
Fast parallel circuits for the quantum Fourier transform (2000)
We give new bounds on the circuit complexity of the quantum Fourier transform (QFT). We give an upper bound of O(log n + log log(1=")) on the circuit depth for computing an approximation of...
Quantum Fourier transforms for extracting hidden linear structures in finite fields (2000)
We propose a definition for quantum Fourier transforms in settings where the algebraic structure is that of a finite field, and show that they can be performed efficiently by a quantum computer....
Fast parallel circuits for the quantum Fourier transform (2000)
We give new bounds on the circuit complexity of the quantum Fourier transform (QFT). We give an upper bound of O(logn + log log(1=")) on the circuit depth for computing an approximation of the...
The query complexity of order-finding (1999)
We consider the problem where P is an unknown permutation on {0,1,...,2^n - 1}, y is an element of {0,1,...,2^n - 1}, and the goal is to determine the minimum r > 0 such that P^r(y) = y (where P^r is...
An Introduction to Quantum Complexity Theory (1999)
We give a basic overview of computational complexity, query complexity, and communication complexity, with quantum information incorporated into each of these scenarios. The aim is to provide simple...
The cost of exactly simulating quantum entanglement with classical communication (1999)
Brassard, Gilles, Cleve, Richard, Tapp, Alain
We investigate the amount of communication that must augment classical local hidden variable models in order to simulate the behaviour of entangled quantum systems. We consider the scenario where a...
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...
On quantum algorithms Contribution to Complexity (1999)
Richard Cleve, Artur Ekert, Leah Henderson, Chiara Macchiavello, Michele Mosca
Quantum computers use the quantum interference of different computational paths to enhance correct outcomes and suppress erroneous outcomes of computations. In effect, they follow the same logical...
The Query Complexity of Order-Finding (1999)
We consider the problem where is an unknown permutation on f0; 1; : : : ; 2 n \Gamma 1g, y 0 2 f0; 1; : : : ; 2 n \Gamma 1g, and the goal is to determine the minimum r ? 0 such that r (y 0 ) = y 0 ....
The Cost of Exactly Simulating Quantum Entanglement With Classical Communication (1999)
Gilles Brassard, Richard Cleve
We investigate the amount of communication that must augment classical local hidden variable models in order to simulate the behaviour of entangled quantum systems. We consider the scenario where a...
Bounds for Small-Error and Zero-Error Quantum Algorithms (1999)
Harry Buhrman Richard, Richard Cleve, Ronald De Wolf, Christof Zalka
We present a number of results related to quantum algorithms with small error probability and quantum algorithms that are zero-error. First, we give a tight analysis of the trade-offs between the...
Bounds for Small-Error and Zero-Error Quantum Algorithms (1999)
Harry Buhrman, Richard Cleve, Ronald De Wolf, Christof Zalka
We present a number of results related to quantum algorithms with small error probability and quantum algorithms that are zero-error. First, we give a tight analysis of the trade-offs between the...
The Cost of Exactly Simulating Quantum Entanglement With Classical Communication (1999)
Gilles Brassard, Richard Cleve, Alain Tapp
We investigate the amount of communication that must augment classical local hidden variable models in order to simulate the behaviour of entangled quantum systems. We consider the scenario where a...
Reducing Error Probability in Quantum Algorithms (Extended Abstract) (1999)
Harry Buhrmann, Richard Cleve, Ronald De Wolf, Christof Zalka
) Harry Buhrman CWI Richard Cleve University of Calgary y Ronald de Wolf CWI and U. of Amsterdam z Christof Zalka Los Alamos x April 26, 1999 Abstract We present several results related to quantum...
Bounds for small-error and zero-error quantum algorithms (1999)
Harry Buhrman, Richard Cleve, Ronald De Wolf, Christof Zalka
We present a number of results related to quantum algorithms with small error probability and quantum algorithms that are zero-error. First, we give a tight analysis of the trade-offs between the...
Quantum Lower Bounds by Polynomials (1998)
Beals, Robert, Buhrman, Harry, Cleve, Richard, Mosca, Michele, De Wolf, Ronald
We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0,1}^N in the black-box model. We show that, in the black-box model, the exponential...
Quantum vs. Classical Communication and Computation (1998)
Buhrman, Harry, Cleve, Richard, Wigderson, Avi
We present a simple and general simulation technique that transforms any black-box quantum algorithm (a la Grover's database search algorithm) to a quantum communication protocol for a related...
Quantum entanglement and the communication complexity of the inner product function (1998)
Richard Cleve, Michael Nielsen
Abstract. We consider the communication complexity of the binary inner product function in a variation of the two-party scenario where the parties have an apriorisupply of particles in an entangled...
On interpolating arithmetic read-once formulas with exponentiation (1998)
Nader H. Bshouty, Richard Cleve
A formula is read-once if each variable appears at most once in it. An arithmetic read-once formula is one in which the operations are addition, subtraction, multiplication, and division (and...
Quantum Entanglement and the Communication Complexity of the Inner Product Function (1998)
Richard Cleve, Wim Van Dam, Michael Nielsen, Alain Tapp
. We consider the communication complexity of the binary inner product function in a variation of the two-party scenario where the parties have an apriorisupply of particles in an entangled quantum...
Interpolating Arithmetic Read-Once Formulas in Parallel (1998)
Nader H. Bshouty, Richard Cleve
. A formula is read-once if each variable appears in it at most once. An arithmetic formula is one in which the operations are addition, subtraction, multiplication, and division (and constants are...
Quantum Entanglement and Communication Complexity (1998)
Harry Buhrman Cwi, Harry Buhrman, Richard Cleve
We consider a variation of the multi-party communication complexity scenario where the parties are supplied with an extra resource: particles in an entangled quantum state. We show that, although a...
Quantum vs. Classical Communication and Computation (1998)
Harry Buhrman, Richard Cleve, Avi Wigderson
We present a simple and general simulation technique that transforms any black-box quantum algorithm (a la Grover's database search algorithm) to a quantum communication protocol for a related...
Quantum vs. Classical Communication and Computation (1998)
Harry Buhrman, Richard Cleve, Avi Wigderson
We present a simple and general simulation technique that transforms any black-box quantum algorithm (a la Grover's database search algorithm) to a quantum communication protocol for a related...
Quantum Entanglement and Communication Complexity (1998)
Harry Buhrman, Richard Cleve, Wim Van Dam
We consider a variation of the multi-party communication complexity scenario where the parties are supplied with an extra resource: particles in an entangled quantum state. We show that, although a...
Teleportation as a Quantum Computation (1998)
Gilles Brassard, Samuel L. Braunstein, Richard Cleve
Introduction Among the many exciting new applications of quantum physics in the realm of information processing, we are particularly fond of quantum cryptography, quantum computing and quantum...
Interpolating Arithmetic Read-Once Formulas in Parallel (1998)
Nader H. Bshouty, Richard Cleve
A formula is read-once if each variable appears at most once in it. An arithmetic formula is one in which the operations are addition, subtraction, multiplication, and division (and constants are...
Quantum Lower Bounds by Polynomials (1998)
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald De Wolf
We examine the number T of queries that a quantum network requires to compute several Boolean functions on f0; 1g N in the black-box model. We show that, in the blackbox model, the exponential...
Quantum Entanglement and the Communication Complexity of the Inner Product Function (1998)
Richard Cleve, Wim Van Dam, Michael Nielsen, Alain Tapp
. We consider the communication complexity of the binary inner product function in a variation of the two-party scenario where the parties have an a priori supply of particles in an entangled quantum...
Quantum lower bounds by polynomials (1998)
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca
We examine the numberTof queries that a quantum network requires to compute several Boolean functions on f0;1gNin the black-box model. We show that, in the blackbox model, the exponential quantum...
Information-theoretic interpretation of quantum error-correcting codes (1997)
Cerf, Nicolas J., Cleve, Richard
Quantum error-correcting codes are analyzed from an information-theoretic perspective centered on quantum conditional and mutual entropies. This approach parallels the description of classical error...
Quantum Entanglement and the Communication Complexity of the Inner Product Function (1997)
Cleve, Richard, Van Dam, Wim, Nielsen, Michael, Tapp, Alain
We consider the communication complexity of the binary inner product function in a variation of the two-party scenario where the parties have an a priori supply of particles in an entangled quantum...
Quantum Algorithms Revisited (1997)
Cleve, Richard, Ekert, Artur, Macchiavello, Chiara, Mosca, Michele
Quantum computers use the quantum interference of different computational paths to enhance correct outcomes and suppress erroneous outcomes of computations. A common pattern underpinning quantum...
Quantum Entanglement and Communication Complexity (1997)
Buhrman, Harry, Cleve, Richard, Van Dam, Wim
We consider a variation of the multi-party communication complexity scenario where the parties are supplied with an extra resource: particles in an entangled quantum state. We show that, although a...
Substituting Quantum Entanglement for Communication (1997)
Cleve, Richard, Buhrman, Harry
We show that quantum entanglement can be used as a substitute for communication when the goal is to compute a function whose input data is distributed among remote parties. Specifically, we show...
Information-theoretic interpretation of quantum error-correcting codes (1997)
Cerf, Nicolas J., Cleve, Richard
Quantum error-correcting codes are analyzed from an information-theoretic perspective centered on quantum conditional and mutual entropies. This approach parallels the description of classical error...
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...
Quantum Stabilizer Codes and Classical Linear Codes (1996)
We show that within any quantum stabilizer code there lurks a classical binary linear code with similar error-correcting capabilities, thereby demonstrating new connections between quantum codes and...
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...
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...
Schumacher's quantum data compression as a quantum computation (1996)
Cleve, Richard, DiVincenzo, David P.
An explicit algorithm for performing Schumacher's noiseless compression of quantum bits is given. This algorithm is based on a combinatorial expression for a particular bijection among binary...
Oracles and queries that are sufficient for exact learning (1996)
Nader H. Bshouty, Richard Cleve, Sampath Kannan, Christino Tamon
We show that the class of all circuits is exactly learnable in randomized expected polynomial time using weak subset and weak superset queries. This is a consequence of the following result which we...
Oracles and Queries that are Sufficient for Exact Learning (1996)
Nader Bshouty Richard, Richard Cleve, Sampath Kannan, Christino Tamon
We show that the class of all circuits is exactly learnable in randomized expected polynomial time using weak subset and weak superset queries. This is a consequence of the following result which we...
Oracles and Queries that are Sufficient for Exact Learning (1996)
Nader H. Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan, Christino Tamon
We show that the class of all circuits is exactly learnable in randomized expected polynomial time using subset and superset queries. This is a consequence of the following result which we consider...
Quantum Stabilizer Codes and Classical Linear Codes (1996)
We show that within any quantum stabilizer code there lurks a classical binary linear code with similar error-correcting capabilities, thereby demonstrating new connections between quantum codes and...
Schumacher's Quantum Data Compression as a Quantum Computation (1996)
Richard Cleve, David P. Divincenzo
An explicit algorithm for performing Schumacher's noiseless compression of quantum bits is given. This algorithm is based on a combinatorial expression for a particular bijection among binary...
Schumacher's Quantum Data Compression as a Quantum Computation (1996)
Richard Cleve, David P. Divincenzo
An explicit algorithm for performing Schumacher's noiseless compression of quantum bits is given. This algorithm is based on a combinatorial expression for a particular bijection among binary...
INTERPOLATING ARITHMETIC READ-ONCE FORMULAS IN PARALLEL (1995)
Bshouty, Nader H., Cleve, Richard
A formula is read-once if each variable appears at most once in it. An artithmetic read-once formula is one in which the operations are addition, subtraction, multiplication, and division (and...
INTERPOLATING ARITHMETIC READ-ONCE FORMULAS IN PARALLEL (1995)
Bshouty, Nader H., Cleve, Richard
A formula is read-once if each variable appears at most once in it. An artithmetic read-once formula is one in which the operations are addition, subtraction, multiplication, and division (and...
INTERPOLATING ARITHMETIC READ-ONCE FORMULAS IN PARALLEL (1995)
Bshouty, Nader H., Cleve, Richard
A formula is read-once if each variable appears at most once in it. An artithmetic read-once formula is one in which the operations are addition, subtraction, multiplication, and division (and...
Adriano Barenco, David P. Divincenzo, Tycho Sleator, Charles H. Bennett, Norman Margolus, John Smolin, ...
We show that a set of gates that consists of all one-bit quantum gates (U(2)) and the two-bit exclusive-or gate (that maps Boolean values (x, y)to(x, x⊕y)) is universal in the sense that all...
Elementary Gates for Quantum Computation (1995)
Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, ...
We show that a set of gates that consists of all one-bit quantum gates (U(2)) and the two-bit exclusive-or gate (that maps Boolean values (x; y) to (x; x \Phi y)) is universal in the sense that all...
Elementary Gates for Quantum Computation (1995)
Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, ...
We show that a set of gates that consists of all one-bit quantum gates (U(2)) and the two-bit exclusive-or gate (that maps Boolean values (x; y) to (x; x \Phi y)) is universal in the sense that all...
Elementary Gates for Quantum Computation (1995)
Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. Divincenzo, Norman Margolus, ...
We show that a set of gates that consists of all one-bit quantum gates (U(2)) and the two-bit exclusive-or gate (that maps Boolean values (x; y) to (x; x \Phi y)) is universal in the sense that all...
Elementary Gates for Quantum Computation (1995)
Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. Divincenzo, Norman Margolus, ...
We show that a set of gates that consists of all one-bit quantum gates (U(2)) and the two-bit exclusive-or gate (that maps Boolean values (x; y) to (x; x \Phi y)) is universal in the sense that all...
Elementary Gates for Quantum Computation (1995)
Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. Divincenzo, Norman Margolus, Peter Shor, ...
We show that a set of gates that consists of all one-bit quantum gates (U(2)) and the two-bit exclusive-or gate (that maps Boolean values (x; y) to (x; x \Phi y)) is universal in the sense that all...
ORACLES AND QUERIES THAT ARE SUFFICIENT FOR EXACT LEARNING (1994)
Bshouty, Nader H., Cleve, Richard, Tamon, Christino, Kannan, Sampath
We show that the class of all circuits is exactly learnable in (randomized) expected polynomial-time using subset and superset queries. Subset and superset queries are a generalization of equivalence...
ORACLES AND QUERIES THAT ARE SUFFICIENT FOR EXACT LEARNING (1994)
Bshouty, Nader H., Cleve, Richard, Tamon, Christino, Kannan, Sampath
We show that the class of all circuits is exactly learnable in (randomized) expected polynomial-time using subset and superset queries. Subset and superset queries are a generalization of equivalence...
ORACLES AND QUERIES THAT ARE SUFFICIENT FOR EXACT LEARNING (1994)
Bshouty, Nader H., Cleve, Richard, Tamon, Christino, Kannan, Sampath
We show that the class of all circuits is exactly learnable in (randomized) expected polynomial-time using subset and superset queries. Subset and superset queries are a generalization of equivalence...
Oracles and Queries that are Sufficient for Exact Learning (1994)
Nader H. Bshouty, Richard Cleve, Ricard Gavaldà, Sampath Kannan, Christino Tamon
We show that the class of all circuits is exactly learnable in randomized expected polynomial time using weak subset and weak superset queries. This is a consequence of the following result which we...
SIZE-DEPTH TRADEOFFS FOR ALGEBRAIC FORMULAE (1992)
Eberly, Wayne, Cleve, Richard, Bshouty, Nader H.
We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed $ epsilon~>~O$, any algebraic formula of size \s+1Ss-1 can be converted into an...
SIZE-DEPTH TRADEOFFS FOR ALGEBRAIC FORMULAE (1992)
Eberly, Wayne, Cleve, Richard, Bshouty, Nader H.
We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed $ epsilon~>~O$, any algebraic formula of size \s+1Ss-1 can be converted into an...
SIZE-DEPTH TRADEOFFS FOR ALGEBRAIC FORMULAE (1992)
Eberly, Wayne, Cleve, Richard, Bshouty, Nader H.
We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed $ epsilon~>~O$, any algebraic formula of size \s+1Ss-1 can be converted into an...
SIZE-DEPTH TRADEOFFS FOR ALGEBRAIC FORMULAE (1992)
Eberly, Wayne, Cleve, Richard, Bshouty, Nader H.
We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed $ epsilon~>~O$, any algebraic formula of size \s+1Ss-1 can be converted into an...
SIZE-DEPTH TRADEOFFS FOR ALGEBRAIC FORMULAE (1992)
Eberly, Wayne, Cleve, Richard, Bshouty, Nader H.
We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed $ epsilon~>~O$, any algebraic formula of size \s+1Ss-1 can be converted into an...
SIZE-DEPTH TRADEOFFS FOR ALGEBRAIC FORMULAE (1992)
Eberly, Wayne, Cleve, Richard, Bshouty, Nader H.
We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed $ epsilon~>~O$, any algebraic formula of size \s+1Ss-1 can be converted into an...
Size-Depth Tradeoffs for Algebraic Formulae (1991)
Nader H. Bshouty, Richard Cleve
y Abstract. Some tradeos between the size and depth of algebraic formulas are shown. In particular, it is shown that, for any xed > 0, any algebraic formula of size S can be converted into an...
Size-Depth Tradeoffs for Algebraic Formulae (1991)
Nader H. Bshouty, Richard Cleve, Wayne Eberly
We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed ffl ? 0, any algebraic formula of size S can be converted into an equivalent...
Die Verwendung künstl. radioaktiver Stoffe in der Zahnheilkunde und ihren Grenzgebieten. (1950)
Hamburg, Med. F., Diss. v. 9. Nov. 1950 (Nicht f. d. Aust.).
Quantum Lower Bounds by Polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald De Wolf
We examine the number T of queries that a quantum network requires to compute several Boolean functions on f0; 1g N in the black-box model. We show that, in the blackbox model, the exponential...
Quantum Lower Bounds by Polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald De Wolf
We examine the number of queries to input variables that a quantum algorithm requires to compute Boolean functions on in the black-box model. We show that the exponential quantum speed-up obtained...
A Quantum Goldreich-Levin Theorem with Cryptographic Applications
We investigate the Goldreich-Levin Theorem in the context of quantum information. This result is a reduction from the problem of inverting a one-way function to the problem of predicting a particular...
Exponential Algorithmic Speedup by a Quantum Walk
Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, Daniel A. Spielman
We construct a black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time...