QuICS Contributes Half a Dozen Papers to Top Quantum Information Conference

Research from the Joint Center for Quantum Information and Computer Science (QuICS) will be presented during six accepted talks at this year’s Quantum Information Processing (QIP) conference, the premiere annual conference for quantum information research. This year marks the 26th annual QIP, which will be hosted by Ghent University in Belgium Feb. 4–10.

QuICS Fellows, postdoctoral researchers, graduate students, and alumni contributed to the research selected for talks, and their work will be featured alongside more than 100 other accepted talks.

“QIP is at the leading edge of quantum information science,” said QuICS Co-Director Yi-Kai Liu. “Often, you hear about new theoretical ideas there, and then a few years later, you read about their experimental realization in journals like Science and Nature. QIP is like a window into the future, and it’s great to see so many QuICS people there.”

QuICS graduate students Matt Kovacs-Deak and Daochen Wang, together with QuICS Fellow and Co-Director Andrew Childs, former Hartree Postdoctoral Fellow Aarthi Sundaram and a colleague, will present a novel framework for quantum divide-and-conquer algorithms. Conventional divide-and-conquer algorithms break a problem apart into smaller chunks that can be tackled independently and then combined to produce an answer to the original problem. The approach works for a wide variety of problems and is a mainstay of algorithm design.

Kovacs-Deak, Wang and their collaborators show that there is a quantum analog of divide and conquer that achieves some known quantum speedups and even unlocks new speedups. In particular, the team applied their quantum divide-and-conquer approach to the longest common subsequence problem, which, given two sequences (imagine numerical digits or letters), seeks to find the longest string of characters shared between them. Among other results, the team proved that quantum divide and conquer can find a solution to the longest common subsequence problem polynomially faster than previously known quantum (or classical) algorithms.

In another talk, QuICS graduate student Adam Ehrenberg and QuICS postdoctoral researcher Christopher Baldwin, together with QuICS Fellow Alexey Gorshkov, former QuICS graduate student Abhinav Deshpande and a colleague, will share their results studying the complexity of simulating quantum systems with classical computers. They discovered a transition in how hard it is to simulate particular quantum systems—those that tend to very slowly lose any memory of their initial conditions through a process called many-body localization.

Beyond a short-time regime where classical techniques can simulate these quantum systems efficiently, the researchers found that there are two other regimes: an intermediate regime that can be simulated classically in subexponential time and a hard regime. This hard regime arises after the quantum system runs for a long time (exponentially long in the system size), then classical algorithms can no longer keep up. They used their result to prove a bound on the quantum complexity of simulating many-body localized systems, providing context for some of the hallmark features of these systems, like their sluggishness in spreading quantum entanglement.

QuICS graduate student Xuchen You, QuICS Fellow Xiaodi Wu, former QuICS graduate student Shouvanik Chakrabarti and a colleague will present their new study of variational quantum eigensolvers (VQEs), which provide a method for finding the lowest energy state of a quantum system. Given an initial state and a system of interest, a VQE is an optimization algorithm that identifies a quantum operator that maps the initial state to the approximate ground state of the system. VQEs are an active area of study because of their near-term applications to noisy intermediate-scale quantum (NISQ) devices.

You and colleagues studied how quickly VQEs home in on an answer. In particular, they studied overparameterized VQEs—a situation in which the number of parameters that the optimization can tweak is larger than the dimension of the quantum state space. They proved that VQEs have an overparameterization threshold, past which they converge exponentially quickly. They go on to prove systems with a lower overparameterization threshold require fewer parameters to guarantee convergence and that all of these results hold independent of the chosen initial state. They also show that in certain circumstances the threshold can actually be much smaller than the dimension of the quantum state space—a useful metric for evaluating the choice of particular initial states for particular problems.

In a fourth talk, QuICS graduate student Joseph Iosue, QuICS Fellows Victor Albert and Michael Gullans, and former QuICS Hartree Postdoctoral Fellow Kunal Sharma will discuss their pioneering paper on continuous-variable quantum state designs. Designs are a statistical tool that provide a way to calculate the average of a polynomial function over a set of points in an abstract space. In general, a t-design is a set of points that can act as a kind of stand-in for the entire space: Averages of polynomial functions with degree less than t taken over the points in the t-design will be the same as averages taken over a uniform distribution of the underlying space.

There are quantum analogs to t-designs, where the points in the t-design are states in a quantum Hilbert space, but up until now they have only been useful for finite-dimensional quantum systems. For infinite-dimensional systems with degrees of freedom represented by continuous variables, like the modes of an electromagnetic field or of a quantum harmonic oscillator, earlier work showed that particular collections of quantum states didn’t form 2-designs. In the new paper, the authors extend this result to show that t-designs (for t ≥ 2) do not exist for these continuous-variable spaces, but they explore relaxing some of the assumptions of that proof and examine the utility of what they call rigged t-designs for quantum information.

Two other papers co-authored by current QuICS researchers will be presented at QIP this year and include results on topological quantum codes and quantum sampling algorithms.

A full list of the QuICS papers accepted at QIP 2023 is below.

Quantum divide and conquer, Andrew Childs, Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram and Daochen Wang

A Convergence Theory for Over-parameterized Variational Quantum Eigensolvers, Xuchen You, Shouvanik Chakrabarti, Boyang Chen and Xiaodi Wu

Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants, Andrew M. Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang and Ruizhe Zhang

Circuit complexity and classical simulation of Many-Body Localized Systems, Adam Ehrenberg, Abhinav Deshpande, Christopher L. Baldwin, Dmitry A. Abanin and Alexey V. Gorshkov

Continuous-variable quantum state designs: theory and applications, Joseph Iosue, Kunal Sharma, Michael Gullans and Victor Albert

Pauli topological codes from Abelian anyon theories, Tyler Ellison, Yu-An Chen, Arpit Dua, Wilbur Shirley, Nathanan Tantivasadakarn and Dominic Williamson

—Story by Chris Cesare