Format results
-
-
-
-
-
-
-
-
-
-
-
Resource dependence relations
Perimeter Institute for Theoretical Physics -
-
Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
FoxconnWe 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.
-
Complexity of Fermionic 2-SAT
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.
-
Low-overhead fault-tolerant quantum computing with high-rate qLDPC codes
Xian QuHigh-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.
-
A noncommuting charge puzzle
Shayan MajidyThe assumption that conserved quantities, also known as charges, commute underpins many basic physics derivations, such as that of the thermal state's form and Onsager coefficients. Yet, the failure of operators to commute plays a key role in quantum theory, e.g., underlying uncertainty relations. Recently, the study of systems with noncommuting charges has emerged as a growing subfield of quantum many-body physics and revealed a conceptual puzzle: noncommuting charges can hinder thermalization in some ways, yet promote it in others. In this talk, we address this puzzle in two distinct settings. First, we introduce noncommuting charges into monitored quantum circuits—a toolbox for studying entanglement dynamics. Numerical results reveal a critical phase with long-range entanglement, replacing the area-law phase typically observed in such circuits. This enhanced entanglement indicates noncommuting charges promote entanglement generation, which accompanies thermalization. Second, we consider systems with dynamical symmetries, which are known to violate the Eigenstate Thermalization Hypothesis (ETH), leading to non-stationary dynamics and preventing equilibration, let alone thermalization. We demonstrate that each pair of dynamical symmetries corresponds to a specific charge. Importantly, introducing new charges that do not commute with the existing charges disrupts the associated non-stationary dynamics, thereby facilitating thermalization. Together, these results shed light on the complex interplay between noncommuting charges, entanglement dynamics, and thermalization in quantum many-body systems. -
How to learn Pauli noise over a gate set
Senrui ChenUnderstanding 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.
-
Brownian Circuits and Quantum Randomness
Gregory BentsenAbstract: 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.
-
Black hole evaporation in random matrix theory (RMT) and statistical CFTs
Andrew RolphIn this talk, with two parts, I will first show how to capture both Hawking's non-unitary entropy curve and density matrix-connecting contributions that restore unitarity, in a toy RMT quantum system modelling black hole evaporation. The motivation is to find the simplest possible dynamical model that captures this aspect of gravitational physics. In the model, there is a dynamical phase transition in the averaging that connects the density matrices in a replica wormhole-like manner and restores unitarity in the entropy curve. In the second half of the talk, I will discuss ongoing follow-up work describing black hole evaporation and unitarity restoration in statistical descriptions of holographic CFTs. -
Constant-Overhead Magic State Distillation
Hayata YamasakiMagic state distillation is a crucial yet resource-intensive process in fault-tolerant quantum computation. The protocol’s overhead, defined as the number of input magic states required per output magic state with an error rate below ϵ, typically grows as O(log^γ (1/ϵ)) as ϵ → 0. Achieving smaller overheads, i.e., smaller exponents γ, is highly desirable; however, all existing protocols require polylogarithmically growing overheads with some γ > 0, and identifying the smallest achievable exponent γ for distilling magic states of qubits has remained challenging. To address this issue, we develop magic state distillation protocols for qubits with efficient, polynomial-time decoding that achieve an O(1) overhead, meaning the optimal exponent γ = 0; this improves over the previous best of γ ≈ 0.678 due to Hastings and Haah. In our construction, we employ algebraic geometry codes to explicitly present asymptotically good quantum codes for 2^10-dimensional qudits that support transversally implementable logical gates in the third level of the Clifford hierarchy. These codes can be realized by representing each 2^10-dimensional qudit as a set of 10 qubits, using stabilizer operations on qubits. We prove that the use of asymptotically good codes with non-vanishing rate and relative distance in magic state distillation leads to the constant overhead. The 10-qubit magic states distilled with these codes can be converted to and from conventional magic states for the controlled-controlled-Z (CCZ) and T gates on qubits with only a constant overhead loss, making it possible to achieve constant-overhead distillation of such standard magic states for qubits. These results resolve the fundamental open problem in quantum information theory concerning the construction of magic state distillation protocols with the optimal exponent. The talk is based on the following paper. https://arxiv.org/abs/2408.07764 -
Generalized Quantum Stein's Lemma and Second Law of Quantum Resource Theories
Hayata YamasakiThe second law of thermodynamics is the cornerstone of physics, characterizing the convertibility between thermodynamic states through a single function, entropy. Given the universal applicability of thermodynamics, a fundamental question in quantum information theory is whether an analogous second law can be formulated to characterize the convertibility of resources for quantum information processing by a single function. In 2008, a promising formulation was proposed, linking resource convertibility to the optimal performance of a variant of the quantum version of hypothesis testing. Central to this formulation was the generalized quantum Stein's lemma, which aimed to characterize this optimal performance by a measure of quantum resources, the regularized relative entropy of resource. If proven valid, the generalized quantum Stein's lemma would lead to the second law for quantum resources, with the regularized relative entropy of resource taking the role of entropy in thermodynamics. However, in 2023, a logical gap was found in the original proof of this lemma, casting doubt on the possibility of such a formulation of the second law. In this work, we address this problem by developing alternative techniques to successfully prove the generalized quantum Stein's lemma under a smaller set of assumptions than the original analysis. Based on our proof, we reestablish and extend the second law of quantum resource theories, applicable to both static resources of quantum states and a fundamental class of dynamical resources represented by classical-quantum (CQ) channels. These results resolve the fundamental problem of bridging the analogy between thermodynamics and quantum information theory. The talk is based on the following paper. https://arxiv.org/abs/2408.02722 -
Random unitaries in extremely low depth
Thomas SchusterRandom unitaries form the backbone of numerous components of quantum technologies, and serve as indispensable toy models for complex processes in quantum many-body physics. In all of these applications, a crucial consideration is in what circuit depth a random unitary can be generated. I will present recent work, in which we show that local quantum circuits can form random unitaries in exponentially lower circuit depths than previously thought. We prove that random quantum circuits on any geometry, including a 1D line, can form approximate unitary designs over n qubits in log n depth. In a similar manner, we construct pseudorandom unitaries (PRUs) in 1D circuits in poly log n depth, and in all-to-all-connected circuits in poly log log n depth. These shallow quantum circuits have low complexity and create only short-range entanglement, yet are indistinguishable from unitaries with exponential complexity. Applications of our results include proving that classical shadows with 1D log-depth Clifford circuits are as powerful as those with deep circuits, demonstrating superpolynomial quantum advantage in learning low-complexity physical systems, and establishing quantum hardness for recognizing phases of matter with topological order.
-
Resource dependence relations
Perimeter Institute for Theoretical PhysicsA resource theory imposes a preorder over states, with one state being above another if the first can be converted to the second by a free operation, and where the set of free operations defines the notion of resourcefulness under study. In general, the location of a state in the preorder of one resource theory can constrain its location in the preorder of a different resource theory. It follows that there can be nontrivial dependence relations between different notions of resourcefulness. In this talk, we lay out the conceptual and formal groundwork for the study of resource dependence relations. In particular, we note that the relations holding among a set of monotones that includes a complete set for each resource theory provides a full characterization of resource dependence relations. As an example, we consider three resource theories concerning the about-face asymmetry properties of a qubit along three mutually orthogonal axes on the Bloch ball, where about-face symmetry refers to a representation of $\mathbb{Z}_2$, consisting of the identity map and a $\pi$ rotation about the given axis. This example is sufficiently simple that we are able to derive a complete set of monotones for each resource theory and to determine all of the relations that hold among these monotones, thereby completely solving the problem of determining resource dependence relations. Nonetheless, we show that even in this simplest of examples, these relations are already quite nuanced. At the end of the talk, we will briefly discuss how to witness nonclassicality in quantum resource dependence relations and demonstrate it with the about-face asymmetry example. The talk is based on the preprint: arXiv:2407.00164 and ongoing work. -
Quantum metrology with correlated noise
I will present a universal numerical tool for identifying optimal adaptive metrological protocols in the presence of both uncorrelated and correlated noise [arXiv:2403.04854]. Leveraging a novel tensor network decomposition of quantum combs, the algorithm demonstrates efficiency even with a large number of channel uses (N=50). In the second part of the talk, I will explore the generalization of existing metrological upper bounds [Nat. Com. 3, 1063 (2012), PRL 131(9), 090801 (2023)] for correlated noise scenarios [arXiv:2410.01881].