Principal Investigator: Dr Oded Regev
The Project
| Our group in Tel Aviv University is
involved in several of the activities in QAP, and in particular the
theory subproject. We are also heading the "Algorithms and Complexity"
workpackage inside the theory subproject. In joint work with the partners UPS and CWI [2], we studied the simultaneous message passing model of communication complexity, and exhibited the first problem where prior entanglement leads to exponentially more efficient communication, compared to the situation without prior entanglement. This demonstrated for the first time that shared quantum entanglement is an extremely powerful resource, even if communication between parties is limited to be classical. We also described a problem where having shared randomness is exponentially more powerful than not having it, even if quantum communication is allowed. In recent work presented in the yearly QIP07 workshop [3] we introduced the notion of a quantum expander. We showed that under certain conditions classical expander constructions generalize to the quantum setting, and in particular so does the Lubotzky, Philips and Sarnak construction of Ramanujan expanders from Cayley graphs of the group PGL. We showed that this definition is exactly what is needed for characterizing the complexity of estimating quantum entropies, and we plan to investigate further applications of this exciting notion. |
 |
In joint work with CWI [4] we demonstrated that Alice and Bob can classically
simulate any quantum correlations by using only two bits of communication. All
previous protocols for exact simulation required the communication to grow to
infinity with the dimension. Our protocol and analysis were based on a power
series method, resembling Krivine's bound on Grothendieck's constant, and on the
computation of volumes of spherical tetrahedra.
In another joint work with CWI [1] we introduced a version of the Bonami-Beckner
hypercontractive inequality for matrix-valued functions on the Boolean cube. We
also presented a number of applications of this. In particular, we analyze maps
that encode n classical bits into m qubits, in such a way that each set of k
bits can be recovered with some probability by an appropriate measurement on the
quantum encoding; we show that if m<0.7n, then the success probability is
exponentially small in k. This implies strong direct product theorems for the
one-way quantum communication complexity of Disjointness and other problems.
List of Publications
QAP
[1] A. Ben-Aroya, O. Regev and R. de Wolf, A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing, accepted for publication in Proc.FOCS'08 quant-ph/0705.3806
A. Retzker, E. Solano and B. Reznik, Tavis-Cummings model and collective multi-qubit entanglement in trapped ions, submitted to Phys. Rev. A quant-ph/0605048
T. Ravon and L. Vaidman, The Three-Box Paradox Revisited, submitted to J. Phys. A quant-ph/0606067
D. Aharonov, D. Gottesman, J. Kempe, The power of quantum systems on the line, submitted to FOCS
J. Kempe, H. Kobayashi, K. Matsumoto et al., On the power of entangled provers: Immunizing games against entanglement, submitted to FOCS
O. Regev, B. Toner, Simulating Quantum Correlations with Finite Communication, submitted to FOCS
L. Vaidman, Impossibility of the counterfactual computation for all possible outcomes, Phys. Rev. Lett. 98 160403 (2007) quant-ph/0610174
L. Vaidman, Backward Evolving Quantum States, submitted to J. Phys. A quant-ph/0606208
A. Ben-Aroya, O. Regev, R. de Wolf, A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing, submitted to FOCS
N. Aharon, S. Machnes, B. Reznik, et al., Continuous input nonlocal games (2007) arXiv:0706.2159
N. Aharon, L. Vaidman, Can quantum mechanics help to win games? (2007) arXiv:0710.1721
J. Kempe, O. Regev, B. Toner, The Unique Games Conjecture with Entangled Provers is False (2007) arXiv:0710.0655
N. Aharon, S. Machnes, B. Reznik et al, Continuous input nonlocal games, accepted for publication in Natural Computation quant-ph/0706.2159
Y. Aharonov, S. Popescu, J. Tollaksen et al, Multiple-time states and multiple-time measurements in quantum mechanics, submitted to Phys. Rev A quant-ph/0712.0320
N. Aharon and L. Vaidman, Quantum advantages in classically defined tasks, Phys. Rev. A 052310 (2008) quant-ph/0710.1721
Y. Aharonov and L. Vaidman, The Two - State Vector Formalism: An Updated Review, Lecture Notes Physics 734 399-447 (2008) quant-ph/0706.1347
D. Gavinsky, J. Kempe, I. Kerenidis et al, Exponential separations for one-way quantum communication complexity, with applications to cryptography, accepted for publication in SIAM. J. on Computing quant-ph/0611209
J. Kempe, H. Kobayashi, K. Matsumoto et al, Using Entanglement in Quantum Multi-Prover Interactive Proofs, Proc. 23rd CCC'08 211-222 (2008) quant-ph/0711.3715
J. Kempe, H. Kobayashi, K. Matsumoto et al, Entangled games are hard to approximate, accepted for publication in Proc.FOCS'08 quant-ph/0704.2903
J. Kempe, O. Regev and B. Toner, Unique Games with Entangled Provers are Easy, accepted for publication in Proc.FOCS'08 quant-ph/0710.0655
J. Kempe, O. Regev, F. Unger, and R. de Wolf, Upper Bounds on the Noise Threshold for Fault-tolerant Quantum Computing, accepted for publication in Proc. 35th ICALP'08 quant-ph/0802.1464
S. Marcovitch, Y. Aharonov, T. Kaufferr et al, Combined Electric and Magnetic Aharonov-Bohm Effects, Am. J. Phys 1141 (2007) quant-ph/0709.1592
A. Rapaport and A. Ta-Shma, On the power of quantum, one round, two prover interactive proof systems, quant-ph (2007) quant-ph/0707.1136
L. Vaidman, Protective Measurements, accepted for publication in Phys. Rev. A quant-ph/0801.2761
L. Vaidman, The Elitzur-Vaidman Interaction-Free Measurements, accepted for publication in Quant. Inf. Comp quant-ph/0801.2777
Related work
[2] D. Gavinsky, J. Kempe, O. Regev, and R. de Wolf, Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity, STOC'06 594-603 (2006). quant-ph/0511013.
[3] A. Ben-Aroya and A. Ta-Shma, Quantum expanders and the quantum entropy difference problem, quant-ph/0702129
[4] O. Regev and B. Toner, Simulating Quantum Correlations with Finite Communication, submitted
D. Gavinsky, J. Kempe, O. Regev and R. de Wolf, Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity, accepted for publication in STOC quant-ph/0511013
L. Vaidman, N. Erez and A. Retzker, Another Look at Quantum Teleportation, Int. J. Quan. Inf. 4 197 (2006) quant-ph/0507051
S. Marcovitch, B. Reznik and L. Vaidman, Quantum Mechanical Realization of a "PR-Box", submitted to Phys. Rev. A quant-ph/0601122
A. Ben-Aroya, O. Schwartz and A. Ta-Shma, An Explicit Construction of Quantum Expanders (2007) arXiv:0709.0911
A. Botero and B. Reznik, Scaling and universality of multipartite entanglement at criticality (2007) arXiv:0708.3391
S. Marcovitch, B. Reznik, Is Communication Complexity Physical? (2007) arXiv:0709.1602
D. Aharonov, W. van Dam, J. Kempe et al, Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation, accepted for publication in SIAM Review quant-ph/0405098
A. Ben-Aroya, O. Schwartz, and A. Ta-Shma, Quantum Expanders: Motivation and Constructions, CCC'08 (2007) quant-ph/0702129
L. Eldar and O. Regev, On quantum constraint satisfaction problems, Proc. ICALP'08 (2008)
J. Kupferman and B. Reznik, Entanglement and the Speed of Evolution in Mixed States (2008) quant-ph/0806.2456
S. Marcovitch and B. Reznik, Implications of communication complexity in multipartite systems, Phys. Rev. A 032120 (2008)
O. Regev and L. Schiff, Impossibility of a Grover speed-up with a faulty oracle, Proc. ICALP'08 (2008)
L. Vaidman, Quantum mechanics - Evolution stopped in its tracks, Nature 137-138 (2008)