Akadēmiskais centrsAlgorithms for Quantum Computing
[2] F. Magniez, A. Nayak, J. Roland, M. Santha. Search via quantum walk. SIAM Journal on Computing, 40(1):142-164, 2011.
[3] H. Krovi, F. Magniez, M. Ozols, J. Roland. Finding is as easy as detecting for quantum walks. Proceedings of 37st International Colloquium on Automata, Languages and Programming (ICALP), Springer LNCS 6198:540-551, 2010.
[4] S. Jeffrey, R. Kothari, F. Magniez, “Nested quantum walks with quantum data structures”, In Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, pp. 1474-1485 (2013).
[5] A. Ambainis, A. Bačkurs, N. Nahimovs, R. Ozols, A. Rivosh: “Search by quantum walks on two-dimensional grid without amplitude amplification”, Proceedings of TQC’2012, to appear.
[6] F. Magniez, A. Nayak, P. Richter, M. Santha, "On the hitting times of quantum versus random walks", Algorithmica, Vol. 63(1), pp. 91-106 (2012)
[7] A. Belovs, A. Childs, S. Jeffery, R. Kothari, F. Magniez. “Time-Efficient Quantum Walks for 3-Distinctness." 39th International Colloqium on Automata, Languages and Programming (ICALP’2013), vol.1, pp. 105-122.
[8] A. Ambainis, K. Balodis, J. Iraids, R. Ozols, J. Smotrovs. “Parameterized Quantum Query Complexity of Graph Collision.” ICALP workshop on Quantum and Classical Complexity, pp. 5-16, 2013.
[9] T. Lee, F. Magniez, M. Santha, "A learning graph based quantum query algorithm for finding constant-size subgraphs", Chicago Journal of Theoretical Computer Science, Vol. 2012, Article 10, pp. 1-21, 2012.
[10] T. Lee, F. Magniez, M. Santha, “Improved quantum query algorithms for triangle finding and associativity testing”, in Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1486-1502, 2013. New Ideas for Quantum Algorithms [1] A. Ambainis. Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations.
[2] A. Montanaro. The quantum query complexity of learning multilinear polynomials.
[3] A. Belovs. Span-program-based quantum algorithm for the rank problem.
[4] A. Belovs, T. Lee. Quantum Algorithm for k-distinctness with Prior Knowledge on the Input.
[5] G. Ivanyos, L. Sanselme, M. Santha. An efficient quantum algorithm for the hidden subgroup problem in nil-2 group. Algorithmica, 62:1-2, 480-498, 2012.
[6] T. Lee, F. Magniez, M. Santha, “Improved quantum query algorithms for triangle finding and associativity testing”, to appear in the Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, 2013
[7] A. Belovs, B. W. Reichardt, “Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection”, Proceedings of ESA’2012, pp. 193-204.
[8] T. Lee, F. Magniez, M. Santha, "A learning graph based quantum query algorithm for finding constant-size subgraphs", arXiv:1109.5135 (2011)
[9] A. Belovs, “Learning-Graph-Based Quantum Algorithm for k-distinctness”, Proceedings of FOCS’2012, to appear.
[10] A. Belovs, “Span programs for functions with constant-sized 1-certificates: extended abstract”, Proceedings of STOC’2012, pp. 77-84.
[11] A. Ambainis. “Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations”. Proceedings of STACS’2012, pp. 636-647.
[12] A. Ambainis. Superlinear advantage for exact quantum algorithms. ACM Symposium on the Theory of Computing (STOC’2013), pp. 891-900.
[13] A. Ta-Shma. Inverting well conditioned matrices in Quantum Logspace. ACM Symposium on the Theory of Computing (STOC’2013), pp. 881-890.
[14] A. Ambainis, A. Montanaro, Quantum algorithms for search with wildcards and combinatorial group testing. Quantum Information and Computation, accepted for publication. arxiv:1210.1148.
[15] T. Decker, G. Ivanyos, M. Santha, P. Wocjan, “Hidden symmetry subgroup problem”. to appear in SIAM Journal on Computing, 2013 Structure of Quantum Algorithms [1] Aram W. Harrow, Ashley Montanaro, Anthony J. Short. Limitations on quantum dimensionality reduction. Proceedings of ICALP 2011, Springer LNCS, volume 6755, pp. 86-97.
[2] Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland. Symmetry-Assisted Adversaries for Quantum State Generation. Proceedings of the IEEE Conference on Computational Complexity. 2011, pp. 167-177
[3] R. Beals, S. Brierley, O. Gray, A. Harrow, S. Kutin, N. Linden, D. Shepherd, M. Stather, “Efficient Distributed Quantum Computing”, arXiv:1207.2307
[4] (*) A. Ambainis and R. de Wolf, “How Low Can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?”, IEEE Conference on Computational Complexity (CCC’2013), pp. 179-184.
[5] A. Belovs, R. Špalek, “Adversary Lower Bound for the k-sum Problem”, arxiv:1206.6528.
[6] N. de Beaudrap, “A linearized stabilizer formalism for systems of finite dimension”, Quantum Information and Computation 13 (p. 73), 2013.
[7] M. J. Bremner, R. Jozsa, D. J. Shepherd, “Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy,” Proc. R. Soc. A vol. 467 no. 2126 pp. 459-472 (2011)
[8] D.M. Appleby, I. Bengtsson, S. Brierley, D. Gross, J.-A. Larsson, “The monomial representations of the Clifford group,” arXiv:1102.1268
[9] A. Belovs, A. Rosmanis. On the Power of Non-Adaptive Learning Graphs. IEEE Conference on Computational Complexity (CCC’2013), pp. 44-55.
[10] R. Jozsa, M. Van den Nest “Classical simulation complexity of extended Clifford circuits” arXiv:1305.6190 (to appear in Quantum Information and Computation).
[11] A. Montanaro . “Almost all decision trees do not allow significant quantum speedup”. arXiv:1209.4781.
[12] A. Montanaro “A composition theorem for decision tree complexity” arXiv:1302.4207
[13] A. Yakaryilmaz, A. C. Cem Say: Proving the Power of Postselection. Fundamenta Informaticae, 123(1): 107-134 (2013).
[14] A. Ambainis, A. Bačkurs, J.Smotrovs, R. de Wolf. Optimal quantum query bounds for almost all Boolean functions. Symposium on Theoretical Aspects of Computer Science (STACS’2013), pp. 446-453.
[15] A. Belovs, R. Špalek. Adversary lower bound for the k-sum problem. 4th Conference on Innovations in Theoretical Computer Science (ITCS’2013), pp. 323-328.
Computer Science Perspectives in Quantum Communication
Quantum Games
[1] G. Scarpa, S. Severini. Kochen-Specker Sets and the Rank-1 Quantum Chromatic Number.
[2] J. Briët, H. Burhman, B. Toner. A generalized Grothendieck inequality and entangled XOR games. Communications in Mathematical Physics, Vol. 305 (3), pp. 827-843 (2011).
[3] J. Briët, T. Vidick. Explicit lower and upper bounds on the entangled value of multiplayer XOR games.Communications in Mathematical Physics, Volume 321, Issue 1, pp 181-207 (2013)
[4] T. Vertesi, N. Brunner. Disproving the Peres conjecture: nonlocality does not imply entanglement distillability.
[5] D. Cavalcanti, N. Brunner, P. Skrzypczyk, A. Salles, V. Scarani. “Large violations of Bell inequalities using both particle and wave measurements”. Phys. Rev. A, Vol. 84(2), 022105 (2011).
[6] Y.-C. Liang, T. Vertesi, N. Brunner. “Semi-device-independent bounds on entanglement”. Phys. Rev. A, Vol. 83(2), 022108 (2011).
[7] P. Janotta, C. Gogolin, J. Barrett, N. Brunner. “Limits on non-local correlations from the structure of the local state space”. New J. Phys., Vol. 13, 063024 (2011).
[8] T. Lawson, N. Linden, S. Popescu, “Biased nonlocal quantum games”.
[9] R. Gallego, N. Brunner, Ch. Hadley, A. Acin. “Device-independent tests of classical and quantum dimensions”. Phys. Rev. Lett., Vol. 105(23), 230501 (2010).
[10] N. Brunner, D. Cavalcanti, A. Salles, P. Skrzypczyk. “Bound non-locality and activation”. Phys. Rev. Lett., Vol. 106(2), 020402 (2011).
[11] J. Briët, H. Buhrman and D. Gijswijt, "Violating the Shannon capacity of metric graphs with entanglement", arXiv:1207.1779. To appear in Proceedings of the National Academy of Sciences (2012)
[12] A. Ambainis, A. Backurs, K. Balodis, D. Kravcenko, R. Ozols, J. Smotrovs, M. Virza: Quantum Strategies Are Better Than Classical in Almost Any XOR Game. Proceedings of ICALP’2012, pp. 25-37.
[13] J. Barrett, S. Pironio, J.-D. Bancal, N. Gisin, The definition of multipartite nonlocality, arXiv:1112.2626
[14] (*) A. Acín, M. L. Almeida, R. Augusiak, N. Brunner, “Guess your neighbour's input: no quantum advantage but an advantage for quantum theory,” arXiv:1205.3076
[15] (*) J.-D. Bancal, S. Pironio, A. Acin, Y.–C. Liang, V, Scarani, N, Gisin, Quantum nonlocality based on finite-speed causal influences leads to superluminal signaling, arXiv:1110.3795.
[16] C. Branciard, D. Rosset, N. Gisin, S. Pironio, Bilocal versus non-bilocal correlations in entanglement swapping experiments, Phys. Rev. A 85, 032119 (2012).
[17] N. Brunner, T. Vertesi, “Persistency of multipartite quantum correlations,” arXiv:1207.3986
[18] L. Mancinska, G. Scarpa and S. Severini, "A Generalization of Kochen-Specker Sets Relates Quantum Coloring to Entanglement-Assisted Channel Capacity", arXiv:1207.1111
[19] G. Scarpa and S. Severini, "Kochen-Specker Sets and the Rank-1 Quantum Chromatic Number", IEEE Transactions on Information Theory, vol.58, no.4, pp.2524-2529, April 2012.
[20] J. Cadney, N. Linden, “Measurement entropy in Generalized Non-Signalling Theory cannot detect bipartite non-locality,” arXiv:1207.3276
[21] (*) D. Cavalcanti, A. Acin, N. Brunner, T. Vertesi, “Super-activation of quantum nonlocality and teleportation,” arXiv:1207.5485
[22] I. Kerenidis, S. Zhang, “A quantum protocol for sampling correlated equilibria unconditionally and without a mediator”, Theory of Quantum Computation, Communication and Cryptography, 2012
[23] M. Pawlowski, A. Winter, “Hyperbits: the information quasiparticles,” Phys. Rev. A 85, 022331 (2012)
[24] J. Briët and T. Vidick, "Explicit lower and upper bounds on the entangled value of multiplayer XOR games", arXiv:1108.5647, presented at QIP 2012. To appear in Communications in Mathematical Physics (2012).
[25] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, S. Wehner “Bell nonlocality”, arXiv:1303.2849 submitted by invitation to Review of Modern Physics
[26] A. Chailloux, I. Kerenidis, J. Sikora, “Oblivious transfer, the CHSH game, and quantum encodings”, arXiv:1304.0983, 2013
[27] C. Branciard, N. Brunner, H. Buhrman, R. Cleve, N. Gisin, S. Portmann, D. Rosset, M. Szegedy, “Classical simulation of entanglement swapping with bounded communication”, Phys. Rev. Lett. 109, 100401 (2012).
[28] F Hirsch, M Túlio Quintino, J Bowles, N Brunner, “Genuine hidden quantum nonlocality” arXiv:1307.4404
[29] M. Navascues, “The Physics of crypto-nonlocality”, arXiv:1303.5124
[30] J. Bohr Brask, R. Chaves, N. Brunner, “Testing nonlocality of single-photon entanglement without a shared reference frame”, Phys. Rev. A 88, 012111 (2013)
[31] N. Brunner, D. Cavalcanti, “Quantum steering with bound entanglement”, arXiv:1210.1556
[32] N. Brunner, N. Linden “Bell nonlocality and Bayesian game theory”, Nature Communications 4, 2057 (2013)
[33] A. Ambainis, J. Iraids, D. Kravčenko, M. Virza. “Advantage of Quantum Strategies in Random Symmetric XOR Games”, Mathematical and Engineering Methods in Computer Science (MEMICS’2012), pp. 57-68.
[34] A. Ambainis, A. Bačkurs, K. Balodis, J. Smotrovs, A. Škuškovniks, M. Virza “Worst-case analysis of non-local games”, Symposium on Theory and Practice of Computer Science (SOFSEM’2013), pp. 121-132.
[35] A. Ambainis, D. Kravchenko, N. Nahimov, A. Rivosh, M. Virza “On symmetric nonlocal games”, Theoretical Computer Science, 494: 36-48 (2013).
[36] A. Ambainis, J. Iraids “Provable Advantage for Quantum Strategies in Random Symmetric XOR Games”, Conference on Theory of Quantum Computing (TQC’2013), accepted for publication in post-proceedings.
[37] J. Briët, H. Buhrman, T. Lee, T. Vidick, “Multipartite entanglement in XOR games”. Quantum Information & Computation 13(3-4): 334-360 (2013)
Quantum Games and Interactive Proofs
[1] J. Kempe and T. Vidick (2011) Parallel repetition of entangled games. In Proc. 43rd ACM STOC, pages 353-362.
[2] J. Kempe, O. Regev and B.Toner (2010) Unique Games with Entangled Provers are Easy. SIAM J. Comp., 39(7):3207-3229.
[3] R. Jain, I. Kerenidis, G. Kuperberg, M. Santha, O. Sattah, S. Zhang, “On the power of a unique quantum witness”, Theory of Computing, vol. 8, pp. 375-400, 2012.
[4] A. Ambainis. “On physical problems that are slightly more difficult than QMA”, Arxiv preprint, to appear.
Quantum Games and Communication Complexity
[1] H. Buhrman, O. Regev, G. Scarpa, R. de Wolf. "Near-Optimal and Explicit Bell Inequality Violations". Proceedings of the IEEE Conference on Computational Complexity, 2011, pp. 157-166; Theory of Computing 8(1): 623-645 (2012)
[2] R. Augusiak, J. Stasińska, C. Hadley, J. K. Korbicz, M. Lewenstein, A. Acín. “Bell inequalities with no quantum violation and unextendible product bases”. Phys. Rev. Lett. 107, 070401 (2011).
[3] L. Aolita, R. Gallego, A. Acín, A. Chiuri, G. Vallone, P. Mataloni, A. Cabello. Fully nonlocal quantum correlations.
[4] R. Gallego, L.E. Würflinger, A. Acín, M. Navascués. Quantum correlations require multipartite information principles.
[5] M. Kaplan, I. Kerenidis, S. Laplante and J. Roland (2011) "Non-Local Box Complexity and Secure Function Evaluation". Quantum Information and Computation, 11(1):40-69.
[6] J. Degorre, M. Kaplan, S. Laplante and J. Roland (2011) "The communication complexity of non-signaling distributions". Quantum Information and Computation, 11(8):649-676.
[7] M. Pawlowski, A. Winter. From Qubits to Hyperbits.
[8] N. Brunner, C. Branciard, N. Gisin, D. Rosset. Communication cost of simulating entanglement swapping.
[9] (*) S. Laplante, V. Lerays, and J. Roland. Classical and quantum partition bound and detector inefficiency. In 39th International Colloquium on Automata, Languages and Programming (ICALP'12), volume 7391 of Lecture Notes in Computer Science, pages 617-628. Springer, 2012. Quant-ph/1203.4155.
[10] (*) I. Kerenidis, S. Laplante, V. Lerays, J. Roland, and D. Xiao. Lower bounds on information complexity via zero-communication protocols and applications. In 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'12), pp. 500-509, 2012
[11] A. Montanaro, “A new exponential separation between quantum and classical one-way communication complexity,” Quantum Information & Computation, vol. 11 no. 7&8, pp. 574-591 (2011)
[12] (*) G. Ivanyos, H. Klauck, T. Lee, M. Santha, R. de Wolf, “New bounds on the classical and quantum communication complexity of some graph properties”, In 32nd Foundations of Software Technology and Theoretical Computer Science (FSTTCS'12), pp.148-159 (2012).
[13] (*) C. Branciard, N. Brunner, H. Buhrman, R. Cleve, N. Gisin, S. Portmann, D.Rosset, M. Szegedy, “Classical simulation of entanglement swapping with bounded communication,” Phys. Rev. Lett. 109, 100401 (2012)
[14] H. Klauck and R. de Wolf, "Fooling One-Sided Quantum Protocols", In 30th Annual Symposium on Theoretical Aspects of Computer Science (STACS 13), pp.424-433, (2013)
[15] (*) R. Gallego, L. E. Würflinger, A. Acín, M. Navascués, “Operational framework for nonlocality”, Phys. Rev. Lett. 109, 070401 (2012).
[16] (*) R. Augusiak, T. Fritz, Ma. Kotowski, Mi. Kotowski, M. Pawłowski, M. Lewenstein, A. Acín, Tight Bell inequalities with no quantum violation from qubit unextendible product bases, Phys. Rev. A 85, 042113 (2012).
[17] L. E. Würflinger, J. D. Bancal, A. Acín, N. Gisin, T. Vértesi, “Nonlocal multipartite correlations from local marginal probabilities”, Phys. Rev. A 86, 032117 (2012).
[18] G. Prettico, A. Acin, “Can bipartite classical information resources be activated?”, arXiv:1203.1445, accepted for publication in Quantum Information and Computation.
[19] C. Morgan, A. Winter, “Towards a strong converse for the quantum capacity (of degradable channels)”, arXiv:1301.4927
[20] N. Datta, Mark M. Wilde, M. Hsieh, A. Winter, “Quantum rate distortion coding with auxiliary resources”, arXiv:1212.5316
[21] E. Chitambar, D. Leung, L. Mancinska, M. Ozols, A. Winter, “Everything You Always Wanted to Know About LOCC (But Were Afraid to Ask)”, arXiv:1210.4583
[22] T. H. Yang, M. Navascues, “Robust Self Testing of Unknown Quantum Systems into Any Entangled Two-Qubit States, Phys. Rev. A 87, 050102(R) (2013)
[23] J. Briët, H. Buhrman, D. Gijswijt, "Violating the Shannon capacity of metric graphs with entanglement". Proceedings of the National Academy of Sciences, Dec 2012.
[24] J. Briet, H. Buhrman, M. Laurent, T. Piovesan, G. Scarpa, "Zero-error source-channel coding with entanglement". In Proceedings of Eurocomb 2013, Sep 2013.
[1] J. Silman, A. Chailloux, N. Aharon, I. Kerenidis, S. Pironio, S. Massar. “Fully Distrustful Quantum Bit Commitment and Coin Flipping”. Phys. Rev. Lett. Vol 106, 220501 (2011).
[2] Ll. Masanes, S. Pironio, A. Acín. “Secure device-independent quantum key distribution with causally independent measurement devices”. Nature Communications, 2, 238 (2011).
[3] R. Colbeck, A. Kent. "Private Randomness Expansion With Untrusted Devices''. J. Phys. A: Math. Theor., 44 (9), 095305 (2011).
[4] A. Acín, S. Massar, S. Pironio. Randomness vs Non Locality and Entanglement.
[5] M. Pawlowski, N. Brunner. “Semi-devide-independent security of one-way quantum key distribution”. Phys. Rev. A, Vol. 84(1), 010302(R) (2011).
[6] H. Buhrman, N. Chandran, S. Fehr, R. Gelles, V. Goyal, R. Ostrovsky, C. Schaffner. "Position-Based Quantum Cryptography: Impossibility and Constructions". In Advances in Cryptology – CRYPTO 2011, pages 429–446, 2011.
[7] H. Buhrman, S. Fehr, C. Schaffner, F. Speelman. The Garden-Hose Game and Application to Position-Based Quantum Cryptography. QCRYPT 2011.
[8] André Chailloux and Iordanis Kerenidis. Optimal bounds for quantum bit commitment. In Proc. IEEE FOCS.
[9] C. Schaffner. "Simple Protocols for Oblivious Transfer and Secure Identification in the Noisy-Quantum-Storage Model". Physical Review A 82, pages 032308, 2010.
[10] A. Kent. Unconditionally Secure Bit Commitment with Flying Qudits.
[11] A. Kent. "Location-Oblivious Data Transfer with Flying Entangled Qudits''. Phys. Rev. A, Vol. 84, 012328 (2011).
[12] A. Kent. Unconditionally Secure Bit Commitment by Transmitting Measurement Outcomes.
[13] M.-H. Hsieh, F. Le Gall. "NP-hardness of decoding quantum error-correction codes''. Phys. Rev. A, 83, 052331 (2011).
[14] K. Y. Cheong, M.-H. Hsieh, T. Koshiba. A Weak Quantum Oblivious Transfer.
[15] M. M. Wilde, M.-H. Hsieh. Entanglement boosts quantum turbo codes.
[16] L. Aolita, R. Gallego, A. Cabello, A. Acín. Fully nonlocal, monogamous and random genuinely multipartite quantum correlations.
[17] R. Rabelo, M. Ho, D. Cavalcanti, N. Brunner, V. Scarani. “Device-independent certification of entangled measurements”. Phys. Rev. Lett., 107, 050502 (2011).
[18] G. Brassard, P. Høyer, K. Kalach, M. Kaplan, S. Laplante, L. Salvail. Merkle puzzles in a quantum world. In Proceedings of Crypto'11, pages 385-404, (2011).
[19] N.J. Bouman, S. Fehr, C. Gonzalez-Guillen, C. Schaffner. An All-But-One Entropic Uncertainty Relation, and Application to Password-based Identification. QCRYPT 2011.
[20] D. Boneh, O. Dagdalen, M. Fischlin, A. Lehmann, C. Schaffner, M.Zhandry. Random Oracles in a Quantum World. In Application of Cryptology and Information Security – ASIACRYPT 2011.
[21] M. Tomamichel, C. Schaffner, A. Smith, R. Renner. "Leftover Hashing Against Quantum Side Information". IEEE Transactions on Information Theory, volume 57, issue 8, pages 5524–5535 (2011).
[22] (*) A. Kent, S. Massar, J. Silman, “Secure and Robust Transmission and Verification of Unknown Quantum States in Minkowski Space”, arXiv:1208.0745.
[23] K. F. Pal, T. Vertesi, N. Brunner, “Closing the detection loophole in multipartite Bell tests using GHZ states,” arXiv:1208.0622.
[24] M. Pawlowski, “Reply to "Comment on 'Security proof for cryptographic protocols based only on the monogamy of Bell's inequality violations",” Phys. Rev. A 85, 046302 (2012).
[25] B. Grandjean, Y.-C. Liang, J.-D. Bancal, N. Brunner, N. Gisin, “Bell inequalities for three systems and arbitrarily many measurement outcomes,” Phys. Rev. A, vol 85, 052113 (2012).
[26] P. Shadbolt, T. Vertesi, Y.-C. Liang, C. Branciard, N. Brunner, J. L. O'Brien, “Guaranteed violation of a Bell inequality without aligned reference frames or calibrated devices,” Scientific Reports 2, 470 (2012).
[27] (*) M. Hendrych, R. Gallego, M. Mičuda, N. Brunner, A. Acín, J. P. Torres, “Experimental estimation of the dimension of classical and quantum systems”, Nature Physics 8, 588 (2012).
[28] N. Brunner, J. Sharam, T. Vertesi, “Testing the Structure of Multipartite Entanglement with Bell Inequalities,” Phys. Rev. Lett. 108, 110501 (2012).
[29] A. Pappa, A. Chailloux, S. Wehner, E. Diamanti, I. Kerenidis, “Multiparty entanglement verification resistant against dishonest parties”, Phys. Rev. Letters 108, 260502, 2012.
[30] A. Pappa, A. Chailloux, S. Wehner, E. Diamanti, I. Kerenidis, “Multiparty entanglement verification resistant against dishonest parties”, Theory of Quantum Computation, Communication and Cryptography, 2012.
[31] I. Kerenidis, S. Wehner, “Long distance two-party quantum cryptography made simple”, Quantum Information and Computation, Vol 12 No 5&6, 448-460, 2012.
[32] H. Buhrman, M. Christandl, and C. Schaffner, "Complete Insecurity of Quantum Protocols for Classical Two-Party Computation", arxiv/1201.0849. To appear in Phys. Rev. Lett.
[33] S. Croke, A. Kent, “Security Details for Bit Commitment by Transmitting Measurement Outcomes”, arXiv:1208.1458
[34] S. Pironio and S. Massar, Security of practical private randomness generation, arXiv:1111.6056
[35] H-W Li, P. Mironowicz, M. Pawlowski, Z-Q Yin, Y-C Wu, S. Wang, W. Chen, H-G Hu, G-C Guo, Z-F Han, “On the relation between semi and fully device independent protocols”, Physical Review A 87, 020302(R) (2013).
[36] B. G. Christensen, K. T. McCusker, J. Altepeter, B. Calkins, T. Gerrits, A. Lita, A. Miller, L. K. Shalm, Y. Zhang, S. W. Nam, N. Brunner, C. C. W. Lim, N. Gisin, P. G. Kwiat, “Detection-Loophole-Free Test of Quantum Nonlocality, and Applications”, Physical Review Letters 111, 130406 (2013).
[37] M. Huber, M. Pawlowski, “Weak randomness in device-independent quantum key distribution and the advantage of using high-dimensional entanglement”, Physical Review A 88, 032309.
[38] S. Pironio, L. Masanes, A. Leverrier, A. Acin, “Security of device-independent quantum key distribution in the bounded-quantum-storage model”, arXiv:1211.1402, accepted for publication in Physical Review X.
[39] J. Barrett, R. Colbeck, A. Kent “Unconditionally secure device-independent quantum key distribution with only two devices”, Physical Review A 86, 062326 (2012).
[40] E. Woodhead, “A quantum cloning bound and application to quantum key distribution”, Physical Review A 88, 012331 (2013).
[41] E. Woodhead, S. Pironio, “Effects of preparation and measurement misalignments on the security of the BB84 quantum key distribution protocol”, Physical Review A 87, 032315 (2013).
[42] A. Pappa, P. Jouguet, T. Lawson, A. Chailloux, M. Legré, P. Trinkler, I. Kerenidis, E. Diamanti, “Experimental plug&play quantum coin flipping”, arXiv:1306.3368.
Tools for Quantum and Classical Computer Science
[1] A. Acin, S. Massar, S. Pironio. Randomness vs Non Locality and Entanglement. This is also part of WP2.4 Cryptographic applications.
[2] A. Ben-Aroya, A. Ta-Shma. “Better short-seed extractors against quantum knowledge”. Submitted to the journal Theoretical Computer Science.
[3] A. Ta-Shma. Short seed extractors against quantum storage. SIAM J. Computing, 40, 664--677, June 2011. An earlier version appeared in STOC 2009.
[4] A. Ben-Aroya, A. Ta-Shma. Approximate quantum error correction for correlated noise. IEEE Trans. on Information Theory, 57 (6), 3982-3099, June 2011. First (and weaker) version was presented at QIP 2009.
[5] R. Colbeck, A. Kent. Private Randomness Expansion With Untrusted Devices. J. Phys. A: Math. Theor., Vol. 44 (9), 095305 (2011)
[6] A. Ben-Aroya and A. Ta-Shma, “Better short-seed quantum-proof extractors”, Theoretical Computer Science, 419: 17-25 (2012)
[7] R. Arnon Friedman, E. Hänggi, A. Ta-Shma, “Towards the Impossibility of Non-Signalling Privacy Amplification from Time-Like Ordering Constraints”, arXiv:1205:3736.
[8] (*) A. Acin, S. Massar, S. Pironio, Randomness versus non locality and entanglement, Phys. Rev. Lett. 108, 100402 (2012).
[9] A. J. Short, T. C. Farrelly, “Quantum equilibration in finite time”, New J. Phys. 14, 013063, 2012.
[10] A. Montanaro, “Some applications of hypercontractive inequalities in quantum information theory”, arXiv:1208.0161
[11] A. Ta-Shma. Inverting well conditioned matrices in Quantum Logspace. ACM Symposium on the Theory of Computing (STOC’2013), pp. 881-890.
[12] R. Gallego, L. Masanes, G. de la Torre, C. Dhara, L. Aolita, A. Acin, “Full randomness from arbitrarily deterministic events”, arXiv:1210.6514, accepted for publication in Nature Communications.
[13] C. Dhara, G. Prettico, A. Acin “Maximal quantum randomness in Bell tests”, arXiv:1211.0650.
[14] C. Dhara, G. de la Torre, A. Acin, “Can observed randomness be certified to be fully intrinsic?”, arXiv:1305.5384.
[15] R. Augusiak, M. Demianowicz, M. Pawłowski, J. Tura, A. Acín, “Monogamies of correlations and amplification of randomness”, arXiv:1307.6390
[16] S. Pironio, L. Masanes, A. Leverrier, A. Acin, “Security of device-independent quantum key distribution in the bounded-quantum-storage model”, arXiv:1211.1402, accepted for publication in Physical Review X
[17] J. Silman, S. Pironio, S. Massar, “Device-Independent Randomness Generation in the Presence of Weak Cross-Talk”, Physical Review Letters 110, 100504 (2013)
[18] N. Silleras, S. Pironio, J. Silman, “Using complete measurement statistic for optimal device-independent randomness evaluation”, arXiv:1309.3930
[19] C. Lancien, A. Winter. Distinguishing multi-partite states by local measurements. Communications in Mathematical Physics 323, 555-573 (2013).
[20] P Mironowicz, M Pawlowski, “Weak randomness in device independent quantum key distribution and the advantage of using high dimensional entanglement”, Phys. Rev. A 88, 032309 (2013)
[21] S.W. Al-Safi, A.J. Short, “Simulating all non-signalling correlations via classical or quantum theory with negative probabilities”, arXiv:1301.2170
[22] R. Arnon Friedman, A. Ta-Shma. “Limits of privacy amplification against non-signalling memory attacks”. In QCrypt 2013.
Quantum Tools for Classical Computer Science
[1] A. Drucker, R. de Wolf, “Quantum proofs for classical theorems”. Theory of Computing (ToC Library Graduate Surveys 2), March 2011.
[2] A. Drucker, R. de Wolf, “Uniform Approximation by (Quantum) Polynomials”. Quantum Information and Computation, 11(3&4):215-225, 2011.
[3] J. Briët, H. Buhrman, T. Lee, T. Vidick, "All Schatten spaces endowed with the Schur product are Q-algebras", Journal of Functional Analysis, 262(1), pp 1-9, (1 January 2012).
[4] (*) S. Fiorini, S. Massar, S. Pokutta, H.R. Tiwary, and R. de Wolf, "Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds", 44th Annual ACM Symposium on Theory of Computing (STOC 12), pp.95-106 (2012).
[5] (*) I. Kerenidis, S. Laplante, V. Lerays, J. Roland, and D. Xiao. Lower bounds on information complexity via zero-communication protocols and applications. In 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'12), 2012. To appear. Quant-ph/1204.1505
[6] A. Ambainis, R. de Wolf. “How Low Can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?”. In 28th IEEE Annual Conference on Computational Complexity (CCC 13), 2013.
[7] S. Fiorini, S. Massar, M. K. Patra, H. R. Tiwary, Generalised probabilistic theories and the extension complexity of polytopes, arXiv:1310.4125.