Schedule for: 24w5259 - Fundamental Limitations to Quantum Computation

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Meet and Greet in BIRS Lounge (PDC 2nd floor)

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Meet in foyer of TCPL to participate in the BIRS group photo. The photograph will be taken outdoors, so dress appropriately for the weather. Please don't be late, or you might not be in the official group photo!

The vast majority of quantum states and unitaries have circuit complexity exponential in the number of qubits. In a similar vein, most of them also have exponential minimum description length, which makes it difficult to pinpoint examples of exponential complexity. In this work, we construct examples of constant description length but exponential circuit complexity. We provide infinite families such that each element requires an exponential number of two-qubit gates to be generated exactly from a product and where the same is true for the approximate generation of the vast majority of elements in the family. The results are based on sets of large transcendence degree and discussed for tensor networks, diagonal unitaries, and maximally coherent states.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

Quantum computers promise superior computational power over classical computers for some structured problems. While this insight is not new, only in recent years, steps have been taken to actually build intermediate-sized quantum devices, creating an exciting state of affairs. For some paradigmatic problems, there is some evidence that quantum computers may outperform classical devices [1]. For practically motivated problems in machine learning [2, 3] and in optimization [4], fault tolerant quantum computers indeed perform better than classical ones. While this may be promising, actual systems to date are relatively small and noisy. The main part of the talk is concerned with identifying *limitations* to quantum computing in this realm. We discuss notions of learnability of output distributions of short quantum circuits - as they can be seen as parts of variational quantum algorithms - and find that a single T-gate renders learning them hard [5]. We identify exponentially tighter bounds on limitations of quantum error mitigation [6]. We finally discuss the impact of non-unital noise on quantum computing, with quite unexpected results [7]. We end on the note that while fault tolerant quantum computers offer substantial computational benefits, the race is still open for near-term quantum devices. [1] Computational advantage of quantum random sampling, D. Hangleiter, J. Eisert, Rev. Mod. Phys. 95, 035001 (2023). [2] A super-polynomial quantum-classical separation for density modelling, N. Pirnay, R. Sweke, J. Eisert, J.-P. Seifert, Phys. Rev. A 107, 042416 (2023). [3] Towards provably efficient quantum algorithms for large-scale machine-learning models, J. Liu, M. Liu, J.-P. Liu, Z. Ye, Y. Wang, Y. Alexeev, J. Eisert, L. Jiang, Nature Comm. 15, 434 (2024). [4] An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory, N. Pirnay, V. Ulitzsch, F. Wilde, J. Eisert, J.-P. Seifert, arXiv:2212.08678, Science Advances (2024). [5] A single T-gate makes distribution learning hard, M. Hinsche, M. Ioannou, A. Nietner, J. Haferkamp, Y. Quek, D. Hangleiter, J.-P. Seifert, J. Eisert, R. Sweke, Phys. Rev. Lett. 130, 240602 (2023). [6] Exponentially tighter bounds on limitations of quantum error mitigation, Y. Quek, D. Stilck França, S. Khatri, J. Jakob Meyer, J. Eisert, arXiv:2210.11505, Nature Physics (2024). [7] Non-unital noise, friend of foe, A. A. Mele, A. Angrisani, A Ghosh, A. Khatri, J. Eisert, Y. Quek, D. Stilck Franca, in preparation (2024).

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

Quantum metrology studies estimation of unknown parameters in quantum systems. The Heisenberg limit of estimation precision 1/N, with N being the number of probes or time steps, is the ultimate sensing limit allowed by quantum mechanics that quadratically outperforms the classically-achievable standard quantum limit 1/√N. The Heisenberg limit is attainable in the noiseless case, but in presence of noise, many quantum systems only allow a constant factor of improvement over the standard quantum limit. To elucidate the noise effect in quantum metrology, we first show a necessary and sufficient condition for achieving the Heisenberg limit using quantum controls. When the condition is satisfied, there exist quantum error correction protocols that achieve the Heisenberg limit. Then we discuss the modified sensing limits when only restricted types of quantum controls can be applied.

In our work we introduce a construction that takes as input an arbitrary CSS stabilizer code and outputs a topological CSS code that is local in dimension $D=3$. The code parameters of the input and output codes are mapped as follows \begin{align} {[[n,k,d]] \mapsto [[\Theta(nn_Xn_Z),k,\Omega(\frac{1}{w}d \min(n_X,n_Z))]],} \end{align} where $n_X$ is the number of $X$ checks, $n_Z$ the number of $Z$ checks, and $w$ the maximum weight of the checks in the input code. When applied to a family of good CSS LDPC codes our construction outputs a family of topological CSS codes that achieve optimal scaling of the code parameters for $D=3$, that is \begin{align} {[[L,\Theta(L),\Theta(L)]] \mapsto [[\Theta(L^3),\Theta(L),\Theta(L^2)]].} \end{align} which saturates exactly the BPT bounds in 3D. Further, our codes exhibit an optimal $\Theta(L)$ energy barrier.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

I will discuss examples of additivity and nonadditivity of quantum capacities. On the additivity side, I will introduce a sufficient criterion for additivity of coherent information, informational degradability, that is apparently more general than degradability. I will present a particular non-degradable channel that I believe is informationally degradable. On the non-additivity side, I will show that the platypus channel displays nonadditivity with many different qubit channels, such as erasure, amplitude damping, and depolarizing. I will also explain the spin alignment conjecture, which would imply that the platypus has additive coherent information with itself.

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

