Long-delayed UT Austin Quantum Complexity Theory Student Project Showcase!

Back at MIT, whenever I taught my graduate course on Quantum Complexity Theory (see here for lecture notes), I had a tradition of showcasing the student projects on this blog: see here (Fall 2010), here (Fall 2012), here (Fall 2014). I was incredibly proud that, each time I taught, at least some of the projects led to publishable original research—sometimes highly significant research, like Paul Christiano’s work on quantum money (which led to my later paper with him), Shelby Kimmel’s work on quantum query complexity, Jenny Barry’s work on quantum partially observable Markov decision processes (“QOMDPs”), or Matt Coudron and Henry Yuen’s work on randomness expansion (which led to their later breakthrough in the subject).

Alas, after I moved to UT Austin, for some reason I discontinued the tradition of these blog-showcases—and inexcusably, I did this even though the wonderful new research results continued! Now that I’m teaching Quantum Complexity Theory at UT for the third time (via Zoom, of course), I decided that it was finally time to remedy this. To keep things manageable, this time I’m going to limit myself to research projects that began their lives in my course and that are already public on the arXiv (or in one case, that will soon be).

So please enjoy the following smorgasbord, from 2016 and 2019 iterations of my course! And if you have any questions about any of the projects—well, I’ll try to get the students to answer in the comments section! Thanks so much and congratulations to the students for their work.

From the Fall 2016 iteration of the course

William Hoza (project turned into a joint paper with Cole Graham), Universal Bell Correlations Do Not Exist.

We prove that there is no finite-alphabet nonlocal box that generates exactly those correlations that can be generated using a maximally entangled pair of qubits. More generally, we prove that if some finite-alphabet nonlocal box is strong enough to simulate arbitrary local projective measurements of a maximally entangled pair of qubits, then that nonlocal box cannot itself be simulated using any finite amount of entanglement. We also give a quantitative version of this theorem for approximate simulations, along with a corresponding upper bound.

Patrick Rall, Signed quantum weight enumerators characterize qubit magic state distillation.

Many proposals for fault-tolerant quantum computation require injection of ‘magic states’ to achieve a universal set of operations. Some qubit states are above a threshold fidelity, allowing them to be converted into magic states via ‘magic state distillation’, a process based on stabilizer codes from quantum error correction.
We define quantum weight enumerators that take into account the sign of the stabilizer operators. These enumerators completely describe the magic state distillation behavior when distilling T-type magic states. While it is straightforward to calculate them directly by counting exponentially many operator weights, it is also an NP-hard problem to compute them in general. This suggests that finding a family of distillation schemes with desired threshold properties is at least as hard as finding the weight distributions of a family of classical codes.
Additionally, we develop search algorithms fast enough to analyze all useful 5 qubit codes and some 7 qubit codes, finding no codes that surpass the best known threshold.

From the Spring 2019 iteration of the course

Ying-Hao Chen, 2-Local Hamiltonian with Low Complexity is QCMA-complete.

We prove that 2-Local Hamiltonian (2-LH) with Low Complexity problem is QCMA-complete by combining the results from the QMA-completeness of 2-LH and QCMA-completeness of 3-LH with Low Complexity. The idea is straightforward. It has been known that 2-LH is QMA-complete. By putting a low complexity constraint on the input state, we make the problem QCMA. Finally, we use similar arguments as in [Kempe, Kitaev, Regev] to show that all QCMA problems can be reduced to our proposed problem.

Jeremy Cook, On the relationships between Z-, C-, and H-local unitaries.

