Workshops

Literature overview

• Devdatt Dubhashi

  • Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, Tanuj Khattar, Ryan Babbush: Optimization by decoded quantum interferometry. 

  • André Chailloux, Jean-Pierre Tillich: Quantum Advantage from Soft Decoders. 

  • André Chailloux, Jean-Pierre Tillich: The Quantum Decoding Problem. 

  • Kunal Marwaha, Bill Fefferman, Alexandru Gheorghiu, Vojtech Havlícek: On the Complexity of Decoded Quantum Interferometry. 

  • Slides 

• Marc Wanner

• Chi-Fang (Anthony) Chen, Anurag Anshu, Quynh Nguyen: Learning quantum Gibbs states locally and efficiently

• Thomas Schuster, Dominik Kufel, Norman Y. Yao, Hsin-Yuan Huang: Hardness of recognizing phases of matter.

• Meghal Gupta, William He, Ryan O'Donnell: Few Single-Qubit Measurements Suffice to Certify Any Quantum State

• Slides 

• Pingal Pratyush Nath

  • András Gilyén, Chi-Fang Chen, Joao F. Doriguello, Michael J. Kastoryano: Quantum Markov Chains: Glauber and Metropolis dynamics

  • Gregory D. Kahanamoku-Meyer, John Blue, Thiago Bergamaschi, Craig Gidney, Isaac L. Chuang: A log-depth in-place quantum Fourier transform that rarely needs ancillas

  • David Gosset, Robin Kothari, Chenyi Zhang: Multi-qubit Toffoli with exponentially fewer T gates

  • Johannes Jakob Meyer, Asad Raza, Jacopo Rizzo, Lorenzo Leone, Sofiene Jerbi, Jens Eisert: Computational Relative Entropy

  • Salman Beigi, Christoph Hirche, Marco Tomamichel: Some properties and applications of the new quantum f-divergences

  • Slides 

• Q&A

• Question to Alexandru Georghiu: Would approx QFT suffice for your sampling? Does it suffice in general for DQI style algorithms as in Andre's tutorial? 

• Answer: I think it depends on what kind of approximation you mean. Like if you mean approximate in operator norm, then I think DQI will still be good because the output state will now be eps-close in trace distance to the ideal output state (assuming you have an eps-approximate QFT) and the associated distribution you get from sampling from it will also be eps-close in TVD to the ideal distribution. This means that you should still be getting good solutions to the underlying optimization problem whp, it might just require you to sample more. In terms of classical simulatibility, I don't see any clear way in which considering the approximate QFT would help (which is consistent with the fact that the quantum algorithm would still perform well in this setting). 

But if the QFT is approximate in more of a Hamming distance sense, i.e. each output qubit is flipped with some small probability eps, then DQI will not perform as well. The relative number of constraints that an output string from DQI will satisfy is something like 1/2 + sqrt{l/m * (m-l)/m}, where m is the number of constraints and l is the number of errors the associated code can correct (this is the semi-circle law in the DQI paper). But now, if around eps of the bits can be flipped, that number will become something like 1/2 + sqrt{l/m * (m-l)/m} - eps/2 (well, I think this is approximately true for small eps, since the value should become 1/2 when eps is 1). As long as eps < sqrt{l/m * (m-l)/m} this should still be pretty good in general (though of course it depends on the associated optimization problem, since there might be classical algorithms that can do just as well if not better).

Now, given that the performance is worse, one would expect that there might be classical algorithms that could sample from this "noisy" DQI output distribution. But I don't immediately see a way to do it. We do know that we can classically sample high weight strings from the (ideal) DQI output distribution, where high weight means probability > 1/poly (this is the Schwarz and van den Nest result). But the DQI distribution is generally fairly flat and even in this regime with a noisy output it will remain fairly flat, so it's not clear that there's anything one can do here, in general.

There are also ways to classically simulate noisy quantum circuits efficiently (for instance https://arxiv.org/abs/2211.03999), but those are generally for random quantum circuits, not the structured kinds of circuits we have in DQI.

I'll also mention that one can ask the same question for factoring/period finding. Say for instance that we merely want to recover a fraction of the bits of the factors of the number we wish to factor. Is there an efficient way to do this classically? I'm not sure if this is written anywhere, but I talked to someone about this and they said that it should be possible to do it efficiently classically for up to 2/3rds of the bits, but beyond that it's brute force. Interestingly, this asymptotically matches the runtime of the best known classical factoring algorithm which takes time 2^{n^{1/3}}. So going beyond 2/3rds would be an improvement over the best known factoring algorithms. It's possible a similar thing is true for DQI.
Related to this, I don't know if there are more efficient quantum factoring algorithms that can give you more than 2/3rds of the bits, without having to do the full version of Shor's algorithm.

• Question to André Chailloux: You mentioned a quantum decoding algorithm by Renes et al https://www.research-collection.ethz.ch/server/api/core/bitstreams/93c90701-78c4-4b89-bd8a-fe72dcb87e57/content What is the status today? Does it give advantage over classical decoding? Are there other such quantum decoding algorithms? And if so what are the consequences for dqi style algorithms? 

• Answer: To give a short answer, I would say the current status is unclear. Using the BPQM framework of Piveteau and Renes does in theory improve DQI type algorithms as it allows to decode more errors than a classical decoder with classical errors. It can possibly have the two following limitations:

  • these decoders do rely on assumptions that are not necessarily satisfied for fixed size codes.

  • even with the improvement, it's unclear whether the DQI type problem we're solving is hard for classical computers. 

Despite these two possible limitations, it is one of the most interesting ways in improving the reduction so there could very well be nice improvements that arise from this, but we don't know yet.