ANR support

All related publications need to mention the support from the project as follows:
Supported by the French ANR project ANR-18-CE47-0010 (QUDATA)

Selection of publications (period January 2019 - June 2024)

Books
2021
[1] Algorithmes quantiques : quand la physique quantique défie la thèse de Church-Turing (), Collège de France / Fayard, . [bibtex] [url]
Refereed Articles
2019
[35] Learning-with-errors problem is easy with quantum samples (, and ), In Phys. Rev. A, American Physical Society, volume 99, . [bibtex] [url] [doi]
[34] Anonymity for Practical Quantum Networks (, , , , and ), In Phys. Rev. Lett., American Physical Society, volume 122, . [bibtex] [url] [doi]
[33] Quantum and classical algorithms for approximate submodular function minimization (, , and ), In Quantum Information and Computation, Rinton Press, volume 19, . [bibtex] [url] [doi]
2020
[32] Extended Learning Graphs for Triangle Finding (, and ), In Algorithmica, volume 82, . [bibtex] [url] [doi]
[31] Quantum gradient descent for linear systems and least squares ( and ), In Phys. Rev. A, American Physical Society, volume 101, . [bibtex] [url] [doi]
[30] Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel ( and ), In Phys. Rev. Research, American Physical Society, volume 2, . [bibtex] [url] [doi]
[29] A Quantum Interior Point Method for LPs and SDPs ( and ), In ACM Transactions on Quantum Computing, Association for Computing Machinery, volume 1, . [bibtex] [url] [doi]
[28] Quantum Algorithms for Feedforward Neural Networks (, , and ), In ACM Transactions on Quantum Computing, Association for Computing Machinery, volume 1, . [bibtex] [url] [doi]
[27] Solving optimization problems with Rydberg analog quantum computers: Realistic requirements for quantum advantage using noisy simulation and classical benchmarks (, and ), In Phys. Rev. A, American Physical Society, volume 102, . [bibtex] [url] [doi]
2021
[26] Quantum machine learning with adaptive linear optics (, and ), In Quantum, volume 5, . [bibtex] [url] [doi]
[25] Quantum algorithms for Second-Order Cone Programming and Support Vector Machines (, and ), In Quantum, volume 5, . [bibtex] [url] [doi]
[24] Quantum spectral clustering ( and ), In Phys. Rev. A, volume 103, . [bibtex] [url] [doi]
[23] On the Possibility of Classical Client Blind Quantum Computing (, , and ), In Cryptography, volume 5, . [bibtex] [url] [doi]
[22] Quantum algorithms for hedging and the learning of Ising models (, , , , and ), In Phys. Rev. A, American Physical Society, volume 103, . [bibtex] [url] [doi]
[21] Composable security for multipartite entanglement verification (, and ), In Phys. Rev. A, American Physical Society, volume 103, . [bibtex] [url] [doi]
[20] Anti-crossings and spectral gap during quantum adiabatic evolution ( and ), In Quantum Information Processing, Springer Science and Business Media LLC, volume 20, . [bibtex] [url] [doi]
[19] Verifying BQP Computations on Noisy Devices with Minimal Overhead (, , and ), In PRX Quantum, American Physical Society, volume 2, . [bibtex] [url] [doi]
2022
[18] Low depth algorithms for quantum amplitude estimation (, , , and ), In Quantum, volume 6, . [bibtex] [url] [doi]
[17] Quantum XYZ Product Codes (, and ), In Quantum, volume 6, . [bibtex] [url] [doi]
[16] Towards local testability for quantum coding ( and ), In Quantum, volume 6, . [bibtex] [url] [doi]
[15] Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ( and ), In SIAM J. Comput., volume 51, . [bibtex] [url] [doi]
[14] Quantum Distributed Complexity of Set Disjointness on a Line ( and ), In ACM Trans. Comput. Theory, volume 14, . [bibtex] [url] [doi]
[13] Quadratic speedup for spatial search by continuous-time quantum walk (, , and ), In Phys. Rev. Lett., volume 129, . [bibtex] [url] [doi]
[12] On constant-time quantum annealing and guaranteed approximations for graph optimization problems (, and ), In Quantum Science and Technology, IOP Publishing, volume 7, . [bibtex] [url] [doi]
[11] QEnclave - A practical solution for secure quantum cloud computing (, , , and ), In npj Quantum Information, Springer Science and Business Media LLC, volume 8, . [bibtex] [url] [doi]
2023
[10] Quantum reinforcement learning via policy iteration (, and ), In Quantum Mach. Intell., volume 5, . [bibtex] [url] [doi]
[9] A (simple) classical algorithm for estimating Betti numbers (, and ), In Quantum, volume 7, . [bibtex] [url] [doi]
[8] Quantum Deep Hedging (, , , , , , , , , , , , , and ), In Quantum, volume 7, . [bibtex] [url] [doi]
[7]Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs ( and ), In ACM Transactions on Computation Theory, volume 15, . [bibtex] [pdf] [doi]
2024
[6] Improved financial forecasting via quantum machine learning (, , , , and ), In Quantum Mach. Intell., volume 6, . [bibtex] [url] [doi]
[5] Quantum Vision Transformers (, , , , and ), In Quantum, volume 8, . [bibtex] [url] [doi]
[4] On the power of threshold-based algorithms for detecting cycles in the CONGEST model (, and ), In Theor. Comput. Sci., volume 996, . [bibtex] [url] [doi]
[3] Avoided level crossings with exponentially closing gaps in quantum annealing (, and ), In Phys. Rev. A, American Physical Society, volume 109, . [bibtex] [url] [doi]
[2] Tight Lieb–Robinson Bound for approximation ratio in quantum annealing (, and ), In npj Quantum Information, Springer Science and Business Media LLC, volume 10, . [bibtex] [url] [doi]
[1] Unifying quantum verification and error-detection: theory and tools for optimisations (, , , and ), In Quantum Science and Technology, IOP Publishing, volume 9, . [bibtex] [url] [doi]
Refereed Conference Papers
2018
[39] Strategies for Quantum Races (, and ), In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) (Avrim Blum, ed.), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, volume 124, . [bibtex] [url] [doi]
2019
[38] Quantum Algorithms for Portfolio Optimization (, and ), In Proceedings of the 1st ACM Conference on Advances in Financial Technologies, Association for Computing Machinery, . [bibtex] [url] [doi]
[37] QFactory: Classically-Instructed Remote Secret Qubits Preparation (, , and ), In Lecture Notes in Computer Science, Springer International Publishing, . [bibtex] [url] [doi]
[36] Localisation-Resistant Random Words with Small Alphabets (, and ), In Lecture Notes in Computer Science, Springer International Publishing, . [bibtex] [url] [doi]
[35] Q-means: A quantum algorithm for unsupervised machine learning (, , and ), In Advances in Neural Information Processing Systems (H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, R. Garnett, eds.), Curran Associates, Inc., volume 32, . [bibtex] [pdf]
[34] Quantum Chebyshev's Inequality and Applications ( and ), In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi, eds.), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, volume 132, . [bibtex] [url] [doi]
2020
[33]Quantum Divide and Compute: Hardware Demonstrations and Noisy Simulations ( and ), In 2020 IEEE Computer Society Annual Symposium on VLSI (ISVLSI), . [bibtex] [doi]
[32]Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expanders (), In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), . [bibtex] [doi]
[31] Security Limitations of Classical-Client Delegated Quantum Computing (, , , , , and ), In Advances in Cryptology - ASIACRYPT 2020, Springer International Publishing, . [bibtex] [url] [doi]
[30] Quantum Algorithms for Deep Convolutional Neural Networks (, and ), In International Conference on Learning Representations, . [bibtex] [url]
[29] Practical Implementation of a Quantum Backtracking Algorithm ( and ), In SOFSEM 2020: Theory and Practice of Computer Science, Springer International Publishing, . [bibtex] [url] [doi]
[28] Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model (, and ), In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) (Christophe Paul, Markus Bläser, eds.), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, volume 154, . [bibtex] [url] [doi]
[27] Quantum Distributed Complexity of Set Disjointness on a Line ( and ), In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) (Artur Czumaj, Anuj Dawar, Emanuela Merelli, eds.), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, volume 168, . [bibtex] [url] [doi]
[26] Quantum Expectation-Maximization for Gaussian mixture models (, and ), In Proceedings of the 37th International Conference on Machine Learning (Hal Daumé III, Aarti Singh, eds.), PMLR, volume 119, . [bibtex] [pdf]
2021
[25] Quantum Complexity of Minimum Cut ( and ), In 36th Computational Complexity Conference (Valentine Kabanets, ed.), Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, volume 200, . [bibtex] [url] [doi]
[24] Quantum sub-Gaussian mean estimator (), In 29th Annual European Symposium on Algorithms (Petra Mutzel, Rasmus Pagh, Grzegorz Herman, eds.), Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, volume 204, . [bibtex] [url] [doi]
[23] Quantum Algorithms for Matrix Scaling and Matrix Balancing (, , , , and ), In 48th International Colloquium on Automata, Languages, and Programming (Nikhil Bansal, Emanuela Merelli, James Worrell, eds.), Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, volume 198, . [bibtex] [url] [doi]
[22] A Unified Framework of Quantum Walk Search (, and ), In 38th International Symposium on Theoretical Aspects of Computer Science (Markus Bläser, Benjamin Monmege, eds.), Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, volume 187, . [bibtex] [url] [doi]
[21] Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs ( and ), In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (Min-Hsiu Hsieh, ed.), Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, volume 197, . [bibtex] [url] [doi]
[20] Distributed Quantum Proofs for Replicated Data (, , and ), In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) (James R. Lee, ed.), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, volume 185, . [bibtex] [url] [doi]
[19] Towards Local Testability for Quantum Coding (, and ), In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) (James R. Lee, ed.), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, volume 185, . [bibtex] [url] [doi]
[18] Quantum algorithms for graph problems with cut queries (, and ), In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, . [bibtex] [url] [doi]
2022
[17] Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming (, , , and ), In 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany (Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman, eds.), Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, volume 244, . [bibtex] [url] [doi]
[16] Quantum Tanner codes ( and ), In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, IEEE, . [bibtex] [url] [doi]
[15] Improved Quantum Lower and Upper Bounds for Matrix Scaling ( and ), In 39th International Symposium on Theoretical Aspects of Computer Science (Petra Berenbrink, Benjamin Monmege, eds.), Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, volume 219, . [bibtex] [url] [doi]
[14] Quantum Algorithm for Stochastic Optimal Stopping Problems with Applications in Finance (, , , and ), In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2022, July 11-15, 2022, Urbana Champaign, Illinois, USA (Le Gall, François, Tomoyuki Morimae, eds.), Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, volume 232, . [bibtex] [url] [doi]
2023
[13]Time and Query Complexity Tradeoffs for the Dihedral Coset Problem (, and ), In Post-Quantum Cryptography (Johansson, Thomas, Smith-Tone, Daniel, eds.), Springer Nature Switzerland, . [bibtex]
[12] (No) Quantum Space-Time Tradeoff for USTCON (, , and ), In 31st Annual European Symposium on Algorithms, ESA 2023, September 4-6, 2023, Amsterdam, The Netherlands (Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, Grzegorz Herman, eds.), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, volume 274, . [bibtex] [url] [doi]
[11] Certificate Games (, , , and ), In 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA (Yael Tauman Kalai, ed.), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, volume 251, . [bibtex] [url] [doi]
[10] The Communication Complexity of Functions with Large Outputs (, , and ), In Structural Information and Communication Complexity - 30th International Colloquium, SIROCCO 2023, Alcalá de Henares, Spain, June 6-9, 2023, Proceedings (Sergio Rajsbaum, Alkida Balliu, Joshua J. Daymude, Dennis Olivetti, eds.), Springer, volume 13892, . [bibtex] [url] [doi]
[9] On the Power of Threshold-Based Algorithms for Detecting Cycles in the CONGEST Model (, and ), In Structural Information and Communication Complexity - 30th International Colloquium, SIROCCO 2023, Alcalá de Henares, Spain, June 6-9, 2023, Proceedings (Sergio Rajsbaum, Alkida Balliu, Joshua J. Daymude, Dennis Olivetti, eds.), Springer, volume 13892, . [bibtex] [url] [doi]
[8] Quantum tomography using state-preparation unitaries (, , and ), In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 (Nikhil Bansal, Viswanath Nagarajan, eds.), SIAM, . [bibtex] [url] [doi]
[7] A Sublinear-Time Quantum Algorithm for Approximating Partition Functions ( and ), In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 (Nikhil Bansal, Viswanath Nagarajan, eds.), SIAM, . [bibtex] [url] [doi]
[6] Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes (), In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 (Nikhil Bansal, Viswanath Nagarajan, eds.), SIAM, . [bibtex] [url] [doi]
[5] Quantum Policy Gradient Algorithms (, , and ), In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2023, July 24-28, 2023, Aveiro, Portugal (Omar Fawzi, Michael Walter, eds.), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, volume 266, . [bibtex] [url] [doi]
[4] Testing Cluster Properties of Signed Graphs ( and ), In Proceedings of the ACM Web Conference 2023, WWW 2023, Austin, TX, USA, 30 April 2023 - 4 May 2023 (Ying Ding, Jie Tang, Juan F. Sequeda, Lora Aroyo, Carlos Castillo, Geert-Jan Houben, eds.), ACM, . [bibtex] [url] [doi]
2024
[3] The NISQ Complexity of Collision Finding (, and ), In Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part IV (Marc Joye, Gregor Leander, eds.), Springer, volume 14654, . [bibtex] [url] [doi]
[2] (Quantum) Complexity of Testing Signed Graph Clusterability ( and ), In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2024, September 9-13, 2024, Okinawa, Japan (Frédéric Magniez, Alex Bredariol Grilo, eds.), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, volume 310, . [bibtex] [url] [doi]
[1]Even-Cycle Detection in the Randomized and Quantum CONGEST Model (, , and ), In Proceedings of 43rd ACM Symposium on Principles of Distributed Computing, . [bibtex] [pdf] [doi]