Adaptive versus non-adaptive strategies for quantum channel discrimination (2009)
Harrow, Aram W., Hassidim, Avinatan, Leung, Debbie W., Watrous, John
We provide a simple example that illustrates the advantage of adaptive over non-adaptive strategies for quantum channel discrimination. In particular, we give a pair of entanglement-breaking channels...
Quantum algorithms for testing properties of distributions (2009)
Bravyi, Sergey, Harrow, Aram W., Hassidim, Avinatan
Suppose one has access to oracles generating samples from two unknown probability distributions P and Q on some N-element set. How many samples does one need to test whether the two distributions are...
Quantum algorithm for solving linear systems of equations (2008)
Harrow, Aram W., Hassidim, Avinatan, Lloyd, Seth
Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix A and and an vector b, find a vector x such that Ax=b....
Quantum Multi Prover Interactive Proofs with Communicating Provers (2008)
Ben-Or, Michael, Hassidim, Avinatan, Pilpel, Haran
Multi Prover Interactive Proof systems (MIPs)were first presented in a cryptographic context, but ever since they were used in various fields. Understanding the power of MIPs in the quantum context...
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...
Quantum Search in an Ordered List via Adaptive Learning (2007)
Ben-Or, M., Hassidim, Avinatan
We use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants: 1. Each comparison can be erroneous with some probability $1 - p$. 2. At each stage $k$...
No nonlocal box is universal (2007)
Dupuis, Frédéric, Gisin, Nicolas, Hassidim, Avinatan, Méthot, André Allan, Pilpel, Haran
We show that standard nonlocal boxes, also known as Popescu-Rohrlich machines, are not sufficient to simulate any nonlocal correlations that do not allow signalling. This was known in the...