STOC'25/TheoryFest workshop C

Recent developments in quantum algorithms

Organizers:

• Stacey Jeffery (QuSoft, CWI and University of Amsterdam)
• Ronald de Wolf (QuSoft, CWI and University of Amsterdam)

Program at a glance (for abstracts, see below; full STOC program is here):

• 8:45-9:45 Ronald de Wolf (QuSoft, CWI and University of Amsterdam): Tutorial about quantum algorithms
• 9:45-10:45 Alexander Schmidhuber (MIT): Quartic quantum speedups for planted inference

• 8:45-9:45 Francois Le Gall (Nagoya University): Recent developments in quantum distributed algorithms
• 9:45-10:45 Mary Wootters (Stanford University): Optimization by Decoded Quantum Interferometry

• 8:45-9:45 Alexander Belov (University of Latvia): Quantum Las Vegas Complexity
• 9:45-10:45 Subhasree Patro (Eindhoven University of Technology): A survey on quantum fine-grained complexity

Abstracts:

• Tuesday 8:45-9:45 Ronald de Wolf (QuSoft, CWI and University of Amsterdam): Tutorial about quantum algorithms
  
  Abstract: This tutorial will give an introduction to the main quantum algorithms known, briefly surveying the state of the art prior to the results presented in this workshop. We will go over Shor's algorithm for factoring integers, Grover's algorithm for search, quantum walks, and the HHL algorithm for solving linear systems. We will also briefly go over the 5 talks of the workshop and put them into context.


• Tuesday 9:45-10:45 Alexander Schmidhuber (MIT): Quartic quantum speedups for planted inference
  
  Abstract: We describe a quantum algorithm for the Planted Noisy kXOR problem (also known as sparse Learning Parity with Noise) that achieves a nearly quartic (4th power) speedup over the best known classical algorithm while also only using logarithmically many qubits. Our work generalizes and simplifies prior work of Hastings, by building on his quantum algorithm for the Tensor Principal Component Analysis (PCA) problem. We achieve our quantum speedup using a general framework based on the Kikuchi Method (recovering the quartic speedup for Tensor PCA), and we anticipate it will yield similar speedups for further planted inference problems. These speedups rely on the fact that planted inference problems naturally instantiate the Guided Sparse Hamiltonian problem. Since the Planted Noisy kXOR problem has been used as a component of certain cryptographic constructions, our work suggests that some of these are susceptible to super-quadratic quantum attacks.
  This is joint work with Ryan O'Donnell, Robin Kothari, and Ryan Babbush.
  


• Wednesday 8:45-9:45 Francois Le Gall (Nagoya University): Recent developments in quantum distributed algorithms
  
  Abstract: I will talk about quantum distributed computing, i.e., distributed computing where the processors of the network can exchange quantum messages. After describing the basics of distributed computing, I will present recent developments in quantum distributed algorithms that show a significant quantum advantage for some distributed computing tasks. I will also describe interesting and important open questions in quantum distributed computing.


• Wednesday 9:45-10:45 Mary Wootters (Stanford University): Optimization by Decoded Quantum Interferometry
  
  Abstract: We introduce a quantum algorithm called Decoded Quantum Interferometry (DQI), which uses the quantum Fourier transform to reduce optimization problems to decoding problems. For approximating optimal polynomial fits to data over finite fields (which follows from a quantum reduction to the problem of decoding Reed-Solomon codes), DQI efficiently achieves a better approximation ratio than any polynomial time classical algorithm known to us. Sparse unstructured optimization problems such as max-k-XORSAT are reduced to decoding of LDPC codes. Although we have not identified quantum advantage for the sparse unstructured case, we prove a theorem which allows the performance of DQI to be calculated instance-by-instance based on the empirical performance of classical LDPC decoders such as belief propagation. We demonstrate this by benchmarking on an instance with over 30,000 variables.
  This is joint work with Stephen P. Jordan, Noah Shutty, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, and Ryan Babbush.
  


• Thursday 8:45-9:45 Alexander Belov (University of Latvia): Quantum Las Vegas Complexity
  
  Abstract: In this talk, I will survey a new framework for the development of quantum algorithms: quantum Las Vegas complexity and the related technical tool of transducers. I will mention the following features and results related to this framework:
  - definition of input-dependent complexity, which is respected under composition;
  - an alternative direct implementation of quantum walks, span programs, and the dual adversary bound;
  - conversion of a bounded-error subroutine into an exact subroutine with only constant increase in complexity;
  - an optimal implementation of the exponential speed-up by a quantum walk on the welded-tree graph.
  These results take into account both query and time complexity. They are achieved in a conceptually very simple way. In particular, implementation of quantum walks does not require any spectral analysis.
  This is joint work with Stacey Jeffery and Duyal Yolcu.


• Thursday 9:45-10:45 Subhasree Patro (Eindhoven University of Technology): A survey on quantum fine-grained complexity
  
  Abstract: One of the major challenges in the field of complexity theory is the inability to prove unconditional time lower bounds. One way around this is the study of fine-grained complexity where we use special reductions to prove exact time lower bounds for problems based on the conjectured hardness of some key problems, say the Satisfiability (SAT) problem, 3SUM or APSP. The situation in the quantum regime is no better; almost all known lower bounds are defined in terms of query complexity, which is not very useful for problems whose best-known algorithms take superlinear time. Therefore, employing fine-grained reductions in the quantum setting seems a natural way forward. However, translating the classical fine-grained reductions directly into the quantum regime is not always possible. In this talk, I will present a survey on recent results that prove fine-grained quantum time lower bounds conditioned on the conjectured quantum hardness of a few key problems.