Quantum Information

Assuming the polynomial hierarchy is infinite, we prove a sufficient condition for determining if uniform and polynomial size quantum circuits over a non-universal gate set are not efficiently classically simulable in the weak multiplicative sense. Our criterion exploits the fact that subgroups of SL(2; C) are essentially either discrete or dense in SL(2; C). Using our criterion, we give a new proof that both instantaneous quantum polynomial (IQP) circuits and conjugated Clifford circuits (CCCs) afford a quantum advantage. We also prove that both commuting CCCs and CCCs over various fragments of the Clifford group afford a quantum advantage, which settles two questions of Bouland, Fitzsimons, and Koh. Our results imply that circuits made of just U \otimes U-conjugated CZ gates afford a quantum advantage for almost all single-qubit unitaries U.

I will present a unified framework for understanding the statistics and anomalies of excitations—ranging from particles to higher-dimensional objects—in quantum lattice systems. We introduce a general method to compute the quantized statistics of Abelian excitations in arbitrary dimensions via Berry phases of locality-preserving symmetry operations, uncovering novel statistics for membrane excitations. These statistics correspond to quantum anomalies of generalized global symmetries and imply obstructions to gauging, enforcing long-range entanglement. In particular, we show that anomalous higher-form symmetries enforce intrinsic long-range entanglement, meaning that fidelity with any SRE states must exhibit exponential decay, unlike ordinary (0-form) symmetry anomalies. As an application, we identify a new example of (3+1)D mixed-state topological order with fermionic loop excitations, characterized by a breakdown of remote detectability linked to higher-form symmetry anomalies.

We present a tensor-network-based classical algorithm (equipped with guarantees) for simulating $n$-qubit quantum circuits with arbitrary single-qubit noise. Our algorithm represents the state of a noisy quantum system by a particular ensemble of matrix product states from which we stochastically sample a pure quantum state. Each single qubit noise process acting on a pure state is then represented by the ensemble of states that achieve the minimal average entanglement (the entanglement of formation) between the noisy qubit and the rest of the system. This approach provides a connection between the entanglement of formation and the accuracy of the simulation algorithm. For a given maximum bond dimension $\chi$ and circuit, our algorithm comes with an upper bound on the simulation error (in total variation distance), runs in $poly(n,\chi)$-time and improves upon related prior work (1) in scope: by extending from the three commonly considered noise models to general single qubit noise (2) in performance: by employing a state-dependent locally-entanglement-optimal unraveling and (3) in conceptual contribution: by showing that the fixed unraveling used in prior work becomes equivalent to our choice of unraveling in the special case of depolarizing and dephasing noise acting on a maximally entangled state. This is joint work with Simon Cichy, Paul K. Faehrmann, Lennart Bittel and Jens Eisert.

In this talk, I will discuss the complexity of a fermionic analogue of Quantum k-SAT. In this Fermionic k-SAT problem, one is given the task to decide whether there is a fermionic state in the null-space of a collection of fermionic, parity-conserving, projectors on n fermionic modes, where each fermionic projector involves at most k fermionic modes. We prove that this problem can be solved efficiently classically for k = 2. In addition, we show that deciding whether there exists a satisfying assignment with a given fixed particle number parity can also be done efficiently classically for Fermionic 2-SAT: this problem is a quantum-fermionic extension of asking whether a classical 2-SAT problem has a solution with a given Hamming weight parity. We also prove that deciding whether there exists a satisfying assignment for particle-number-conserving Fermionic 2-SAT for some given particle number is NP-complete. Complementary to this, we show that Fermionic 9-SAT is QMA_1-hard. 

High-rate quantum low-density parity-check (qLDPC) codes offer significantly lower encoding overhead compared to their topological counterparts by relaxing locality constraints. However, achieving full-fledged logical computation with these codes in physical systems with low space-time costs remains a formidable challenge. In the first part of this talk, I will provide an overview of recent advancements in implementing qLDPC codes as quantum memories on realistic platforms, such as reconfigurable atom arrays. Next, I will present a new scheme for performing parallelizable and locally addressable logical operations on homological product codes. This scheme extends the transversal CNOT gate from two identical CSS codes to two distinct, yet structurally similar, qLDPC codes, enabling efficient local addressing of collectively encoded information. We demonstrate that this approach achieves lower overhead in not only the space- but also the overall space-time overhead compared to surface-code-based computations. Finally, I will discuss new strategies for achieving highly space-time-efficient computations with qLDPC codes by leveraging algorithm-specific fault tolerance, designing tailored protocols for structured quantum algorithms.

Understanding quantum noise is an essential step towards building practical quantum information processing systems. Pauli noise is a useful model widely applied in quantum benchmarking, quantum error mitigation, and quantum error correction. Despite previous research, the problem of how to learn a Pauli noise model self-consistently, completely, and efficiently has remained open. In this talk, I will introduce a framework of gate-set Pauli noise learning that aims at addressing this problem. The framework treats initialization, measurement, and a set of quantum gates to suffer from unknown Pauli noise channels, which are allowed to have customized locality constraints. The goal is to learn all the Pauli noise channels using only those noisy operations. I will first introduce a theory on the “learnability” of Pauli noise model, i.e., what information is fundamentally identifiable within the model and what is not. This is established using tools from algebraic graph theory and ideas from gate set tomography; I will then discuss a sample-efficient procedure to learn all learnable information of a Paul noise model to any desired precision; Finally, I will demonstrate how to apply our theoretic framework for concrete practical gate set and noise assumptions, and discuss the potential impact on quantum error mitigation and other applications.

Abstract: Randomness is a powerful resource for information-processing applications. For example, classical randomness is essential for modern information security and underpins many cryptographic schemes. Similarly, quantum randomness can protect quantum information against noise or eavesdroppers who wish to access or manipulate that information. These observations raise a set of related questions: How quickly and efficiently can we generate quantum randomness? How much quantum randomness is necessary for a given task? What can we use quantum randomness for? In this talk, I address these questions using all-to-all Brownian circuits, a family of random quantum circuits for which exact results can often be obtained via mean-field theory. I will first demonstrate that all-to-all Brownian circuits form k-designs in a time that scales linearly with k. I will then discuss how these circuits can be applied to study Heisenberg-limited metrology and quantum advantage. In particular, I will discuss a time-reversal protocol that can achieve Heisenberg-limited precision in cavity QED and trapped ion setups; I will also discuss the application of these circuits to studying classical spoofing algorithms for the linear cross-entropy benchmark, a popular measure of quantum advantage.