Quantum walk algorithms can speed up search of physical regions of space in both the discrete-time [arXiv:quant-ph/0402107] and continuous-time setting [arXiv:quant-ph/0306054], where the physical region of space being searched is modeled as a connected graph. In such a model, Aaronson and Ambainis [arXiv:quant-ph/0303041] provide three different criteria for a unitary matrix to act locally with respect to a graph, called Z-local, C-local, and H-local unitaries, and left the open question of relating these three locality criteria. Using a correspondence between continuous- and discrete-time quantum walks by Childs [arXiv:0810.0312], we provide a way to approximate N×N H-local unitaries with error δ using O(1/√δ,√NC-local unitaries, where the comma denotes the maximum of the two terms.

Joshua A. Cook, Approximating Unitary Preparations of Orthogonal Black Box States.

In this paper, I take a step toward answering the following question: for m different small circuits that compute m orthogonal n qubit states, is there a small circuit that will map m computational basis states to these m states without any input leaving any auxiliary bits changed. While this may seem simple, the constraint that auxiliary bits always be returned to 0 on any input (even ones besides the m we care about) led me to use sophisticated techniques. I give an approximation of such a unitary in the m = 2 case that has size polynomial in the approximation error, and the number of qubits n.

Sabee Grewal (project turned into a joint paper with me), Efficient Learning of Non-Interacting Fermion Distributions.

We give an efficient classical algorithm that recovers the distribution of a non-interacting fermion state over the computational basis. For a system of n non-interacting fermions and m modes, we show that O(m2n4log(m/δ)/ε4) samples and O(m4n4log(m/δ)/ε4) time are sufficient to learn the original distribution to total variation distance ε with probability 1−δ. Our algorithm empirically estimates the one- and two-mode correlations and uses them to reconstruct a succinct description of the entire distribution efficiently.

Sam Gunn and Niels Kornerup, Review of a Quantum Algorithm for Betti Numbers.

We looked into the algorithm for calculating Betti numbers presented by Lloyd, Garnerone, and Zanardi (LGZ). We present a new algorithm in the same spirit as LGZ with the intent of clarifying quantum algorithms for computing Betti numbers. Our algorithm is simpler and slightly more efficient than that presented by LGZ. We present a thorough analysis of our algorithm, pointing out reasons that both our algorithm and that presented by LGZ do not run in polynomial time for most inputs. However, the algorithms do run in polynomial time for calculating an approximation of the Betti number to polynomial multiplicative error, when applied to some class of graphs for which the Betti number is exponentially large.

William Kretschmer, Lower Bounding the AND-OR Tree via Symmetrization.

We prove a simple, nearly tight lower bound on the approximate degree of the two-level AND-OR tree using symmetrization arguments. Specifically, we show that ~deg(ANDm∘ORn)=Ω(~(mn)). To our knowledge, this is the first proof of this fact that relies on symmetrization exclusively; most other proofs involve the more complicated formulation of approximate degree as a linear program [BT13, She13, BDBGK18]. Our proof also demonstrates the power of a symmetrization technique involving Laurent polynomials (polynomials with negative exponents) that was previously introduced by Aaronson, Kothari, Kretschmer, and Thaler [AKKT19].

Jiahui Liu and Ruizhe Zhang (project turned into a joint paper with me, Mark Zhandry, and Qipeng Liu),
New Approaches for Quantum Copy-Protection.

Quantum copy protection uses the unclonability of quantum states to construct quantum software that provably cannot be pirated. Copy protection would be immensely useful, but unfortunately little is known about how to achieve it in general. In this work, we make progress on this goal, by giving the following results:
– We show how to copy protect any program that cannot be learned from its input/output behavior, relative to a classical oracle. This improves on Aaronson [CCC’09], which achieves the same relative to a quantum oracle. By instantiating the oracle with post-quantum candidate obfuscation schemes, we obtain a heuristic construction of copy protection.
– We show, roughly, that any program which can be watermarked can be copy detected, a weaker version of copy protection that does not prevent copying, but guarantees that any copying can be detected. Our scheme relies on the security of the assumed watermarking, plus the assumed existence of public key quantum money. Our construction is general, applicable to many recent watermarking schemes.

John Kallaugher, Triangle Counting in the Quantum Streaming Model. Not yet available but coming soon to an arXiv near you!

We give a quantum algorithm for counting triangles in graph streams that uses less space than the best possible classical algorithm.

10 Responses to “Long-delayed UT Austin Quantum Complexity Theory Student Project Showcase!”

  1. fred Says:

    Scott, what fraction of your students end up actually working in the field of quantum physics/computation after graduation? (as opposed to ending up in finance because they’re great at math)

  2. Scott Says:

    fred #1: The majority of students in Quantum Complexity Theory have gone on to do neither quantum computation nor finance, but some other kind of CS research (or physics, or in a few cases math or chemistry). I’m proud, of course, that some of the students (Shalev Ben-David, Adam Bouland, Shelby Kimmel, Matt Coudron, Henry Yuen, …) went on to be excellent quantum computing researchers, while others (like Paul Christiano) did amazing quantum computing research before switching to a different field. I don’t think it harmed the others to understand the basics of QC! 🙂

  3. Mostafa Touny Says:

    Thank you for sharing!
    I am wondering whether you recommend these students projects as an inspiration or a starting point, For other students.

    If you have a capacity, How can other students make the best of these?

  4. Scott Says:

    Mostafa Touny #3: I hope other students will make use of them by reading them and seeing whether they can tackle any of the implicit or explicit open problems, or otherwise push the results further!

  5. asdf Says:

    Henry Yuen is also one of the authors of the MIP*=RE paper, right? Wow, to think he got his start in your course. Has much been happening in the related research worlds (math or CS) since that paper came out?

    Here are some thoughts from an operator algebra blogger. I don’t understand much of it but maybe other people here do:


  6. William Gasarch Says:

    At one time it was thought to be a good thing to have your ugrad project and our PhD be in diff areas of (in our case) theoretical computer science. Good for broadening.

    This seems harder to do now as CS theory has gotten harder, so start up time is longer.

    I am sure that Scott’s ugrads who did work in quantum as ugrads and then went into something else benefited greatly from the quantum. They learned how to do research and of course they learned a ton of math.

  7. snoop Says:

    >> So please enjoy…

    papers on arxiv with hiphop music and rap wouldve been even more enjoyable

  8. JollyJoker Says:

    Maybe I shouldn’t ask questions that I’m unlikely to understand the answer to, but is the first paper by Hoza good evidence that the realism part of “local realism” is violated by QM? I got the idea that realist but nonlocal theories exist, at least de Broglie – Bohm, but there was some complexity argument against dB-B and more generally the idea of realist theories made Lubos Motl spew profanity.

  9. Scott Says:

    JollyJoker #8: Your question just inspired Aaronson’s Law (or one of them)—

      If you torture recent results in quantum information theory, demanding to know which interpretations of QM they’re “evidence for,” you’ll almost always end up disappointed — the poor results will either tearfully plead ignorance, or just say something random to get you to release them. 🙂
  10. JollyJoker Says:

    Scott #9: Nice! 🙂

Leave a Reply

Comment Policy: All comments are placed in moderation and reviewed prior to appearing. Comments can be left in moderation for any reason, but in particular, for ad-hominem attacks, hatred of groups of people, or snide and patronizing tone. Also: comments that link to a paper or article and, in effect, challenge me to respond to it are at severe risk of being left in moderation, as such comments place demands on my time that I can no longer meet. You'll have a much better chance of a response from me if you formulate your own argument here, rather than outsourcing the job to someone else. I sometimes accidentally miss perfectly reasonable comments in the moderation queue, or they get caught in the spam filter. If you feel this may have been the case with your comment, shoot me an email.

You can now use rich HTML in comments! You can also use basic TeX, by enclosing it within $$ $$ for displayed equations or \( \) for inline equations.