Publications

Journals

Published:

• S. Laplante, M. Laurière and A. Nolin, J. Roland, and G. Senno, Robust Bell inequalities from communication complexity, Quantum 2:72, 2018.
• E. Campbell, A. Khurana, and A. Montanaro, Applying quantum algorithms to constraint satisfaction problems, Quantum 3:167, 2019.
• J. Doriguello and A. Montanaro, Quantum sketching protocols for Hamming distance and beyond, Phys. Rev. A 99:062331, 2019.
• M. Hebenstreit, R. Jozsa, B. Kraus, S. Strelchuk, M. Yoganathan, All pure fermionic non-Gaussian states are magic states for matchgate computations, Phys. Rev. Lett. 123, 080503, 2019.
• M. Yoganathan, R. Jozsa and S. Strelchuk, Quantum advantage of unitary Clifford circuits with magic state inputs, Proc. R. Soc. (Lond.) A 475: 20180427, 2019.

Accepted:

• N. Kumar, I. Kerenidis and E. Diamanti, Experimental demonstration of quantum advantage for one-way communication complexity, To appear in Nature Communications. arXiv:1811.09154, 2019.

Under review:

• J. Allcock, C.Y. Hsieh, I. Kerenidis, S. Zhang, Quantum algorithms for feedforward neural networks, arXiv preprint arXiv:1812.03089, 2018.
• J. van Apeldoorn, A. Gilyén, S. Gribling, and R. de Wolf, Convex optimization using quantum oracles, arXiv:1809.00643, 2018.
• J. van Apeldoorn and S. Gribling, Simon’s problem for linear functions, arXiv:1810.12030, 2018.
• K. Bharti, A.S. Arora and L.C. Kwek, and J. Roland, A simple proof of uniqueness of the KCBS inequality, arXiv:1811.05294, 2018.
• S. Chakraborty, L. Novo, and J. Roland, Finding a marked node on any graph by continuous time quantum walk, arXiv:1807.05957, 2018.
• I Kerenidis, J Landman, A Luongo, A Prakash, q-means: A quantum algorithm for unsupervised machine learning, arXiv:1812.03584, 2018.
• I Kerenidis, A Luongo, Quantum classification of the MNIST dataset via slow feature analysis, arXiv:1805.08837, 2018.
• I. Kerenidis, A. Prakash, A quantum interior point method for LPs and SDPs, arXiv:1808.09266, 2018.
• A. Ambainis, A. Gilyén, S. Jeffery, and M. Kokainis, Quadratic speedup for finding marked vertices by quantum walks, arXiv:1903.07493, 2019.
• J. van Apeldoorn and A. Gilyén, Quantum algorithms for zero-sum games, arXiv:1904.03180, 2019.
• I. Bardet, M. Junge, N. LaRacuente, C. Rouzé, D.S. França, Group transference techniques for the estimation of the decoherence times and capacities of quantum Markov semigroups, arXiv:1904.11043, 2019.
• S. Chakraborty, K. Luh and J. Roland, On analog quantum algorithms for the mixing of markov chains, arXiv:1904.11895, 2019.
• X. Guo, C.R. Breum, J. Borregaard, S. Izumi, M.V. Larsen, M. Christandl, J.S. Neergaard-Nielsen and U.L. Andersen, Distributed quantum sensing in a continuous variable entangled network, arXiv:1905.09408, 2019.
• Y. Hamoudi, P. Rebentrost, A. Rosmanis and M. Santha, Quantum and classical algorithms for approximate submodular function minimization, arXiv:1907.05378, 2019.
• G. Joret J. Cardinal and J. Roland, Information-theoretic lower bounds for quantum sorting, arXiv:1902.06473, 2019.
• I. Kerenidis, A. Prakash, D. Szilagyi, Quantum Algorithms for Portfolio Optimization, arXiv:1908.08040, 2019.
• I. Kerenidis, A. Prakash, D. Szilagyi, A Quantum Interior-Point Method for Second-Order Cone Programming, arXiv:1908.06720, 2019.
• G. De Palma, The squashed entanglement of the noiseless quantum Gaussian attenuator and amplifier, arXiv:1905.08480, 2019.

Conference proceedings

Published:

• D. Aggarwal, A. Joux, A. Prakash and M. Santha, A new public-key cryptosystem via Mersenne numbers, In Proceedings of 38th International Cryptology Conference CRYPTO, 2018.
• Y. Aono, P. Q. Nguyen ann Y. Shen, Quantum Lattice Enumeration and Tweaking Discrete Pruning, In Proceedings of 24th Annual International Conference on the Theory and Application of Cryptology and Information Security ASIACRYPT, 2018.
• F. Le Gall and F. Magniez, Sublinear-Time Quantum Computation of the Diameter in CONGEST Networks, In Proceedings of 37th ACM Symposium on Principles of Distributed Computing, 2018.
• S. Gharibian, M. Santha, J. Sikora, A. Sundaram and J. Yirka, Quantum generalizations of the polynomial hierarchy with applications to QMA(2), In Proceedings of 43rd International Symposium on Mathematical Foundations of Computer Science, 2018.
• G. Ivanyos, A. Prakash and M. Santha, On learning linear functions from subset and its applications in quantum computing, In Proceedings of 26th Annual European Symposium on Algorithms, 2018. Also in QIP 2019.
• A. Ambainis, K. Balodis, J. Iraids, M. Kokainis, K. Prusis, J. Vihrovs, Quantum Speedups for Exponential-Time Dynamic Programming Algorithms, In the Proceedings of 30th Annual Symposium On Discrete Algorithms, 2019.
• A. Ambainis, M. Hamburg, D. Unruh, Quantum security proofs using semi-classical oracles, In Proceedings of 38th International Cryptology Conference CRYPTO, 2019.
• J. van Apeldoorn and A. Gilyén. Improvements in Quantum SDP-Solving with Applications, In Proceedings of 46th International Colloquium on Automata, Languages and Programming, 2019.
• A. Arora, J. Roland, and S. Weis, Quantum weak coin flipping, In 51st ACM Symposium on Theory of Computing, 2019.
• S. Arunachalam, S. Chakraborty, T. Lee, M. Paraashar, and R. de Wolf, Two new results about quantum exact learning, In Proceedings of 46th International Colloquium on Automata, Languages and Programming, 2019.
• A. Belovs, Quantum Algorithm for Distribution-Free Junta Testing, In Proceedings of 14th Computer Science Symposium in Russia, 2019.
• S. Chakraborty, A. Gilyén and S. Jeffery, The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation, In Proceedings of 46th International Colloquium on Automata, Languages, and Programming, 2019.
• Y. Hamoudi and F. Magniez, Quantum Chebyshev’s Inequality and Applications, In Proceedings of 46th International Colloquium on Automata, Languages and Programming, 2019.
• T. Lee, M. Ray and M. Santha, Strategies for quantum races, In Proceedings of 10th Innovations in Theoretical Computer Science, 2019.
• M. Sinha and R. de Wolf, Exponential Separation between Quantum Communication and Logarithm of Approximate Rank, In Proceedings of IEEE FOCS’19. arXiv:1811.10090, 2019.