It is a difficult problem to engineer natural unitary evolutions that evolve a quantum system to a state with some given desired properties. Variational quantum algorithms (VQAs) provide one such approach, where the desired state is the ground state of a quantum many-body Hamiltonian. Other examples can be given by quantum states with specific equilibration properties. We formalize such statements in terms of computational complexity. Optimizing the parameters in VQAs is NP-hard, and approximating the optimal VQA circuit depths is QCMA-hard. This talk focuses on extending such hardness statements toward continuous time evolution: maximizing quantum expectation values over time is NEXP-hard. This result provides arguably the first natural NEXP-hard problem and, as a corollary, formalizes further limitations of VQAs. Moreover, it allows us to partially capture the complexity of equilibration properties of quantum many-body systems.

Coauthors: Andrew Childs, Honghao Fu, Zhi Li, Maris Ozols, Vedang Vyas Source: arXiv:2309.16387

Lunch is served daily between 11:30am and 1:30pm in the Vistas Dining Room, the top floor of the Sally Borden Building.

We formulate the phase space of molecular rotational and nuclear-spin states. Taking in molecular geometry and nuclear-spin data, our framework yields admissible position and momentum states, inter-convertible via a generalized Fourier transform. We classify molecules into three types — asymmetric, rotationally symmetric, and perrotationally symmetric — with the last type having no macroscopic analogue due to nuclear-spin statistics constraints. We identify two features in perrotationally symmetric state spaces that are Hamiltonian-independent and induced solely by symmetry and spin statistics. First, many molecular species are intrinsically rotation-spin entangled in a way that cannot be broken without transitioning to another species. Second, adiabatic changes in position realize naturally robust operations in the form of an Abelian or even non-Abelian monodromy, akin to what is achieved by braiding anyonic quasiparticles or realizing fault-tolerant quantum gates.

Strengthenings of the data processing inequality are a useful tool in determining the limitations of quantum architectures. A common tool of choice are contraction coefficients. In this talk I will discuss recent results on the structure of these coefficients for quantum f-divergences. Here we are utilizing a recent definition of f-divergences based on integral representations. These include commonly used quantities as special cases, e.g. the relative entropy. For example we discuss the special role of the chi2 divergence and operator convex functions f. We will see that these tools give a wide range of possibilities to work with contraction coefficients and use them in proofs. Finally, we discuss upper bounds on contraction coefficients, in terms of the trace distance and a new quantity, the quantum Doeblin coefficient.

Preparing thermal and ground states is an essential quantum algorithmic task for quantum simulation. In this work, we construct the first efficiently implementable and exactly detailed-balanced Lindbladian for Gibbs states of arbitrary noncommutative Hamiltonians. Our construction can also be regarded as a continuous-time quantum analog of the Metropolis-Hastings algorithm. To prepare the quantum Gibbs state, our algorithm invokes Hamiltonian simulation for a time proportional to the mixing time and the inverse temperature β, up to polylogarithmic factors. Moreover, the gate complexity reduces significantly for lattice Hamiltonians as the corresponding Lindblad operators are (quasi-) local (with radius ∼β) and only depend on local Hamiltonian patches. Meanwhile, purifying our Lindbladians yields a temperature-dependent family of frustration-free "parent Hamiltonians", prescribing an adiabatic path for the canonical purified Gibbs state (i.e., the Thermal Field Double state). These favorable features suggest that our construction is the ideal quantum algorithmic counterpart of classical Markov chain Monte Carlo sampling.

A buffet dinner is served daily between 5:30pm and 7:30pm in Vistas Dining Room, top floor of the Sally Borden Building.

Breakfast is served daily between 7 and 9am in the Vistas Dining Room, the top floor of the Sally Borden Building.

The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation stating that arbitrarily long quantum computations can be performed with a polylogarithmic overhead provided the noise level is below a constant level. A recent work by Fawzi, Grospellier and Leverrier (FOCS 2018) building on a result by Gottesman (QIC 2013) has shown that the space overhead can be asymptotically reduced to a constant independent of the circuit provided we only consider circuits with a length bounded by a polynomial in the width. In this work, using a minimal model for quantum fault tolerance, we establish a general lower bound on the space overhead required to achieve fault tolerance. For any non-unitary qubit channel N and any quantum fault tolerance schemes against i.i.d. noise modeled by N, we prove a lower bound of max{Q(N)−1n,αNlogT} on the number of physical qubits, for circuits of length T and width n. Here, Q(N) denotes the quantum capacity of N and αN>0 is a constant only depending on the channel N. In our model, we allow for qubits to be replaced by fresh ones during the execution of the circuit and we allow classical computation to be free and perfect. This improves upon results that assumed classical computations to be also affected by noise, and that sometimes did not allow for fresh qubits to be added. Along the way, we prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude damping noise resolving a conjecture by Ben-Or, Gottesman, and Hassidim (2013).

5-day workshop participants are welcome to use BIRS facilities (TCPL ) until 3 pm on Friday, although participants are still required to checkout of the guest rooms by 11AM.

The output distributions of random quantum circuits are candidates for multiple applications ranging from quantum supremacy experiments to generative modeling. We show that several desirable properties of these output distributions can be proven using a surprisingly strong concentration inequality for the p-norms via unitary 2p-designs. In particular, we show the following results for random quantum circuits of linear depth: 1) the output distributions are far from uniform in total variation distance as conjectured by Aaronson and Chen, 2) most output distributions are hard to distinguish from the uniform distribution using statistical queries and 3) that output distributions satisfy the linear cross entropy benchmark with high probability. We will discuss directions for future research towards understanding the behavior of output distributions of random quantum circuits under noise.