ANR QuDATA Workshop
Quantum Algorithms for Massive Data
24-26 January, 2024
Bordeaux

Program

Wednesday, 24 January

• 14h00 - Yixin Shen (INRIA Rennes)
  Finding many Collisions via Reusable Quantum Walks
  Given a random function $f$ with domain $[2n]$ and codomain $[2m]$, with $m ≥ n$, a collision of $f$ is a pair of distinct inputs with the same image. Collision finding is an ubiquitous problem in cryptanalysis, and it has been well studied using both classical and quantum algorithms. Indeed, the quantum query complexity of the problem is well known to be $\Theta(2^{m/3})$, and matching algorithms are known for any value of $m$. The situation becomes different when one is looking for multiple collision pairs. Here, for $2k$ collisions, a query lower bound of $\Theta(2^{(2k+m)/3})$ was shown by Liu and Zhandry (EUROCRYPT '19). A matching algorithm is known, but only for relatively small values of $m$, when many collisions exist. In this paper, we improve the algorithms for this problem and, in particular, extend the range of admissible parameters where the lower bound is met.

  Our new method relies on a chained quantum walk algorithm, which might be of independent interest. It allows to extract multiple solutions of an MNRS-style quantum walk, without having to recompute it entirely: after finding and outputting a solution, the current state is reused as the initial state of another walk.

  As an application, we improve the quantum sieving algorithms for the shortest vector problem (SVP), with a complexity of $20.2563d+o(d)$ instead of the previous $20.2570d+o(d)$.
• 15h00 - Stéphane Dartois (CEA LIST, Univ. Paris-Saclay)
  Geometric multipartite entanglement and injective norm of uniform quantum states
  Good multipartite entanglement measures are poorly understood. One of them, named geometric entanglement, has been used to study e.g. the amount of entanglement used by Grover algorithm or in condensed matter to study topological phase transition. However, computing the geometric entanglement of typical quantum states is a NP-hard problem. In this talk, I will discuss the closely related injective norm for random uniform quantum states and provide an upper bound for this injective norm in several asymptotic regimes.

  This is ongoing work, in collaboration with Benjamin McKenna (U Harvard).
• 15h30 - Coffee break [ salle 076 - LaBRI ]
• 16h00 - Leonardo Novo (INL Braga - Portugal)
  Quantum search and optimization with continuous-time quantum walks
  Quantum walks, the quantum analogue of classical random walks, became an important framework for the development of quantum algorithms. In this talk, I will show how some analytical results about the performance of continuous-time quantum walk search algorithms can be used to analyse quantum algorithms for finding minima of cost functions via an adiabatic unstructured search approach. In order to obtain the expected Grover-like speed-up with the latter approach, it is necessary to have a precise knowledge of the position of the avoided crossing. However, we show that determining this exactly is a #P-HARD problem. This raises the question of whether a provable quadratic speed-up over classical unstructured search can be obtained for optimization problems in the adiabatic setting. Finally, I will discuss some near-term approaches to solve optimization problems based on continuous-time quantum walks, showing analytical and numerical evidence that they may outperform QAOA.
• 17h00 - End of talks

Thursday, 25 January

• 9h00 - Félix Huber (LaBRI, Univ. Bordeaux)
  Semidefinite programming bounds for quantum codes
  The fundamental problem in coding theory is to determine the maximum size of an error-correcting code of given distance and block length. Here we provide a semidefinite programming hierarchy to answer this question for the existence of quantum codes. Our hierarchy is complete in the sense that every set of parameters for which no code exists will be detected at some level of the hierarchy. We highlight connections to the quantum Shannon capactity of quantum graphs.
• 10h00 - Wouter Rozendaal (IMB, Univ. Bordeaux)
  A Renormalisation Decoder for Kitaev's Toric Code
  Kitaev's toric code is expected to be at the core of the first generation of quantum computers that will incorporate error protection. To make full use of the toric code, one requires an efficient decoding scheme that will process the classical information obtained from quantum syndrome measurements, so as to be able to regularly put arrays of qubits back into their intended states. The renormalisation decoders introduced by Duclos-Cianci and Poulin exhibit one of the best trade-offs between efficiency and speed. One feature that remained a mystery however, is their behaviour over adversarial channels, i.e. their worst-case behaviour. In this talk, we introduce a relatively natural and deterministic version of a renormalisation decoder and discuss its error-correcting radius.
• 10h30 - Coffee break [ salle 073 - LaBRI ]
• 11h00 - Jens Siewert (UPV/EHU, Leioa - Spain)
  Correlation constraints and the Bloch geometry of two-party systems
  A well-known consequence of the Schmidt decomposition theorem is that the local purities of a bipartite pure state are the same. What about the converse question: Given two different local purities, what is the maximum compatible global purity? This may be viewed as a relaxed version of the quantum marginal problem for bipartite states. We give a complete answer for the case of two qubits and present an analysis also for higher dimensions $d>2$. Technically this analysis is closely related to the Bloch representation, so that the results naturally lead to a geometrical picture, a Bloch body for two-party systems.

  Joint work with Simon Morelli, Christopher Eltschka, Marcus Huber.
• 12h00 - End of talks
• Lunch at Haut-Carré

• 14h00 - Simon Martiel (IBM Quantum, Paris)
  Shallower CNOT circuits on realistic quantum hardware
  TBA.
• 15h00 - Arthur Braida (ATOS & Univ. Orléans)
  Tight Lieb-Robinson bound for approximation ratio in Quantum Annealing
  Quantum annealing (QA) holds promise for optimization problems in quantum computing, especially for combinatorial optimization. This analog framework attracts attention for its potential to address complex problems. Its gate-based homologous, QAOA with proven performance, has brought lots of attention to the NISQ era. Several numerical benchmarks try to classify these two metaheuristics however, classical computational power highly limits the performance insights. In this work, we introduce a new parametrized version of QA enabling a precise 1-local analysis of the algorithm. We develop a tight Lieb-Robinson bound for regular graphs, achieving the best-known numerical value to analyze QA locally. Studying MaxCut over cubic graph as a benchmark optimization problem, we show that a linear-schedule QA with a 1-local analysis achieves an approximation ratio over $0.7020$, outperforming any known 1-local algorithms.
• 15h30 - Coffee break [ salle 076 - LaBRI ]
• 16h00 - Ion Nechita (CNRS Toulouse)
  Monogamy of highly symmetric states
  We study the question of how highly entangled two particles can be when also entangled in a similar way with other particles on the complete graph Kn for the case of Werner, isotropic and Brauer states. We formalize our question as a semidefinite program and then solve this optimization problem analytically, using tools from representation theory. In particular, we determine the exact maximum values p of the projection to the maximally entangled state and antisymmetric Werner state possible, solving long-standing open problems.

  This is joint work with Rene Allerstorfer, Matthias Christandl, Dmitry Grinko, Maris Ozols, Denis Rochette, and Philip Verduyn Lunel, arXiv:2309.16655
• 17h00 - End of talks

Friday, 26 January

• 9h00 - Yassine Hamoudi (LaBRI, CNRS Bordeaux)
  The NISQ Complexity of Collision Finding
  Collision-resistant hashing, a fundamental primitive in modern cryptography, ensures that there is no efficient way to find distinct inputs that produce the same hash value. This property underpins the security of various cryptographic applications, making it crucial to understand its complexity. Although it is well-understood in the classical setting, the advent of quantum computing has introduced new challenges since quantum adversaries — equipped with the power of quantum queries — can find collisions much more efficiently, prompting a need for longer hash outputs. However, as we are in the NISQ era, quantum computation is noisy and quantum memory is short-lived. We explore the existence and implications of quantum attacks in different NISQ models and ask whether they can already impact security.
• 10h00 - Maël Luce (IRIF, Univ. Paris-Cité)
  Distributed Grover Algorithm
  The CONGEST model is a standard distributed computing in which a set of $n$ processing nodes connected according to an $n$-node graph $G = (V,E)$ proceed synchronously, in a sequence of rounds. At each round, every node can send an $O(\log{n})$-bit message to each of its neighbors in $G$, and perform some local computation. We see how a distributed version of Grover can be implemented in this model to speed up different classical algorithms.
• 10h30 - Coffee break [ salle 076 - LaBRI ]
• 11h00 - Simon Apers (IRIF, CNRS Paris)
  Quantum speedups for linear programming via interior point methods
  We describe a quantum algorithm based on an interior point method for solving a linear program with $n$ inequality constraints on $d$ variables. The algorithm explicitly returns a feasible solution that is $\varepsilon$-close to optimal, and runs in time $\sqrt{n} \,\mathrm{poly}(d,\log(n),\log(1/\varepsilon))$ which is sublinear for tall linear programs (i.e., $n \gg d$). Our algorithm speeds up the Newton step in the state-of-the-art interior point method of Lee and Sidford [FOCS '14]. This requires us to efficiently approximate the Hessian and gradient of the barrier function, and these are our main contributions.

  To approximate the Hessian, we describe a quantum algorithm for the spectral approximation of $A^T A$ for a tall matrix $A \in \mathbb{R}^{n \times d}$. The algorithm uses leverage score sampling in combination with Grover search, and returns a $\delta$-approximation by making $O(\sqrt{nd}/\delta)$ row queries to $A$. This generalizes an earlier quantum speedup for graph sparsification by Apers and de Wolf [FOCS '20]. To approximate the gradient, we use a recent quantum algorithm for multivariate mean estimation by Cornelissen, Hamoudi and Jerbi [STOC '22]. While a naive implementation introduces a dependence on the condition number of the Hessian, we avoid this by pre-conditioning our random variable using our quantum algorithm for spectral approximation.
• 12h00 - End of talks
• Lunch at Haut-Carré
• End of the meeting

Pictures of the meeting

                       

Organizers: Cyril Gavoille, Adrian Tanasa, Yassine Hamoudi