Agnostic Phase Estimation - Xingrui Song; Flavio Salvati; Chandrashekhar Gaikwad; Nicole Yunger Halpern; David R. M. Arvidsson-Shukur; Kater Murch (2024)
The goal of quantum metrology is to improve measurements' sensitivities by harnessing quantum resources. Metrologists often aim to maximize the quantum Fisher information, which bounds the measurement setup's sensitivity. In studies of fundamental limits on metrology, a paradigmatic setup features a qubit (spin-half system) subject to an unknown rotation. One obtains the maximal quantum Fisher information about the rotation if the spin begins in a state that maximizes the variance of the rotation-inducing operator. If the rotation axis is unknown, however, no optimal single-qubit sensor can be prepared. Inspired by simulations of closed timelike curves, we circumvent this limitation. We obtain the maximum quantum Fisher information about a rotation angle, regardless of the unknown rotation axis. To achieve this result, we initially entangle the probe qubit with an ancilla qubit. Then, we measure the pair in an entangled basis, obtaining more information about the rotation angle than any single-qubit sensor can achieve. We demonstrate this metrological advantage using a two-qubit superconducting quantum processor. Our measurement approach achieves a quantum advantage, outperforming every entanglement-free strategy.

Average Rényi Entanglement Entropy in Gaussian Boson Sampling - Jason Youm; Joseph T. Iosue; Adam Ehrenberg; Yu-Xin Wang; Alexey V. Gorshkov (2024)
Recently, many experiments have been conducted with the goal of demonstrating a quantum advantage over classical computation. One popular framework for these experiments is Gaussian Boson Sampling, where quadratic photonic input states are interfered via a linear optical unitary and subsequently measured in the Fock basis. In this work, we study the modal entanglement of the output states in this framework just before the measurement stage. Specifically, we compute Page curves as measured by various Rényi-α entropies, where the Page curve describes the entanglement between two partitioned groups of output modes averaged over all linear optical unitaries. We derive these formulas for α=1 (i.e. the von Neumann entropy), and, more generally, for all positive integer α, in the asymptotic limit of infinite number of modes and for input states that are composed of single-mode-squeezed-vacuum state with equal squeezing strength. We then analyze the limiting behaviors when the squeezing is small and large. Having determined the averages, we then explicitly calculate the Rényi-α variance for integers α>1, and we are able to show that these entropies are weakly typical.

Beatty Sequences for a Quadratic Irrational: Decidability and Applications - Luke Schaeffer; Jeffrey Shallit; Stefan Zorcic (2024)
Let α and β belong to the same quadratic field. We show that the inhomogeneous Beatty sequence (⌊nα+β⌋)n≥1 is synchronized, in the sense that there is a finite automaton that takes as input the Ostrowski representations of n and y in parallel, and accepts if and only if y=⌊nα+β⌋. Since it is already known that the addition relation is computable for Ostrowski representations based on a quadratic number, a consequence is a new and rather simple proof that the first-order logical theory of these sequences with addition is decidable. The decision procedure is easily implemented in the free software Walnut.  As an application, we show that for each r≥1 it is decidable whether the set {⌊nα+β⌋:n≥1} forms an additive basis (or asymptotic additive basis) of order r. Using our techniques, we also solve some open problems of Reble and Kimberling, and give an explicit characterization of a sequence of Hildebrand et al.

A Case for Synthesis of Recursive Quantum Unitary Programs - Deng, Haowei; Tao, Runzhou; Peng, Yuxiang; Wu, Xiaodi (Proceedings of the ACM on Programming Languages, 2024)
Quantum programs are notoriously difficult to code and verify due to unintuitive quantum knowledge associated with quantum programming. Automated tools relieving the tedium and errors associated with low-level quantum details would hence be highly desirable. In this paper, we initiate the study of program synthesis for quantum unitary programs that recursively define a family of unitary circuits for different input sizes, which are widely used in existing quantum programming languages. Specifically, we present QSynth, the first quantum program synthesis framework, including a new inductive quantum programming language, its specification, a sound logic for reasoning, and an encoding of the reasoning procedure into SMT instances. By leveraging existing SMT solvers, QSynth successfully synthesizes ten quantum unitary programs including quantum adder circuits, quantum eigenvalue inversion circuits and Quantum Fourier Transformation, which can be readily transpiled to executable programs on major quantum platforms, e.g., Q#, IBM Qiskit, and AWS Braket.

Clifford-Deformed Surface Codes - Dua, Arpit; Kubica, Aleksander; Jiang, Liang; Flammia, Steven T.; Michael Gullans (PRX Quantum, 2024)
Various realizations of Kitaev's surface code perform surprisingly well for biased Pauli noise. Attracted by these potential gains, we study the performance of Clifford-deformed surface codes (CDSCs) obtained from the surface code by applying single-qubit Clifford operators. We first analyze CDSCs on the 3×3 square lattice and find that, depending on the noise bias, their logical error rates can differ by orders of magnitude. To explain the observed behavior, we introduce the effective distance d′, which reduces to the standard distance for unbiased noise. To study CDSC performance in the thermodynamic limit, we focus on random CDSCs. Using the statistical mechanical mapping for quantum codes, we uncover a phase diagram that describes random CDSC families with 50% threshold at infinite bias. In the high-threshold region, we further demonstrate that typical code realizations outperform the thresholds and subthreshold logical error rates, at finite bias, of the best-known translationally invariant codes. We demonstrate the practical relevance of these random CDSC families by constructing a translation-invariant CDSC belonging to a high-performance random CDSC family. We also show that our translation-invariant CDSC outperforms well-known translation-invariant CDSCs such as the XZZX and XY codes.

Complexity-constrained quantum thermodynamics - Anthony Munson; Naga Bhavya Teja Kothakonda; Jonas Haferkamp; Nicole Yunger Halpern; Jens Eisert; Philippe Faist (2024)
Quantum complexity measures the difficulty of realizing a quantum process, such as preparing a state or implementing a unitary. We present an approach to quantifying the thermodynamic resources required to implement a process if the process's complexity is restricted. We focus on the prototypical task of information erasure, or Landauer erasure, wherein an n-qubit memory is reset to the all-zero state. We show that the minimum thermodynamic work required to reset an arbitrary state, via a complexity-constrained process, is quantified by the state's complexity entropy. The complexity entropy therefore quantifies a trade-off between the work cost and complexity cost of resetting a state. If the qubits have a nontrivial (but product) Hamiltonian, the optimal work cost is determined by the complexity relative entropy. The complexity entropy quantifies the amount of randomness a system appears to have to a computationally limited observer. Similarly, the complexity relative entropy quantifies such an observer's ability to distinguish two states. We prove elementary properties of the complexity (relative) entropy and determine the complexity entropy's behavior under random circuits. Also, we identify information-theoretic applications of the complexity entropy. The complexity entropy quantifies the resources required for data compression if the compression algorithm must use a restricted number of gates. We further introduce a complexity conditional entropy, which arises naturally in a complexity-constrained variant of information-theoretic decoupling. Assuming that this entropy obeys a conjectured chain rule, we show that the entropy bounds the number of qubits that one can decouple from a reference system, as judged by a computationally bounded referee. Overall, our framework extends the resource-theoretic approach to thermodynamics to integrate a notion of time, as quantified by complexity.

Complexity-constrained quantum thermodynamics - Anthony Munson; Naga Bhavya Teja Kothakonda; Jonas Haferkamp; Nicole Yunger Halpern; Jens Eisert; Philippe Faist (2024)
Quantum complexity measures the difficulty of realizing a quantum process, such as preparing a state or implementing a unitary. We present an approach to quantifying the thermodynamic resources required to implement a process if the process's complexity is restricted. We focus on the prototypical task of information erasure, or Landauer erasure, wherein an n-qubit memory is reset to the all-zero state. We show that the minimum thermodynamic work required to reset an arbitrary state, via a complexity-constrained process, is quantified by the state's complexity entropy. The complexity entropy therefore quantifies a trade-off between the work cost and complexity cost of resetting a state. If the qubits have a nontrivial (but product) Hamiltonian, the optimal work cost is determined by the complexity relative entropy. The complexity entropy quantifies the amount of randomness a system appears to have to a computationally limited observer. Similarly, the complexity relative entropy quantifies such an observer's ability to distinguish two states. We prove elementary properties of the complexity (relative) entropy and determine the complexity entropy's behavior under random circuits. Also, we identify information-theoretic applications of the complexity entropy. The complexity entropy quantifies the resources required for data compression if the compression algorithm must use a restricted number of gates. We further introduce a complexity conditional entropy, which arises naturally in a complexity-constrained variant of information-theoretic decoupling. Assuming that this entropy obeys a conjectured chain rule, we show that the entropy bounds the number of qubits that one can decouple from a reference system, as judged by a computationally bounded referee. Overall, our framework extends the resource-theoretic approach to thermodynamics to integrate a notion of time, as quantified by complexity.

Continuous-Variable Quantum State Designs: Theory and Applications - Iosue, Joseph T.; Sharma, Kunal; Michael Gullans; Albert, Victor V. (Phys. Rev. X, 2024)
We generalize the notion of quantum state designs to infinite-dimensional spaces. We first prove that, under the definition of continuous-variable (CV) state t-designs from [Blume-Kohout et al., Commun. Math. Phys. 326, 755 (2014)], no state designs exist for t≥2. Similarly, we prove that no CV unitary t-designs exist for t≥2. We propose an alternative definition for CV state designs, which we call rigged t-designs, and provide explicit constructions for t = 2. As an application of rigged designs, we develop a design-based shadow-tomography protocol for CV states. Using energy-constrained versions of rigged designs, we define an average fidelity for CV quantum channels and relate this fidelity to the CV entanglement fidelity. As an additional result of independent interest, we establish a connection between torus 2-designs and complete sets of mutually unbiased bases.

Efficient and practical Hamiltonian simulation from time-dependent product formulas - Jan Lukas Bosse; Andrew M. Childs; Charles Derby; Filippo Maria Gambetta; Ashley Montanaro; Raul A. Santos (2024)
In this work we propose an approach for implementing time-evolution of a quantum system using product formulas. The quantum algorithms we develop have provably better scaling (in terms of gate complexity and circuit depth) than a naive application of well-known Trotter formulas, for systems where the evolution is determined by a Hamiltonian with different energy scales (i.e., one part is "large" and another part is "small"). Our algorithms generate a decomposition of the evolution operator into a product of simple unitaries that are directly implementable on a quantum computer. Although the theoretical scaling is suboptimal compared with state-of-the-art algorithms (e.g., quantum signal processing), the performance of the algorithms we propose is highly competitive in practice. We illustrate this via extensive numerical simulations for several models. For instance, in the strong-field regime of the 1D transverse-field Ising model, our algorithms achieve an improvement of one order of magnitude in both the system size and evolution time that can be simulated with a fixed budget of 1000 arbitrary 2-qubit gates, compared with standard Trotter formulas.

Efficiently verifiable quantum advantage on near-term analog quantum simulators - Zhenning Liu; Dhruv Devulapalli; Dominik Hangleiter; Yi-Kai Liu; Alicia J. Kollár; Alexey V. Gorshkov; Andrew M. Childs (2024)
Existing schemes for demonstrating quantum computational advantage are subject to various practical restrictions, including the hardness of verification and challenges in experimental implementation. Meanwhile, analog quantum simulators have been realized in many experiments to study novel physics. In this work, we propose a quantum advantage protocol based on single-step Feynman-Kitaev verification of an analog quantum simulation, in which the verifier need only run an O(λ2)-time classical computation, and the prover need only prepare O(1) samples of a history state and perform O(λ2) single-qubit measurements, for a security parameter λ. We also propose a near-term feasible strategy for honest provers and discuss potential experimental realizations.

Encoding Majorana codes - Maryam Mudassar; Riley W. Chien; Daniel Gottesman (2024)
To implement a quantum error correction protocol, we first need a scheme to prepare our state in the correct subspace of the code, and this can be done using a unitary encoding circuit. Majorana codes are special since any gates that transform such codes must preserve fermionic parity. In this paper, we present an algorithm that uses the stabilizer matrix to compute unitary encoding circuits for Majorana codes. We present two approaches, both of which use a version of Gaussian elimination with row operations replaced with elementary fermionic Clifford operations. One approach uses an additional ancilla mode and works for all Majorana stabilizer codes, while the second approach does not use ancilla but does not work if the total parity is inside the stabilizer group.

Error Correction in Dynamical Codes - Xiaozhen Fu; Daniel Gottesman (2024)
We ask what is the general framework for a quantum error correcting code that is defined by a sequence of measurements. Recently, there has been much interest in Floquet codes and space-time codes. In this work, we define and study the distance of a dynamical code. This is a subtle concept and difficult to determine: At any given time, the system will be in a subspace which forms a quantum error-correcting code with a given distance, but the full error correction capability of that code may not be available due to the schedule of measurements associated with the code. We address this challenge by developing an algorithm that tracks information we have learned about the error syndromes through the protocol and put that together to determine the distance of a dynamical code, in a non-fault-tolerant context. We use the tools developed for the algorithm to analyze the initialization and masking properties of a generic Floquet code. Further, we look at properties of dynamical codes under the constraint of geometric locality with a view to understand whether the fundamental limitations on logical gates and code parameters imposed by geometric locality for traditional codes can be surpassed in the dynamical paradigm. We find that codes with a limited number of long range connectivity will not allow non-Clifford gates to be implemented with finite depth circuits in the 2D setting.

Estimation of Hamiltonian parameters from thermal states - Luis Pedro García-Pintos; Kishor Bharti; Jacob Bringewatt; Hossein Dehghani; Adam Ehrenberg; Nicole Yunger Halpern; Alexey V. Gorshkov (2024)
We upper- and lower-bound the optimal precision with which one can estimate an unknown Hamiltonian parameter via measurements of Gibbs thermal states with a known temperature. The bounds depend on the uncertainty in the Hamiltonian term that contains the parameter and on the term's degree of noncommutativity with the full Hamiltonian: higher uncertainty and commuting operators lead to better precision. We apply the bounds to show that there exist entangled thermal states such that the parameter can be estimated with an error that decreases faster than 1/n−−√, beating the standard quantum limit. This result governs Hamiltonians where an unknown scalar parameter (e.g. a component of a magnetic field) is coupled locally and identically to n qubit sensors. In the high-temperature regime, our bounds allow for pinpointing the optimal estimation error, up to a constant prefactor. Our bounds generalize to joint estimations of multiple parameters. In this setting, we recover the high-temperature sample scaling derived previously via techniques based on quantum state discrimination and coding theory. In an application, we show that noncommuting conserved quantities hinder the estimation of chemical potentials.

Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding - Jiaqi Leng; Joseph Li; Yuxiang Peng; Xiaodi Wu (2024)
Many promising quantum applications depend on the efficient quantum simulation of an exponentially large sparse Hamiltonian, a task known as sparse Hamiltonian simulation, which is fundamentally important in quantum computation. Although several theoretically appealing quantum algorithms have been proposed for this task, they typically require a black-box query model of the sparse Hamiltonian, rendering them impractical for near-term implementation on quantum devices. In this paper, we propose a technique named Hamiltonian embedding. This technique simulates a desired sparse Hamiltonian by embedding it into the evolution of a larger and more structured quantum system, allowing for more efficient simulation through hardware-efficient operations. We conduct a systematic study of this new technique and demonstrate significant savings in computational resources for implementing prominent quantum applications. As a result, we can now experimentally realize quantum walks on complicated graphs (e.g., binary trees, glued-tree graphs), quantum spatial search, and the simulation of real-space Schrödinger equations on current trapped-ion and neutral-atom platforms. Given the fundamental role of Hamiltonian evolution in the design of quantum algorithms, our technique markedly expands the horizon of implementable quantum advantages in the NISQ era.

Experimental roadmap for optimal state transfer and entanglement generation in power-law systems - Andrew Y. Guo; Jeremy T. Young; Ron Belyansky; Przemyslaw Bienias; Alexey V. Gorshkov (2024)
Experimental systems with power-law interactions have recently garnered interest as promising platforms for quantum information processing. Such systems are capable of spreading entanglement superballistically and achieving an asymptotic speed-up over locally interacting systems. Recently, protocols developed by Eldredge et al. [Phys. Rev. Lett. 119, 170503 (2017)] and Tran et al. [Phys. Rev. X 11, 031016 (2021)] for the task of transferring a quantum state between distant particles quickly were shown to be optimal and saturate theoretical bounds. However, the implementation of these protocols in physical systems with long-range interactions remains to be fully realized. In this work, we provide an experimental roadmap towards realizing fast state-transfer protocols in three classes of atomic and molecular systems with dipolar interactions: polar molecules composed of alkali-metal dimers, neutral atoms in excited Rydberg states, and atoms with strong magnetic moments (e.g. dysprosium). As a guide to near-term experimental implementation, we numerically evaluate the tradeoffs between the two protocols for small system sizes and develop methods to address potential crosstalk errors that may arise during the execution of the protocols.

Fast simulation of planar Clifford circuits - Gosset, David; Grier, Daniel; Kerzner, Alex; Luke Schaeffer (Quantum, 2024)
A general quantum circuit can be simulated classically in exponential time. If it has a planar layout, then a tensor-network contraction algorithm due to Markov and Shi has a runtime exponential in the square root of its size, or more generally exponential in the treewidth of the underlying graph. Separately, Gottesman and Knill showed that if all gates are restricted to be Clifford, then there is a polynomial time simulation. We combine these two ideas and show that treewidth and planarity can be exploited to improve Clifford circuit simulation. Our main result is a classical algorithm with runtime scaling asymptotically as nω/2<n1.19 which samples from the output distribution obtained by measuring all n qubits of a planar graph state in given Pauli bases. Here ω is the matrix multiplication exponent. We also provide a classical algorithm with the same asymptotic runtime which samples from the output distribution of any constant-depth Clifford circuit in a planar geometry. Our work improves known classical algorithms with cubic runtime. A key ingredient is a mapping which, given a tree decomposition of some graph G, produces a Clifford circuit with a structure that mirrors the tree decomposition and which emulates measurement of the corresponding graph state. We provide a classical simulation of this circuit with the runtime stated above for planar graphs and otherwise ntω−1 where t is the width of the tree decomposition. Our algorithm incorporates two subroutines which may be of independent interest. The first is a matrix-multiplication-time version of the Gottesman-Knill simulation of multi-qubit measurement on stabilizer states. The second is a new classical algorithm for solving symmetric linear systems over F2 in a planar geometry, extending previous works which only applied to non-singular linear systems in the analogous setting.

Free Quantum Codes from Twisted Unitary $t$-groups - Eric Kubischta; Ian Teixeira (2024)
We introduce twisted unitary t-groups, a generalization of unitary t-groups under a twisting by an irreducible representation. We then apply representation theoretic methods to the Knill-Laflamme error correction conditions to show that twisted unitary t-groups automatically correspond to quantum codes with distance d=t+1. By construction these codes have many transversal gates, which are naturally fault tolerant.

High-Energy Collision of Quarks and Mesons in the Schwinger Model: From Tensor Networks to Circuit QED - Belyansky, Ron; Whitsitt, Seth; Mueller, Niklas; Fahimniya, Ali; Bennewitz, Elizabeth R.; Davoudi, Zohreh; Gorshkov, Alexey V. (Physical Review Letters, 2024)
With the aim of studying nonperturbative out-of-equilibrium dynamics of high-energy particle collisions on quantum simulators, we investigate the scattering dynamics of lattice quantum electrodynamics in 1+1 dimensions. Working in the bosonized formulation of the model and in the thermodynamic limit, we use uniform-matrix-product-state tensor networks to construct multi-particle wave-packet states, evolve them in time, and detect outgoing particles post collision. This facilitates the numerical simulation of scattering experiments in both confined and deconfined regimes of the model at different energies, giving rise to rich phenomenology, including inelastic production of quark and meson states, meson disintegration, and dynamical string formation and breaking. We obtain elastic and inelastic scattering cross sections, together with time-resolved momentum and position distributions of the outgoing particles. Furthermore, we propose an analog circuit-QED implementation of the scattering process that is native to the platform, requires minimal ingredients and approximations, and enables practical schemes for particle wave-packet preparation and evolution. This study highlights the role of classical and quantum simulation in enhancing our understanding of scattering processes in quantum field theories in real time.

Integrability of Goldilocks quantum cellular automata - Logan E. Hillberry; Lorenzo Piroli; Eric Vernier; Nicole Yunger Halpern; Tomaž Prosen; Lincoln D. Carr (2024)
Goldilocks quantum cellular automata (QCA) have been simulated on quantum hardware and produce emergent small-world correlation networks. In Goldilocks QCA, a single-qubit unitary is applied to each qubit in a one-dimensional chain subject to a balance constraint: a qubit is updated if its neighbors are in opposite basis states. Here, we prove that a subclass of Goldilocks QCA -- including the one implemented experimentally -- map onto free fermions and therefore can be classically simulated efficiently. We support this claim with two independent proofs, one involving a Jordan--Wigner transformation and one mapping the integrable six-vertex model to QCA. We compute local conserved quantities of these QCA and predict experimentally measurable expectation values. These calculations can be applied to test large digital quantum computers against known solutions. In contrast, typical Goldilocks QCA have equilibration properties and quasienergy-level statistics that suggest nonintegrability. Still, the latter QCA conserve one quantity useful for error mitigation. Our work provides a parametric quantum circuit with tunable integrability properties with which to test quantum hardware.

Ion trap with in-vacuum high numerical aperture imaging for a dual-species modular quantum computer - Carter, Allison L.; O’Reilly, Jameson; Toh, George; Saha, Sagnik; Shalaev, Mikhail; Goetting, Isabella; Monroe, Christopher (Review of Scientific Instruments, 2024)
Photonic interconnects between quantum systems will play a central role in both scalable quantum computing and quantum networking. Entanglement of remote qubits via photons has been demonstrated in many platforms; however, improving the rate of entanglement generation will be instrumental for integrating photonic links into modular quantum computers. We present an ion trap system that has the highest reported free-space photon collection efficiency for quantum networking. We use a pair of in-vacuum aspheric lenses, each with a numerical aperture of 0.8, to couple 10% of the 493 nm photons emitted from a 138Ba+ ion into single-mode fibers. We also demonstrate that proximal effects of the lenses on the ion position and motion can be mitigated.

Long-Distance Nuclear Matrix Elements for Neutrinoless Double-Beta Decay from Lattice QCD - Zohreh Davoudi; William Detmold; Zhenghao Fu; Anthony V. Grebe; William Jay; David Murphy; Patrick Oare; Phiala E. Shanahan; Michael L. Wagman (2024)
Neutrinoless double-beta (0νββ) decay is a heretofore unobserved process which, if observed, would imply that neutrinos are Majorana particles. Interpretations of the stringent experimental constraints on 0νββ-decay half-lives require calculations of nuclear matrix elements. This work presents the first lattice quantum-chromodynamics (LQCD) calculation of the matrix element for 0νββ decay in a multi-nucleon system, specifically the nn→ppee transition, mediated by a light left-handed Majorana neutrino propagating over nuclear-scale distances. This calculation is performed with quark masses corresponding to a pion mass of mπ=806 MeV at a single lattice spacing and volume. The statistically cleaner Σ−→Σ+ee transition is also computed in order to investigate various systematic uncertainties. The prospects for matching the results of LQCD calculations onto a nuclear effective field theory to determine a leading-order low-energy constant relevant for 0νββ decay with a light Majorana neutrino are investigated. This work, therefore, sets the stage for future calculations at physical values of the quark masses that, combined with effective field theory and nuclear many-body studies, will provide controlled theoretical inputs to experimental searches of 0νββ decay.

Multi-product Hamiltonian simulation with explicit commutator scaling - Junaid Aftab; Dong An; Konstantina Trivisa (2024)
The well-conditioned multi-product formula (MPF), proposed by [Low, Kliuchnikov, and Wiebe, 2019], is a simple high-order time-independent Hamiltonian simulation algorithm that implements a linear combination of standard product formulas of low order. While the MPF aims to simultaneously exploit commutator scaling among Hamiltonians and achieve near-optimal time and precision dependence, its lack of a rigorous error bound on the nested commutators renders its practical advantage ambiguous. In this work, we conduct a rigorous complexity analysis of the well-conditioned MPF, demonstrating explicit commutator scaling and near-optimal time and precision dependence at the same time. Using our improved complexity analysis, we present several applications of practical interest where the MPF based on a second-order product formula can achieve a polynomial speedup in both system size and evolution time, as well as an exponential speedup in precision, compared to second-order and even higher-order product formulas. Compared to post-Trotter methods, the MPF based on a second-order product formula can achieve polynomially better scaling in system size, with only poly-logarithmic overhead in evolution time and precision.

Optimal function estimation with photonic quantum sensor networks - Bringewatt, Jacob; Ehrenberg, Adam; Goel, Tarushii; Gorshkov, Alexey V. (Physical Review Research, 2024)
The problem of optimally measuring an analytic function of unknown local parameters each linearly coupled to a qubit sensor is well understood, with applications ranging from field interpolation to noise characterization. Here, we resolve a number of open questions that arise when extending this framework to Mach-Zehnder interferometers and quadrature displacement sensing. In particular, we derive lower bounds on the achievable mean square error in estimating a linear function of either local phase shifts or quadrature displacements. In the case of local phase shifts, these results prove, and somewhat generalize, a conjecture by Proctor et al. [arXiv:1702.04271 (2017)]. For quadrature displacements, we extend proofs of lower bounds to the case of arbitrary linear functions. We provide optimal protocols achieving these bounds up to small (multiplicative) constants and describe an algebraic approach to deriving new optimal protocols, possibly subject to additional constraints. Using this approach, we prove necessary conditions for the amount of entanglement needed for any optimal protocol for both local phase and displacement sensing.

Phase transition in magic with random quantum circuits - Pradeep Niroula; Christopher David White; Qingfeng Wang; Sonika Johri; Daiwei Zhu; Christopher Monroe; Crystal Noel; Michael Gullans (2024)
Magic is a property of quantum states that enables universal fault-tolerant quantum computing using simple sets of gate operations. Understanding the mechanisms by which magic is created or destroyed is, therefore, a crucial step towards efficient and practical fault-tolerant computation. We observe that a random stabilizer code subject to coherent errors exhibits a phase transition in magic, which we characterize through analytic, numeric and experimental probes. Below a critical error rate, stabilizer syndrome measurements remove the accumulated magic in the circuit, effectively protecting against coherent errors; above the critical error rate syndrome measurements concentrate magic. A better understanding of such rich behavior in the resource theory of magic could shed more light on origins of quantum speedup and pave pathways for more efficient magic state generation.

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth - Joel Rajakumar; James D. Watson; Yi-Kai Liu (2024)
Sampling from the output distributions of quantum computations comprising only commuting gates, known as instantaneous quantum polynomial (IQP) computations, is believed to be intractable for classical computers, and hence this task has become a leading candidate for testing the capabilities of quantum devices. Here we demonstrate that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, whose depth is greater than a critical O(1) threshold, the output distribution can be efficiently sampled by a classical computer. Unlike other simulation algorithms for quantum supremacy tasks, we do not require assumptions on the circuit's architecture, on anti-concentration properties, nor do we require Ω(log(n)) circuit depth. We take advantage of the fact that IQP circuits have deep sections of diagonal gates, which allows the noise to build up predictably and induce a large-scale breakdown of entanglement within the circuit. Our results suggest that quantum supremacy experiments based on IQP circuits may be more susceptible to classical simulation than previously thought.

Post-quantum cryptography and the quantum future of cybersecurity - Liu, Yi-Kai; Moody, Dustin (Phys. Rev. Appl., 2024)
We review the current status of efforts to develop and deploy post-quantum cryptography on the Internet. Then we suggest specific ways in which quantum technologies might be used to enhance cybersecurity in the near future and beyond. We focus on two goals: protecting the secret keys that are used in classical cryptography, and ensuring the trustworthiness of quantum computations. These goals may soon be within reach, thanks to recent progress in both theory and experiment. This progress includes interactive protocols for testing quantumness as well as for performing uncloneable cryptographic computations; and experimental demonstrations of device-independent random number generators, device-independent quantum key distribution, quantum memories, and analog quantum simulators.

Precision Bounds on Continuous-Variable State Tomography Using Classical Shadows - Gandhari, Srilekha; Albert, Victor V.; Gerrits, Thomas; Taylor, Jacob M.; Michael Gullans (PRX Quantum, 2024)
Shadow tomography is a framework for constructing succinct descriptions of quantum states using randomized measurement bases, called “classical shadows,” with powerful methods to bound the estimators used. We recast existing experimental protocols for continuous-variable quantum state tomography in the classical-shadow framework, obtaining rigorous bounds on the number of independent measurements needed for estimating density matrices from these protocols. We analyze the efficiency of homodyne, heterodyne, photon-number-resolving, and photon-parity protocols. To reach a desired precision on the classical shadow of an N-photon density matrix with high probability, we show that homodyne detection requires order O(N4+1/3) measurements in the worst case, whereas photon-number-resolving and photon-parity detection require O (N4)measurements in the worst case (both up to logarithmic corrections). We benchmark these results against numerical simulation as well as experimental data from optical homodyne experiments. We find that numerical and experimental analyses of homodyne tomography match closely with our theoretical predictions. We extend our single-mode results to an efficient construction of multimode shadows based on local measurements.

Properties and Applications of the Kirkwood-Dirac Distribution - David R. M. Arvidsson-Shukur; William F. Braasch Jr.; Stephan De Bievre; Justin Dressel; Andrew N. Jordan; Christopher Langrenez; Matteo Lostaglio; Jeff S. Lundeen; Nicole Yunger Halpern (2024)
The most famous quasi-probability distribution, the Wigner function, has played a pivotal role in the development of a continuous-variable quantum theory that has clear analogues of position and momentum. However, the Wigner function is ill-suited for much modern quantum-information research, which is focused on finite-dimensional systems and general observables. Instead, recent years have seen the Kirkwood-Dirac (KD) distribution come to the forefront as a powerful quasi-probability distribution for analysing quantum mechanics. The KD distribution allows tools from statistics and probability theory to be applied to problems in quantum-information processing. A notable difference to the Wigner function is that the KD distribution can represent a quantum state in terms of arbitrary observables. This paper reviews the KD distribution, in three parts. First, we present definitions and basic properties of the KD distribution and its generalisations. Second, we summarise the KD distribution's extensive usage in the study or development of measurement disturbance; quantum metrology; weak values; direct measurements of quantum states; quantum thermodynamics; quantum scrambling and out-of-time-ordered correlators; and the foundations of quantum mechanics, including Leggett-Garg inequalities, the consistent-histories interpretation, and contextuality. We emphasise connections between operational quantum advantages and negative or non-real KD quasi-probabilities. Third, we delve into the KD distribution's mathematical structure. We summarise the current knowledge regarding the geometry of KD-positive states (the states for which the KD distribution is a classical probability distribution), describe how to witness and quantify KD non-positivity, and outline relationships between KD non-positivity and observables' incompatibility.

The Quantum Abstract Machine - Liyi Li; Le Chang; Rance Cleaveland; Mingwei Zhu; Xiaodi Wu (2024)
This paper develops a model of quantum behavior that is intended to support the abstract yet accurate design and functional verification of quantum communication protocols. The work is motivated by the need for conceptual tools for the development of quantum-communication systems that are usable by non-specialists in quantum physics while also correctly capturing at a useful abstraction the underlying quantum phenomena. Our approach involves defining a quantum abstract machine (QAM) whose operations correspond to well-known quantum circuits; these operations, however, are given direct abstract semantics in a style similar to that of Berry's and Boudol's Chemical Abstract Machine. This paper defines the QAM's semantics and shows via examples how it may be used to model and reason about existing quantum communication protocols.

A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles - Jonathan Katz; Ben Sela (2024)
We study the (quantum) security of pseudorandom generators (PRGs) constructed from random oracles. We prove a "lifting theorem" showing, roughly, that if such a PRG is unconditionally secure against classical adversaries making polynomially many queries to the random oracle, then it is also (unconditionally) secure against quantum adversaries in the same sense. As a result of independent interest, we also show that any pseudo-deterministic quantum-oracle algorithm (i.e., a quantum algorithm that with high probability returns the same value on repeated executions) can be simulated by a computationally unbounded but query bounded classical-oracle algorithm with only a polynomial blowup in the number of queries. This implies as a corollary that our lifting theorem holds even for PRGs that themselves make quantum queries to the random oracle.

Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations - Joseph Carolan; Alexander Poremba (2024)
Sponge hashing is a novel class of cryptographic hash algorithms which underlies the current international hash function standard SHA-3. In a nutshell, a sponge function takes as input a bit-stream of any length and processes it via a simple iterative procedure: it repeatedly feeds each block of the input into a so-called block function, and then produces a short digest which consists of a subset of the final output bits. While much is known about the post-quantum security of the sponge construction in the case when the block function is modeled as a random function or permutation, the case of invertible permutations, which more accurately models the construction underlying SHA-3, has so far remained a fundamental open problem. In this work, we make new progress towards overcoming this barrier and show several results. First, we prove the "double-sided zero-search" conjecture proposed by Unruh (eprint' 2021) and show that finding zero-pairs in a random 2n-bit permutation requires at least Ω(2n/2) many queries -- and this is tight due to Grover's algorithm. At the core of our proof lies a novel "symmetrization argument" which uses insights from the theory of Young subgroups. Second, we consider more general variants of the double-sided search problem and show similar query lower bounds for them. As an application, we prove the quantum one-wayness of the single-round sponge with invertible permutations in the quantum random oracle model.

Quantum thermodynamics of nonequilibrium processes in lattice gauge theories - Zohreh Davoudi; Christopher Jarzynski; Niklas Mueller; Greeshma Oruganti; Connor Powers; Nicole Yunger Halpern (2024)
A key objective in nuclear and high-energy physics is to describe nonequilibrium dynamics of matter, e.g., in the early universe and in particle colliders, starting from the Standard Model. Classical-computing methods, via the framework of lattice gauge theory, have experienced limited success in this mission. Quantum simulation of lattice gauge theories holds promise for overcoming computational limitations. Because of local constraints (Gauss's laws), lattice gauge theories have an intricate Hilbert-space structure. This structure complicates the definition of thermodynamic properties of systems coupled to reservoirs during equilibrium and nonequilibrium processes. We show how to define thermodynamic quantities such as work and heat using strong-coupling thermodynamics, a framework that has recently burgeoned within the field of quantum thermodynamics. Our definitions suit instantaneous quenches, simple nonequilibrium processes undertaken in quantum simulators. To illustrate our framework, we compute the work and heat exchanged during a quench in a Z2 lattice gauge theory coupled to matter in 1+1 dimensions. The thermodynamic quantities, as functions of the quench parameter, evidence an expected phase transition. For general thermal states, we derive a simple relation between a quantum many-body system's entanglement Hamiltonian, measurable with quantum-information-processing tools, and the Hamiltonian of mean force, used to define strong-coupling thermodynamic quantities.

Randomized measurement protocols for lattice gauge theories - Bringewatt, Jacob; Kunjummen, Jonathan; Mueller, Niklas (Quantum, 2024)
Randomized measurement protocols, including classical shadows, entanglement tomography, and randomized benchmarking are powerful techniques to estimate observables, perform state tomography, or extract the entanglement properties of quantum states. While unraveling the intricate structure of quantum states is generally difficult and resource-intensive, quantum systems in nature are often tightly constrained by symmetries. This can be leveraged by the symmetry-conscious randomized measurement schemes we propose, yielding clear advantages over symmetry-blind randomization such as reducing measurement costs, enabling symmetry-based error mitigation in experiments, allowing differentiated measurement of (lattice) gauge theory entanglement structure, and, potentially, the verification of topologically ordered states in existing and near-term experiments. Crucially, unlike symmetry-blind randomized measurement protocols, these latter tasks can be performed without relearning symmetries via full reconstruction of the density matrix.

Scattering wave packets of hadrons in gauge theories: Preparation on a quantum computer - Zohreh Davoudi; Chung-Chun Hsieh; Saurabh V. Kadam (2024)
Quantum simulation holds promise of enabling a complete description of high-energy scattering processes rooted in gauge theories of the Standard Model. A first step in such simulations is preparation of interacting hadronic wave packets. To create the wave packets, one typically resorts to adiabatic evolution to bridge between wave packets in the free theory and those in the interacting theory, rendering the simulation resource intensive. In this work, we construct a wave-packet creation operator directly in the interacting theory to circumvent adiabatic evolution, taking advantage of resource-efficient schemes for ground-state preparation, such as variational quantum eigensolvers. By means of an ansatz for bound mesonic excitations in confining gauge theories, which is subsequently optimized using classical or quantum methods, we show that interacting mesonic wave packets can be created efficiently and accurately using digital quantum algorithms that we develop. Specifically, we obtain high-fidelity mesonic wave packets in the Z2 and U(1) lattice gauge theories coupled to fermionic matter in 1+1 dimensions. Our method is applicable to both perturbative and non-perturbative regimes of couplings. The wave-packet creation circuit for the case of the Z2 lattice gauge theory is built and implemented on the Quantinuum H1-1 trapped-ion quantum computer using 13 qubits and up to 308 entangling gates. The fidelities agree well with classical benchmark calculations after employing a simple symmetry-based noise-mitigation technique. This work serves as a step toward quantum computing scattering processes in quantum chromodynamics.

The Second Moment of Hafnians in Gaussian Boson Sampling - Adam Ehrenberg; Joseph T. Iosue; Abhinav Deshpande; Dominik Hangleiter; Alexey V. Gorshkov (2024)
Gaussian Boson Sampling is a popular method for experimental demonstrations of quantum advantage, but many subtleties remain in fully understanding its theoretical underpinnings. An important component in the theoretical arguments for approximate average-case hardness of sampling is anticoncentration, which is a second-moment property of the output probabilities. In Gaussian Boson Sampling these are given by hafnians of generalized circular orthogonal ensemble matrices. In a companion work [arXiv:2312.08433], we develop a graph-theoretic method to study these moments and use it to identify a transition in anticoncentration. In this work, we find a recursive expression for the second moment using these graph-theoretic techniques. While we have not been able to solve this recursion by hand, we are able to solve it numerically exactly, which we do up to Fock sector 2n=80. We further derive new analytical results about the second moment. These results allow us to pinpoint the transition in anticoncentration and furthermore yield the expected linear cross-entropy benchmarking score for an ideal (error-free) device.

Simulating Meson Scattering on Spin Quantum Simulators - Elizabeth R. Bennewitz; Brayden Ware; Alexander Schuckert; Alessio Lerose; Federica M. Surace; Ron Belyansky; William Morong; De Luo; Arinjoy De; Kate S. Collins; Or Katz; Christopher Monroe; et al. (2024)
Studying high-energy collisions of composite particles, such as hadrons and nuclei, is an outstanding goal for quantum simulators. However, preparation of hadronic wave packets has posed a significant challenge, due to the complexity of hadrons and the precise structure of wave packets. This has limited demonstrations of hadron scattering on quantum simulators to date. Observations of confinement and composite excitations in quantum spin systems have opened up the possibility to explore scattering dynamics in spin models. In this article, we develop two methods to create entangled spin states corresponding to wave packets of composite particles in analog quantum simulators of Ising spin Hamiltonians. One wave-packet preparation method uses the blockade effect enabled by beyond-nearest-neighbor Ising spin interactions. The other method utilizes a quantum-bus-mediated exchange, such as the native spin-phonon coupling in trapped-ion arrays. With a focus on trapped-ion simulators, we numerically benchmark both methods and show that high-fidelity wave packets can be achieved in near-term experiments. We numerically study scattering of wave packets for experimentally realizable parameters in the Ising model and find inelastic-scattering regimes, corresponding to particle production in the scattering event, with prominent and distinct experimental signals. Our proposal, therefore, demonstrates the potential of observing inelastic scattering in near-term quantum simulators.

SimuQ: A Framework for Programming Quantum Hamiltonian Simulation with Analog Compilation - Peng, Yuxiang; Young, Jacob; Liu, Pengyu; Wu, Xiaodi (Proceedings of the ACM on Programming Languages, 2024)
Quantum Hamiltonian simulation, which simulates the evolution of quantum systems and probes quantum phenomena, is one of the most promising applications of quantum computing. Recent experimental results suggest that Hamiltonian-oriented analog quantum simulation would be advantageous over circuit-oriented digital quantum simulation in the Noisy Intermediate-Scale Quantum (NISQ) machine era. However, programming analog quantum simulators is much more challenging due to the lack of a unified interface between hardware and software. In this paper, we design and implement SimuQ, the first framework for quantum Hamiltonian simulation that supports Hamiltonian programming and pulse-level compilation to heterogeneous analog quantum simulators. Specifically, in SimuQ, front-end users specify the target quantum system with Hamiltonian Modeling Language, and the Hamiltonian-level programmability of analog quantum simulators is specified through a new abstraction called the abstract analog instruction set (AAIS) and programmed in AAIS Specification Language by hardware providers. Through a solver-based compilation, SimuQ generates executable pulse schedules for real devices to simulate the evolution of desired quantum systems, which is demonstrated on superconducting (IBM), neutral-atom (QuEra), and trapped-ion (IonQ) quantum devices. Moreover, we demonstrate the advantages of exposing the Hamiltonian-level programmability of devices with native operations or interaction-based gates and establish a small benchmark of quantum simulation to evaluate SimuQ's compiler with the above analog quantum simulators.

Strong interactions between integrated microresonators and alkali atomic vapors: towards single-atom, single-photon operation - Roy Zektzer; Xiyuan Lu; Khoi Tuan Hoang; Rahul Shrestha; Sharoon Austin; Feng Zhou; Ashish Chanana; Glenn Holland; Daron Westly; Paul Lett; Alexey V. Gorshkov; Kartik Srinivasan (2024)
Cavity quantum electrodynamics (cQED), the interaction of a two-level system with a high quality factor (Q) cavity, is a foundational building block in different architectures for quantum computation, communication, and metrology. The strong interaction between the atom and the cavity enables single photon operation which is required for quantum gates and sources. Cold atoms, quantum dots, and color centers in crystals are amongst the systems that have shown single photon operations, but they require significant physical infrastructure. Atomic vapors, on the other hand, require limited experimental infrastructure and are hence much easier to deploy outside a laboratory, but they produce an ensemble of moving atoms that results in short interaction times involving multiple atoms, which can hamper quantum operations. A solution to this issue can be found in nanophotonic cavities, where light-matter interaction is enhanced and the volume of operation is small, so that fast single-atom, single-photon operations are enabled. In this work, we study the interaction of an atomically-clad microring resonator (ACMRR) with different-sized ensembles of Rb atoms. We demonstrate strong coupling between an ensemble of ~50 atoms interacting with a high-quality factor (Q > 4 x 10^5) ACMRR, yielding a many-atom cooperativity C ~ 5.5. We continue to observe signatures of atom-photon interaction for a few (< 3) atoms, for which we observe saturation at the level of one intracavity photon. Further development of our platform, which includes integrated thermo-optic heaters to enable cavity tuning and stabilization, should enable the observation of interactions between single photons and single atoms.

Topology and entanglement of molecular phase space - Victor V. Albert; Eric Kubischta; Mikhail Lemeshko; Lee R. Liu (2024)
We formulate a quantum phase space for 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 or breaking symmetry. Second, each molecular position state houses an internal pseudo-spin or "fiber" degree of freedom, and the fiber's Berry phase or matrix after adiabatic changes in position yields naturally robust operations, akin to braiding anyonic quasiparticles or realizing fault-tolerant quantum gates. We outline scenarios where these features can be experimentally probed.

Trainability Barriers in Low-Depth QAOA Landscapes - Joel Rajakumar; John Golden; Andreas Bärtschi; Stephan Eidenbenz (2024)
The Quantum Alternating Operator Ansatz (QAOA) is a prominent variational quantum algorithm for solving combinatorial optimization problems. Its effectiveness depends on identifying input parameters that yield high-quality solutions. However, understanding the complexity of training QAOA remains an under-explored area. Previous results have given analytical performance guarantees for a small, fixed number of parameters. At the opposite end of the spectrum, barren plateaus are likely to emerge at Ω(n) parameters for n qubits. In this work, we study the difficulty of training in the intermediate regime, which is the focus of most current numerical studies and near-term hardware implementations. Through extensive numerical analysis of the quality and quantity of local minima, we argue that QAOA landscapes can exhibit a superpolynomial growth in the number of low-quality local minima even when the number of parameters scales logarithmically with n. This means that the common technique of gradient descent from randomly initialized parameters is doomed to fail beyond small n, and emphasizes the need for good initial guesses of the optimal parameters.

Ultrastrong light-matter interaction in a multimode photonic crystal - Andrei Vrajitoarea; Ron Belyansky; Rex Lundgren; Seth Whitsitt; Alexey V. Gorshkov; Andrew A. Houck (2024)
Harnessing the interaction between light and matter at the quantum level has been a central theme in atomic physics and quantum optics, with applications from quantum computation to quantum metrology. Combining complex interactions with photonic synthetic materials provides an opportunity to investigate novel quantum phases and phenomena, establishing interesting connections to condensed matter physics. Here we explore many-body phenomena with a single artificial atom coupled to the many discrete modes of a photonic crystal. This experiment reaches the ultrastrong light-matter coupling regime using the circuit quantum electrodynamics paradigm, by galvanically coupling a highly nonlinear fluxonium qubit to a tight-binding lattice of microwave resonators. In this regime, the transport of a single photon becomes a many-body problem, owing to the strong participation of multi-photon bound states arising from interactions that break particle number conservation. Exploiting the effective photon-photon interactions mediated by the qubit, the transport of multiple photons leads to complex multimode dynamics that can be employed for generating a continuous reservoir of strongly-correlated photons, an important resource for quantum networks. This work opens exciting prospects for exploring nonlinear quantum optics at the single-photon level and stabilizing entangled many-body phases of light.

Zero-temperature entanglement membranes in quantum circuits - Grace M. Sommers; Sarang Gopalakrishnan; Michael Gullans; David A. Huse (2024)
In chaotic quantum systems, the entanglement of a region A can be described in terms of the surface tension of a spacetime membrane pinned to the boundary of A. Here, we interpret the tension of this entanglement membrane in terms of the rate at which information "flows" across it. For any orientation of the membrane, one can define (generically nonunitary) dynamics across the membrane; we explore this dynamics in various space-time translation-invariant (STTI) stabilizer circuits in one and two spatial dimensions. We find that the flux of information across the membrane in these STTI circuits reaches a steady state. In the cases where this dynamics is nonunitary and the steady state flux is nonzero, this occurs because the dynamics across the membrane is unitary in a subspace of extensive entropy. This generalized unitarity is present in a broad class of STTI stabilizer circuits, and is also present in some special non-stabilizer models. The existence of multiple unitary (or generalized unitary) directions forces the entanglement membrane tension to be a piecewise linear function of the orientation of the membrane; in this respect, the entanglement membrane behaves like an interface in a zero-temperature classical lattice model. We argue that entanglement membranes in random stabilizer circuits that produce volume-law entanglement are also effectively at zero temperature.

Accelerating Progress Towards Practical Quantum Advantage: The Quantum Technology Demonstration Project Roadmap - Paul Alsing; Phil Battle; Joshua C. Bienfang; Tammie Borders; Tina Brower-Thomas; Lincoln D. Carr; Fred Chong; Siamak Dadras; Brian DeMarco; Ivan Deutsch; Eden Figueroa; Danna Freedman; et al. (2023)
Quantum information science and technology (QIST) is a critical and emerging technology with the potential for enormous world impact and is currently invested in by over 40 nations. To bring these large-scale investments to fruition and bridge the lower technology readiness levels (TRLs) of fundamental research at universities to the high TRLs necessary to realize the promise of practical quantum advantage accessible to industry and the public, we present a roadmap for Quantum Technology Demonstration Projects (QTDPs). Such QTDPs, focused on intermediate TRLs, are large-scale public-private partnerships with a high probability of translation from laboratory to practice. They create technology demonstrating a clear 'quantum advantage' for science breakthroughs that are user-motivated and will provide access to a broad and diverse community of scientific users. Successful implementation of a program of QTDPs will have large positive economic impacts.

Accurate and Honest Approximation of Correlated Qubit Noise - F. Setiawan; Alexander V. Gramolin; Elisha S. Matekole; Hari Krovi; Jacob M. Taylor (2023)
Accurate modeling of noise in realistic quantum processors is critical for constructing fault-tolerant quantum computers. While a full simulation of actual noisy quantum circuits provides information about correlated noise among all qubits and is therefore accurate, it is, however, computationally expensive as it requires resources that grow exponentially with the number of qubits. In this paper, we propose an efficient systematic construction of approximate noise channels, where their accuracy can be enhanced by incorporating noise components with higher qubit-qubit correlation degree. To formulate such approximate channels, we first present a method, dubbed the cluster expansion approach, to decompose the Lindbladian generator of an actual Markovian noise channel into components based on interqubit correlation degree. We then generate a k-th order approximate noise channel by truncating the cluster expansion and incorporating noise components with correlations up to the k-th degree. We require that the approximate noise channels must be accurate and also "honest", i.e., the actual errors are not underestimated in our physical models. As an example application, we apply our method to model noise in a three-qubit quantum processor that stabilizes a [[2,0,0]] codeword, which is one of the four Bell states. We find that, for realistic noise strength typical for fixed-frequency superconducting qubits coupled via always-on static interactions, correlated noise beyond two-qubit correlation can significantly affect the code simulation accuracy. Since our approach provides a systematic noise characterization, it enables the potential for accurate, honest and scalable approximation to simulate large numbers of qubits from full modeling or experimental characterizations of small enough quantum subsystems, which are efficient but still retain essential noise features of the entire device.

Advantages and limitations of quantum routing - Bapat, Aniruddha; Andrew M. Childs; Alexey V. Gorshkov; Schoute, Eddie (PRX Quantum, 2023)
The Swap gate is a ubiquitous tool for moving information on quantum hardware, yet it can be considered a classical operation because it does not entangle product states. Genuinely quantum operations could outperform Swap for the task of permuting qubits within an architecture, which we call routing. We consider quantum routing in two models: (1) allowing arbitrary two-qubit unitaries, or (2) allowing Hamiltonians with norm-bounded interactions. We lower bound the circuit depth or time of quantum routing in terms of spectral properties of graphs representing the architecture interaction constraints, and give a generalized upper bound for all simple connected n-vertex graphs. In particular, we give conditions for a superpolynomial classical-quantum routing separation, which exclude graphs with a small spectral gap and graphs of bounded degree. Finally, we provide examples of a quadratic separation between gate-based and Hamiltonian routing models with a constant number of local ancillas per qubit and of an Ω(n) speedup if we also allow fast local interactions.
Keywords: Data Structures and Algorithms (cs.DS); FOS: Computer and information sciences; FOS: Physical sciences; Quantum Physics (quant-ph)

Analyzing Convergence in Quantum Neural Networks: Deviations from Neural Tangent Kernels - Xuchen You; Shouvanik Chakrabarti; Boyang Chen; Xiaodi Wu (2023)
A quantum neural network (QNN) is a parameterized mapping efficiently implementable on near-term Noisy Intermediate-Scale Quantum (NISQ) computers. It can be used for supervised learning when combined with classical gradient-based optimizers. Despite the existing empirical and theoretical investigations, the convergence of QNN training is not fully understood. Inspired by the success of the neural tangent kernels (NTKs) in probing into the dynamics of classical neural networks, a recent line of works proposes to study over-parameterized QNNs by examining a quantum version of tangent kernels. In this work, we study the dynamics of QNNs and show that contrary to popular belief it is qualitatively different from that of any kernel regression: due to the unitarity of quantum operations, there is a non-negligible deviation from the tangent kernel regression derived at the random initialization. As a result of the deviation, we prove the at-most sublinear convergence for QNNs with Pauli measurements, which is beyond the explanatory power of any kernel regression dynamics. We then present the actual dynamics of QNNs in the limit of over-parameterization. The new dynamics capture the change of convergence rate during training and implies that the range of measurements is crucial to the fast QNN convergence.

Bell sampling from quantum circuits - Dominik Hangleiter; Michael Gullans (2023)
A central challenge in the verification of quantum computers is benchmarking their performance as a whole and demonstrating their computational capabilities. In this work, we find a universal model of quantum computation, Bell sampling, that can be used for both of those tasks and thus provides an ideal stepping stone towards fault-tolerance. In Bell sampling, we measure two copies of a state prepared by a quantum circuit in the transversal Bell basis. We show that the Bell samples are classically intractable to produce and at the same time constitute what we call a circuit shadow: from the Bell samples we can efficiently extract information about the quantum circuit preparing the state, as well as diagnose circuit errors. In addition to known properties that can be efficiently extracted from Bell samples, we give two new and efficient protocols, a test for the depth of the circuit and an algorithm to estimate a lower bound to the number of T gates in the circuit. With some additional measurements, our algorithm learns a full description of states prepared by circuits with low T-count.

Bell sampling from quantum circuits - Dominik Hangleiter; Michael Gullans (2023)
A central challenge in the verification of quantum computers is benchmarking their performance as a whole and demonstrating their computational capabilities. In this work, we find a model of quantum computation, Bell sampling, that can be used for both of those tasks and thus provides an ideal stepping stone towards fault-tolerance. In Bell sampling, we measure two copies of a state prepared by a quantum circuit in the transversal Bell basis. We show that the Bell samples are classically intractable to produce and at the same time constitute what we call a circuit shadow: from the Bell samples we can efficiently extract information about the quantum circuit preparing the state, as well as diagnose circuit errors. In addition to known properties that can be efficiently extracted from Bell samples, we give two new and efficient protocols, a test for the depth of the circuit and an algorithm to estimate a lower bound to the number of T gates in the circuit. With some additional measurements, our algorithm learns a full description of states prepared by circuits with low T-count.

Bounds on Autonomous Quantum Error Correction - Oles Shtanko; Yu-Jie Liu; Simon Lieu; Alexey V. Gorshkov; Victor V. Albert (2023)
Autonomous quantum memories are a way to passively protect quantum information using engineered dissipation that creates an "always-on'' decoder. We analyze Markovian autonomous decoders that can be implemented with a wide range of qubit and bosonic error-correcting codes, and derive several upper bounds and a lower bound on the logical error rate in terms of correction and noise rates. For many-body quantum codes, we show that, to achieve error suppression comparable to active error correction, autonomous decoders generally require correction rates that grow with code size. For codes with a threshold, we show that it is possible to achieve faster-than-polynomial decay of the logical error rate with code size by using superlogarithmic scaling of the correction rate. We illustrate our results with several examples. One example is an exactly solvable global dissipative toric code model that can achieve an effective logical error rate that decreases exponentially with the linear lattice size, provided that the recovery rate grows proportionally with the linear lattice size.

Candidate for a passively protected quantum memory in two dimensions - Simon Lieu; Yu-Jie Liu; Alexey V. Gorshkov (2023)
An interesting problem in the field of quantum error correction involves finding a physical system that hosts a ``passively protected quantum memory,'' defined as an encoded qubit coupled to an environment that naturally wants to correct errors. To date, a quantum memory stable against finite-temperature effects is only known in four spatial dimensions or higher. Here, we take a different approach to realize a stable quantum memory by relying on a driven-dissipative environment. We propose a new model, the photonic-Ising model, which appears to passively correct against both bit-flip and phase-flip errors in two dimensions: A square lattice composed of photonic ``cat qubits'' coupled via dissipative terms which tend to fix errors locally. Inspired by the presence of two distinct Z2-symmetry-broken phases, our scheme relies on Ising-like dissipators to protect against bit flips and on a driven-dissipative photonic environment to protect against phase flips. We also discuss possible ways to realize the photonic-Ising model.

Clifford operations and homological codes for rotors and oscillators - Yijia Xu; Yixu Wang; Victor V. Albert (2023)
We develop quantum information processing primitives for the planar rotor, the state space of a particle on a circle. By interpreting rotor wavefunctions as periodically identified wavefunctions of a harmonic oscillator, we determine the group of bosonic Gaussian operations inherited by the rotor. This n-rotor Clifford group, U(1)n(n+1)/2⋊GLn(Z), is represented by continuous U(1) gates generated by polynomials quadratic in angular momenta, as well as discrete GLn(Z) momentum sign-flip and sum gates. We classify homological rotor error-correcting codes [arXiv:2303.13723] and various rotor states based on equivalence under Clifford operations. Reversing direction, we map homological rotor codes and rotor Clifford operations back into oscillators by interpreting occupation-number states as rotor states of non-negative angular momentum. This yields new multimode homological bosonic codes protecting against dephasing and changes in occupation number, along with their corresponding encoding and decoding circuits. In particular, we show how to non-destructively measure the oscillator phase using conditional occupation-number addition and post selection. We also outline several rotor and oscillator varieties of the GKP-stabilizer codes [arXiv:1903.12615].

Collision-resolved pressure sensing - Daniel S. Barker; Daniel Carney; Thomas W. LeBrun; David C. Moore; Jacob M. Taylor (2023)
Heat and pressure are ultimately transmitted via quantized degrees of freedom, like gas particles and phonons. While a continuous Brownian description of these noise sources is adequate to model measurements with relatively long integration times, sufficiently precise measurements can resolve the detailed time dependence coming from individual bath-system interactions. We propose the use of nanomechanical devices operated with impulse readout sensitivity around the ``standard quantum limit'' to sense ultra-low gas pressures by directly counting the individual collisions of gas particles on a sensor. We illustrate this in two paradigmatic model systems: an optically levitated nanobead and a tethered membrane system in a phononic bandgap shield.

Colloquium: Advances in automation of quantum dot devices control - Justyna P. Zwolak; Jacob M. Taylor (Reviews of Modern Physics, 2023)
Arrays of quantum dots (QDs) are a promising candidate system to realize scalable, coupled qubit systems and serve as a fundamental building block for quantum computers. In such semiconductor quantum systems, devices now have tens of individual electrostatic and dynamical voltages that must be carefully set to localize the system into the single-electron regime and to realize good qubit operational performance. The mapping of requisite QD locations and charges to gate voltages presents a challenging classical control problem. With an increasing number of QD qubits, the relevant parameter space grows sufficiently to make heuristic control unfeasible. In recent years, there has been considerable effort to automate device control that combines script-based algorithms with machine learning (ML) techniques. In this Colloquium, a comprehensive overview of the recent progress in the automation of QD device control is presented, with a particular emphasis on silicon- and GaAs-based QDs formed in two-dimensional electron gases. Combining physics-based modeling with modern numerical optimization and ML has proven effective in yielding efficient, scalable control. Further integration of theoretical, computational, and experimental efforts with computer science and ML holds vast potential in advancing semiconductor and other platforms for quantum computing.

Colloquium: Quantum and Classical Discrete Time Crystals - Michael P. Zaletel; Mikhail Lukin; Christopher Monroe; Chetan Nayak; Frank Wilczek; Norman Y. Yao (2023)
The spontaneous breaking of time translation symmetry has led to the discovery of a new phase of matter - the discrete time crystal. Discrete time crystals exhibit rigid subharmonic oscillations, which result from a combination of many-body interactions, collective synchronization, and ergodicity breaking. This Colloquium reviews recent theoretical and experimental advances in the study of quantum and classical discrete time crystals. We focus on the breaking of ergodicity as the key to discrete time crystals and the delaying of ergodicity as the source of numerous phenomena that share many of the properties of discrete time crystals, including the AC Josephson effect, coupled map lattices, and Faraday waves. Theoretically, there exists a diverse array of strategies to stabilize time crystalline order in both closed and open systems, ranging from localization and prethermalization to dissipation and error correction. Experimentally, many-body quantum simulators provide a natural platform for investigating signatures of time crystalline order; recent work utilizing trapped ions, solid-state spin systems, and superconducting qubits will be reviewed. Finally, this Colloquium concludes by describing outstanding challenges in the field and a vision for new directions on both the experimental and theoretical fronts.

Complexity and order in approximate quantum error-correcting codes - Jinmin Yi; Weicheng Ye; Daniel Gottesman; Zi-Wen Liu (2023)
We establish rigorous connections between quantum circuit complexity and approximate quantum error correction (AQEC) properties, covering both all-to-all and geometric scenarios including lattice systems. To this end, we introduce a type of code parameter that we call subsystem variance, which is closely related to the optimal AQEC precision. Our key finding is that if the subsystem variance is below an O(k/n) threshold then any state in the code subspace must obey certain circuit complexity lower bounds, which identify nontrivial ``phases'' of codes. Based on our results, we propose O(k/n) as a boundary between subspaces that should and should not count as AQEC codes. This theory of AQEC provides a versatile framework for understanding the quantum complexity and order of many-body quantum systems, offering new insights for wide-ranging physical scenarios, in particular topological order and critical quantum systems which are of outstanding importance in many-body and high energy physics. We observe from various different perspectives that roughly O(1/n) represents a common, physically significant ``scaling threshold'' of subsystem variance for features associated with nontrivial quantum order.

Compressed gate characterization for quantum devices with time-correlated noise - Michael Gullans; M. Caranti; A. R. Mills; J. R. Petta (2023)
As quantum devices make steady progress towards intermediate scale and fault-tolerant quantum computing, it is essential to develop rigorous and efficient measurement protocols that account for known sources of noise. Most existing quantum characterization protocols such as gate set tomography and randomized benchmarking assume the noise acting on the qubits is Markovian. However, this assumption is often not valid, as for the case of 1/f charge noise or hyperfine nuclear spin noise. Here, we present a general framework for quantum process tomography (QPT) in the presence of time-correlated noise. We further introduce fidelity benchmarks that quantify the relative strength of different sources of Markovian and non-Markovian noise. As an application of our method, we perform a comparative theoretical and experimental analysis of silicon spin qubits. We first develop a detailed noise model that accounts for the dominant sources of noise and validate the model against experimental data. Applying our framework for time-correlated QPT, we find that the number of independent parameters needed to characterize one and two-qubit gates can be compressed by 10x and 100x, respectively, when compared to the fully generic case. These compressions reduce the amount of tomographic measurements needed in experiment, while also significantly speeding up numerical simulations of noisy quantum circuit dynamics compared to time-dependent Hamiltonian simulation. Using this compressed noise model, we find good agreement between our theoretically predicted process fidelities and two qubit interleaved randomized benchmarking fidelities of 99.8% measured in recent experiments on silicon spin qubits. More broadly, our formalism can be directly extended to develop efficient and scalable tuning protocols for high-fidelity control of large-arrays of quantum devices with non-Markovian noise.

Critical phase and spin sharpening in SU(2)-symmetric monitored quantum circuits - Shayan Majidy; Utkarsh Agrawal; Sarang Gopalakrishnan; Andrew C. Potter; Romain Vasseur; Nicole Yunger Halpern (Physical Review B, 2023)
Monitored quantum circuits exhibit entanglement transitions at certain measurement rates. Such a transition separates phases characterized by how much information an observer can learn from the measurement outcomes. We study SU(2)-symmetric monitored quantum circuits, using exact numerics and a mapping onto an effective statistical-mechanics model. Due to the symmetry's non-Abelian nature, measuring qubit pairs allows for nontrivial entanglement scaling even in the measurement-only limit. We find a transition between a volume-law entangled phase and a critical phase whose diffusive purification dynamics emerge from the non-Abelian symmetry. Additionally, we numerically identify a "spin-sharpening transition." On one side is a phase in which the measurements can efficiently identify the system's total spin quantum number; on the other side is a phase in which measurements cannot.

Data Needs and Challenges of Quantum Dot Devices Automation: Workshop Report - Justyna P. Zwolak; Jacob M. Taylor; Reed Andrews; Jared Benson; Garnett Bryant; Donovan Buterakos; Anasua Chatterjee; Sankar Das Sarma; Mark A. Eriksson; Eliška Greplová; Michael Gullans; Fabian Hader; et al. (2023)
Gate-defined quantum dots are a promising candidate system to realize scalable, coupled qubit systems and serve as a fundamental building block for quantum computers. However, present-day quantum dot devices suffer from imperfections that must be accounted for, which hinders the characterization, tuning, and operation process. Moreover, with an increasing number of quantum dot qubits, the relevant parameter space grows sufficiently to make heuristic control infeasible. Thus, it is imperative that reliable and scalable autonomous tuning approaches are developed. In this report, we outline current challenges in automating quantum dot device tuning and operation with a particular focus on datasets, benchmarking, and standardization. We also present ideas put forward by the quantum dot community on how to overcome them.

Decoherence from Long-Range Forces in Atom Interferometry - Jonathan Kunjummen; Daniel Carney; Jacob M. Taylor (Phys. Rev. A, 2023)

Digital quantum simulation of NMR experiments - Seetharam, Kushal; Biswas, Debopriyo; Noel, Crystal; Risinger, Andrew; Zhu, Daiwei; Katz, Or; Chattopadhyay, Sambuddha; Cetina, Marko; Monroe, Christopher; Demler, Eugene; Sels, Dries (Science Advances, 2023)
Simulations of nuclear magnetic resonance (NMR) experiments can be an important tool for extracting information about molecular structure and optimizing experimental protocols but are often intractable on classical computers for large molecules such as proteins and for protocols such as zero-field NMR. We demonstrate the first quantum simulation of an NMR spectrum, computing the zero-field spectrum of the methyl group of acetonitrile using four qubits of a trapped-ion quantum computer. We reduce the sampling cost of the quantum simulation by an order of magnitude using compressed sensing techniques. We show how the intrinsic decoherence of NMR systems may enable the zero-field simulation of classically hard molecules on relatively near-term quantum hardware and discuss how the experimentally demonstrated quantum algorithm can be used to efficiently simulate scientifically and technologically relevant solid-state NMR experiments on more mature devices. Our work opens a practical application for quantum computation.

The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver - Pedro C. S. Costa; Dong An; Ryan Babbush; Dominic Berry (2023)
The solution of linear systems of equations is the basis of many other quantum algorithms, and recent results provided an algorithm with optimal scaling in both the condition number κ and the allowable error ϵ [PRX Quantum \textbf{3}, 0403003 (2022)]. That work was based on the discrete adiabatic theorem, and worked out an explicit constant factor for an upper bound on the complexity. Here we show via numerical testing on random matrices that the constant factor is in practice about 1,500 times smaller than the upper bound found numerically in the previous results. That means that this approach is far more efficient than might naively be expected from the upper bound. In particular, it is over an order of magnitude more efficient than using a randomised approach from [arXiv:2305.11352] that claimed to be more efficient.

DiVincenzo-like criteria for autonomous quantum machines - José Antonio Marín Guzmán; Paul Erker; Simone Gasparinetti; Marcus Huber; Nicole Yunger Halpern (2023)
Controlled quantum machines have matured significantly. A natural next step is to grant them autonomy, freeing them from timed external control. For example, autonomy could unfetter quantum computers from classical control wires that heat and decohere them; and an autonomous quantum refrigerator recently reset superconducting qubits to near their ground states, as is necessary before a computation. What conditions are necessary for realizing useful autonomous quantum machines? Inspired by recent quantum thermodynamics and chemistry, we posit conditions analogous to DiVincenzo's criteria for quantum computing. Our criteria are intended to foment and guide the development of useful autonomous quantum machines.

Effect of non-unital noise on random circuit sampling - Bill Fefferman; Soumik Ghosh; Michael Gullans; Kohdai Kuroiwa; Kunal Sharma (2023)
In this work, drawing inspiration from the type of noise present in real hardware, we study the output distribution of random quantum circuits under practical non-unital noise sources with constant noise rates. We show that even in the presence of unital sources like the depolarizing channel, the distribution, under the combined noise channel, never resembles a maximally entropic distribution at any depth. To show this, we prove that the output distribution of such circuits never anticoncentrates — meaning it is never too "flat" — regardless of the depth of the circuit. This is in stark contrast to the behavior of noiseless random quantum circuits or those with only unital noise, both of which anticoncentrate at sufficiently large depths. As consequences, our results have interesting algorithmic implications on both the hardness and easiness of noisy random circuit sampling, since anticoncentration is a critical property exploited by both state-of-the-art classical hardness and easiness results.

Efficient learning of ground & thermal states within phases of matter - Emilio Onorati; Cambyse Rouzé; Daniel Stilck França; James D. Watson (2023)
We consider two related tasks: (a) estimating a parameterisation of a given Gibbs state and expectation values of Lipschitz observables on this state; and (b) learning the expectation values of local observables within a thermal or quantum phase of matter. In both cases, we wish to minimise the number of samples we use to learn these properties to a given precision. For the first task, we develop new techniques to learn parameterisations of classes of systems, including quantum Gibbs states of non-commuting Hamiltonians with exponential decay of correlations and the approximate Markov property. We show it is possible to infer the expectation values of all extensive properties of the state from a number of copies that not only scales polylogarithmically with the system size, but polynomially in the observable's locality -- an exponential improvement. This set of properties includes expected values of quasi-local observables and entropies.  For the second task, we develop efficient algorithms for learning observables in a phase of matter of a quantum system. By exploiting the locality of the Hamiltonian, we show that M local observables can be learned with probability 1−δ to precision ϵ with using only N=O(log(Mδ)epolylog(ϵ−1)) samples -- an exponential improvement on the precision over previous bounds. Our results apply to both families of ground states of Hamiltonians displaying local topological quantum order, and thermal phases of matter with exponential decay of correlations. In addition, our sample complexity applies to the worse case setting whereas previous results only applied on average. Furthermore, we develop tools of independent interest, such as robust shadow tomography algorithms, Gibbs approximations to ground states, and generalisations of transportation cost inequalities for Gibbs states.

Error Mitigation Thresholds in Noisy Quantum Circuits - Pradeep Niroula; Sarang Gopalakrishnan; Michael Gullans (2023)
Extracting useful information from noisy near-term quantum simulations requires error mitigation strategies. A broad class of these strategies rely on precise characterization of the noise source. We study the performance of such strategies when the noise is imperfectly characterized. We adapt an Imry-Ma argument to predict the existence of an error mitigation threshold for random spatially local circuits in spatial dimensions D≥2: characterization disorder below the threshold rate allows for error mitigation up to times that scale with the number of qubits. For one-dimensional circuits, by contrast, mitigation fails at an O(1) time for any imperfection in the characterization of disorder. We discuss implications for tests of quantum computational advantage, fault-tolerant probes of measurement-induced phase transitions, and quantum algorithms in near-term devices.

Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model - Kelsey A. Jackson; Carl Miller; Daochen Wang (2023)
In the wake of recent progress on quantum computing hardware, the National Institute of Standards and Technology (NIST) is standardizing cryptographic protocols that are resistant to attacks by quantum adversaries. The primary digital signature scheme that NIST has chosen is CRYSTALS-Dilithium. The hardness of this scheme is based on the hardness of three computational problems: Module Learning with Errors (MLWE), Module Short Integer Solution (MSIS), and SelfTargetMSIS. MLWE and MSIS have been well-studied and are widely believed to be secure. However, SelfTargetMSIS is novel and, though classically as hard as MSIS, its quantum hardness is unclear. In this paper, we provide the first proof of the hardness of SelfTargetMSIS via a reduction from MLWE in the Quantum Random Oracle Model (QROM). Our proof uses recently developed techniques in quantum reprogramming and rewinding. A central part of our approach is a proof that a certain hash function, derived from the MSIS problem, is collapsing. From this approach, we deduce a new security proof for Dilithium under appropriate parameter settings. Compared to the only other rigorous security proof for a variant of Dilithium, Dilithium-QROM, our proof has the advantage of being applicable under the condition q = 1 mod 2n, where q denotes the modulus and n the dimension of the underlying algebraic ring. This condition is part of the original Dilithium proposal and is crucial for the efficient implementation of the scheme. We provide new secure parameter sets for Dilithium under the condition q = 1 mod 2n, finding that our public key sizes and signature sizes are about 2.5 to 2.8 times larger than those of Dilithium-QROM for the same security levels.

Ever more optimized simulations of fermionic systems on a quantum computer - Qingfeng Wang; Ze-Pei Cian; Ming Li; Igor L. Markov; Yunseong Nam (2023)
Despite using a novel model of computation, quantum computers break down programs into elementary gates. Among such gates, entangling gates are the most expensive. In the context of fermionic simulations, we develop a suite of compilation and optimization techniques that massively reduce the entangling-gate counts. We exploit the well-studied non-quantum optimization algorithms to achieve up to 24% savings over the state of the art for several small-molecule simulations, with no loss of accuracy or hidden costs. Our methodologies straightforwardly generalize to wider classes of near-term simulations of the ground state of a fermionic system or real-time simulations probing dynamical properties of a fermionic system.

Experimental Observation of Thermalization with Noncommuting Charges - Florian Kranzl; Aleksander Lasek; Manoj K. Joshi; Amir Kalev; Rainer Blatt; Christian F. Roos; Nicole Yunger Halpern (PRX Quantum, 2023)
Quantum simulators have recently enabled experimental observations of quantum many-body systems' internal thermalization. Often, the global energy and particle number are conserved, and the system is prepared with a well-defined particle number - in a microcanonical subspace. However, quantum evolution can also conserve quantities, or charges, that fail to commute with each other. Noncommuting charges have recently emerged as a subfield at the intersection of quantum thermodynamics and quantum information. Until now, this subfield has remained theoretical. We initiate the experimental testing of its predictions, with a trapped-ion simulator. We prepare 6-21 spins in an approximate microcanonical subspace, a generalization of the microcanonical subspace for accommodating noncommuting charges, which cannot necessarily have well-defined nontrivial values simultaneously. We simulate a Heisenberg evolution using laser-induced entangling interactions and collective spin rotations. The noncommuting charges are the three spin components. We find that small subsystems equilibrate to near a recently predicted non-Abelian thermal state. This work bridges quantum many-body simulators to the quantum thermodynamics of noncommuting charges, whose predictions can now be tested.

A family of permutationally invariant quantum codes - Arda Aydin; Max A. Alekseyev; Alexander Barg (2023)
We construct a new family of permutationally invariant codes that correct t Pauli errors for any t≥1. We also show that codes in the new family correct spontaneous decay errors as well as deletion errors. In many cases the codes in this family are shorter than the best previously known explicit families of permutationally invariant codes both for Pauli errors, deletions, and for the amplitude damping channel. As a separate result, we generalize the conditions for permutationally invariant codes to correct t Pauli errors from the previously known results for t=1 to any number of errors. For small t, these conditions can be used to construct new examples of codes by computer.

A Family of Quantum Codes with Exotic Transversal Gates - Eric Kubischta; Ian Teixeira (2023)
Recently it has been shown that the binary icosahedral group 2I together with a certain involution forms the most efficient single-qubit universal gate set. In order for this to be viable, one must construct a quantum code with transversal gate group 2I, however, no such code has ever been demonstrated explicitly. We fill this void by constructing a novel family of quantum codes that all have transversal gate group 2I.

Fat Pointers for Temporal Memory Safety of C - Zhou, Jie; Criswell, John; Hicks, Michael (Proceedings of the ACM on Programming Languages, 2023)
Temporal memory safety bugs, especially use-after-free and double free bugs, pose a major security threat to C programs. Real-world exploits utilizing these bugs enable attackers to read and write arbitrary memory locations, causing disastrous violations of confidentiality, integrity, and availability. Many previous solutions retrofit temporal memory safety to C, but they all either incur high performance overhead and/or miss detecting certain types of temporal memory safety bugs. In this paper, we propose a temporal memory safety solution that is both efficient and comprehensive. Specifically, we extend Checked C, a spatially-safe extension to C, with temporally-safe pointers. These are implemented by combining two techniques: fat pointers and dynamic key-lock checks. We show that the fat-pointer solution significantly improves running time and memory overhead compared to the disjoint-metadata approach that provides the same level of protection. With empirical program data and hands-on experience porting real-world applications, we also show that our solution is practical in terms of backward compatibility -- one of the major complaints about fat pointers.
Keywords: Cryptography and Security (cs.CR); FOS: Computer and information sciences

Fault-tolerant hyperbolic Floquet quantum error correcting codes - Ali Fahimniya; Hossein Dehghani; Kishor Bharti; Sheryl Mathew; Alicia J. Kollár; Alexey V. Gorshkov; Michael Gullans (2023)
A central goal in quantum error correction is to reduce the overhead of fault-tolerant quantum computing by increasing noise thresholds and reducing the number of physical qubits required to sustain a logical qubit. We introduce a potential path towards this goal based on a family of dynamically generated quantum error correcting codes that we call "hyperbolic Floquet codes." These codes are defined by a specific sequence of non-commuting two-body measurements arranged periodically in time that stabilize a topological code on a hyperbolic manifold with negative curvature. We focus on a family of lattices for n qubits that, according to our prescription that defines the code, provably achieve a finite encoding rate (1/8+2/n) and have a depth-3 syndrome extraction circuit. Similar to hyperbolic surface codes, the distance of the code at each time-step scales at most logarithmically in n. The family of lattices we choose indicates that this scaling is achievable in practice. We develop and benchmark an efficient matching-based decoder that provides evidence of a threshold near 0.1% in a phenomenological noise model. Utilizing weight-two check operators and a qubit connectivity of 3, one of our hyperbolic Floquet codes uses 400 physical qubits to encode 52 logical qubits with a code distance of 8, i.e., it is a [[400,52,8]] code. At small error rates, comparable logical error suppression to this code requires 5x as many physical qubits (1924) when using the honeycomb Floquet code with the same noise model and decoder.

Fault-Tolerant Quantum Memory using Low-Depth Random Circuit Codes - Jon Nelson; Gregory Bentsen; Steven T. Flammia; Michael Gullans (2023)
Low-depth random circuit codes possess many desirable properties for quantum error correction but have so far only been analyzed in the code capacity setting where it is assumed that encoding gates and syndrome measurements are noiseless. In this work, we design a fault-tolerant distillation protocol for preparing encoded states of one-dimensional random circuit codes even when all gates and measurements are subject to noise. This is sufficient for fault-tolerant quantum memory since these encoded states can then be used as ancillas for Steane error correction. We show through numerical simulations that our protocol can correct erasure errors up to an error rate of 2%. In addition, we also extend results in the code capacity setting by developing a maximum likelihood decoder for depolarizing noise similar to work by Darmawan et al. As in their work, we formulate the decoding problem as a tensor network contraction and show how to contract the network efficiently by exploiting the low-depth structure. Replacing the tensor network with a so-called ''tropical'' tensor network, we also show how to perform minimum weight decoding. With these decoders, we are able to numerically estimate the depolarizing error threshold of finite-rate random circuit codes and show that this threshold closely matches the hashing bound even when the decoding is sub-optimal.

Feasibility of a trapped atom interferometer with accelerating optical traps - Gayathrini Premawardhana; Jonathan Kunjummen; Sarthak Subhankar; Jacob M. Taylor (2023)
In order to increase the measured phase of an atom interferometer and improve its sensitivity, researchers attempt to increase the enclosed space-time area using two methods: creating larger separations between the interferometer arms and having longer evolution times. However, increasing the evolution time reduces the bandwidth that can be sampled, whereas decreasing the evolution time worsens the sensitivity. In this paper, we attempt to address this by proposing a setup for high-bandwidth applications, with improved overall sensitivity. This is realized by accelerating and holding the atoms using optical dipole traps. We find that accelerations of up to 103-105 m/s2 can be achieved using acousto-optic deflectors (AODs) to move the traps. By comparing the sensitivity of our approach to acceleration as a baseline to traditional atom interferometry, we find a substantial improvement to the state of the art. In the limit of appropriate beam and optics stabilization, sensitivities approaching 10−14 (m/s2)/Hz−−−√ may be achievable at 1 Hz, while detection at 1 kHz with a sensitivity an order of magnitude better than traditional free-fall atom interferometers is possible with today's systems.

Fixing and Mechanizing the Security Proof of Fiat-Shamir with Aborts and Dilithium - Barbosa, Manuel; Barthe, Gilles; Doczkal, Christian; Don, Jelle; Fehr, Serge; Grégoire, Benjamin; Huang, Yu-Hsuan; Hülsing, Andreas; Lee, Yi; Wu, Xiaodi (Advances in Cryptology – CRYPTO 2023, 2023)
We extend and consolidate the security justification for the Dilithium signature scheme. In particular, we identify a subtle but crucial gap that appears in several ROM and QROM security proofs for signature schemes that are based on the Fiat-Shamir with aborts paradigm, including Dilithium. The gap lies in the CMA-to-NMA reduction and was uncovered when trying to formalize a variant of the QROM security proof by Kiltz, Lyubashevsky, and Schaffner (Eurocrypt 2018). The gap was confirmed by the authors, and there seems to be no simple patch for it. We provide new, fixed proofs for the affected CMA-to-NMA reduction, both for the ROM and the QROM, and we perform a concrete security analysis for the case of Dilithium to show that the claimed security level is still valid after addressing the gap. Furthermore, we offer a fully mechanized ROM proof for the CMA-security of Dilithium in the EasyCrypt proof assistant. Our formalization includes several new tools and techniques of independent interest for future formal verification results.

A general approach to backaction-evading receivers with magnetomechanical and electromechanical sensors - Brittany Richman; Sohitri Ghosh; Daniel Carney; Gerard Higgins; Peter Shawhan; C. J. Lobb; Jacob M. Taylor (2023)
Today's mechanical sensors are capable of detecting extremely weak perturbations while operating near the standard quantum limit. However, further improvements can be made in both sensitivity and bandwidth when we reduce the noise originating from the process of measurement itself -- the quantum-mechanical backaction of measurement -- and go below this 'standard' limit, possibly approaching the Heisenberg limit. One of the ways to eliminate this noise is by measuring a quantum nondemolition variable such as the momentum in a free-particle system. Here, we propose and characterize theoretical models for direct velocity measurement that utilize traditional electric and magnetic transducer designs to generate a signal while enabling this backaction evasion. We consider the general readout of this signal via electric or magnetic field sensing by creating toy models analogous to the standard optomechanical position-sensing problem, thereby facilitating the assessment of measurement-added noise. Using simple models that characterize a wide range of transducers, we find that the choice of readout scheme -- voltage or current -- for each mechanical detector configuration implies access to either the position or velocity of the mechanical sub-system. This in turn suggests a path forward for key fundamental physics experiments such as the direct detection of dark matter particles.

General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory - Zohreh Davoudi; Shaw, Alexander F.; Stryker, Jesse R. (Quantum, 2023)
With a focus on universal quantum computing for quantum simulation, and through the example of lattice gauge theories, we introduce rather general quantum algorithms that can efficiently simulate certain classes of interactions consisting of correlated changes in multiple (bosonic and fermionic) quantum numbers with non-trivial functional coefficients. In particular, we analyze diagonalization of Hamiltonian terms using a singular-value decomposition technique, and discuss how the achieved diagonal unitaries in the digitized time-evolution operator can be implemented. The lattice gauge theory studied is the SU(2) gauge theory in 1+1 dimensions coupled to one flavor of staggered fermions, for which a complete quantum-resource analysis within different computational models is presented. The algorithms are shown to be applicable to higher-dimensional theories as well as to other Abelian and non-Abelian gauge theories. The example chosen further demonstrates the importance of adopting efficient theoretical formulations: it is shown that an explicitly gauge-invariant formulation using loop, string, and hadron degrees of freedom simplifies the algorithms and lowers the cost compared with the standard formulations based on angular-momentum as well as the Schwinger-boson degrees of freedom. The loop-string-hadron formulation further retains the non-Abelian gauge symmetry despite the inexactness of the digitized simulation, without the need for costly controlled operations. Such theoretical and algorithmic considerations are likely to be essential in quantumly simulating other complex theories of relevance to nature.

Generalized Hybrid Search and Applications to Blockchain and Hash Function Security - Alexandru Cojocaru; Juan Garay; Fang Song (2023)
In this work we first examine the hardness of solving various search problems by hybrid quantum-classical strategies, namely, by algorithms that have both quantum and classical capabilities. We then construct a hybrid quantum-classical search algorithm and analyze its success probability. Regarding the former, for search problems that are allowed to have multiple solutions and in which the input is sampled according to arbitrary distributions we establish their hybrid quantum-classical query complexities -- i.e., given a fixed number of classical and quantum queries, determine what is the probability of solving the search task. At a technical level, our results generalize the framework for hybrid quantum-classical search algorithms proposed by Rosmanis. Namely, for an arbitrary distribution D on Boolean functions, the probability an algorithm equipped with τc classical and τq quantum queries succeeds in finding a preimage of 1 for a function sampled from D is at most νD⋅(2τc−−√+2τq+1)2, where νD captures the average (over D) fraction of preimages of 1. As applications of our hardness results, we first revisit and generalize the security of the Bitcoin protocol called the Bitcoin backbone, to a setting where the adversary has both quantum and classical capabilities, presenting a new hybrid honest majority condition necessary for the protocol to properly operate. Secondly, we examine the generic security of hash functions against hybrid adversaries. Regarding our second contribution, we design a hybrid algorithm which first spends all of its classical queries and in the second stage runs a ``modified Grover'' where the initial state depends on the distribution D. We show how to analyze its success probability for arbitrary target distributions and, importantly, its optimality for the uniform and the Bernoulli distribution cases.

Hamiltonians whose low-energy states require $Ω(n)$ T gates - Nolan J. Coble; Matthew Coudron; Jon Nelson; Seyed Sajjad Nezhadi (2023)
The recent resolution of the NLTS Conjecture [ABN22] establishes a prerequisite to the Quantum PCP (QPCP) Conjecture through a novel use of newly-constructed QLDPC codes [LZ22]. Even with NLTS now solved, there remain many independent and unresolved prerequisites to the QPCP Conjecture, such as the NLSS Conjecture of [GL22]. In this work we focus on a specific and natural prerequisite to both NLSS and the QPCP Conjecture, namely, the existence of local Hamiltonians whose low-energy states all require ω(logn) T gates to prepare. In fact, we prove a stronger result which is not necessarily implied by either conjecture: we construct local Hamiltonians whose low-energy states require Ω(n) T gates. Following a previous work [CCNN23], we further show that our procedure can be applied to the NLTS Hamiltonians of [ABN22] to yield local Hamiltonians whose low-energy states require both Ω(logn)-depth and Ω(n) T gates to prepare. Our results utilize a connection between T-count and stabilizer groups, which was recently applied in the context of learning low T-count states [GIKL23a, GIKL23b, GIKL23c].

High-Energy Collision of Quarks and Hadrons in the Schwinger Model: From Tensor Networks to Circuit QED - Ron Belyansky; Seth Whitsitt; Niklas Mueller; Ali Fahimniya; Elizabeth R. Bennewitz; Zohreh Davoudi; Alexey V. Gorshkov (2023)
With the aim of studying nonperturbative out-of-equilibrium dynamics of high-energy particle collisions on quantum simulators, we investigate the scattering dynamics of lattice quantum electrodynamics in 1+1 dimensions. Working in the bosonized formulation of the model, we propose an analog circuit-QED implementation that is native to the platform, requires minimal ingredients and approximations, and enables practical schemes for particle wave-packet preparation and evolution. Furthermore, working in the thermodynamic limit, we use uniform-matrix-product-state tensor networks to construct multi-particle wave-packet states, evolve them in time, and detect outgoing particles post collision. This facilitates the numerical simulation of scattering experiments in both confined and deconfined regimes of the model at different energies, giving rise to rich phenomenology, including inelastic production of quark and meson states, meson disintegration, and dynamical string formation and breaking. We obtain elastic and inelastic scattering cross sections, together with time-resolved momentum and position distributions of the outgoing particles. This study highlights the role of classical and quantum simulation in enhancing our understanding of scattering processes in quantum field theories in real time.

Improved Digital Quantum Simulation by Non-Unitary Channels - W. Gong; Yaroslav Kharkov; Minh C. Tran; Przemyslaw Bienias; Alexey V. Gorshkov (2023)
Simulating quantum systems is one of the most promising avenues to harness the computational power of quantum computers. However, hardware errors in noisy near-term devices remain a major obstacle for applications. Ideas based on the randomization of Suzuki-Trotter product formulas have been shown to be a powerful approach to reducing the errors of quantum simulation and lowering the gate count. In this paper, we study the performance of non-unitary simulation channels and consider the error structure of channels constructed from a weighted average of unitary circuits. We show that averaging over just a few simulation circuits can significantly reduce the Trotterization error for both single-step short-time and multi-step long-time simulations. We focus our analysis on two approaches for constructing circuit ensembles for averaging: (i) permuting the order of the terms in the Hamiltonian and (ii) applying a set of global symmetry transformations. We compare our analytical error bounds to empirical performance and show that empirical error reduction surpasses our analytical estimates in most cases. Finally, we test our method on an IonQ trapped-ion quantum computer accessed via the Amazon Braket cloud platform, and benchmark the performance of the averaging approach.

Lattice quantum chromodynamics at large isospin density: 6144 pions in a box - Ryan Abbott; William Detmold; Fernando Romero-López; Zohreh Davoudi; Marc Illa; Assumpta Parreño; Robert J. Perry; Phiala E. Shanahan; Michael L. Wagman (2023)
We present an algorithm to compute correlation functions for systems with the quantum numbers of many identical mesons from lattice quantum chromodynamics (QCD). The algorithm is numerically stable and allows for the computation of n-pion correlation functions for n∈{1,…,N} using a single N×N matrix decomposition, improving on previous algorithms. We apply the algorithm to calculations of correlation functions with up to 6144 π+s using two ensembles of gauge field configurations generated with quark masses corresponding to a pion mass mπ=170 MeV and spacetime volumes of (4.43×8.8) fm4 and (5.83×11.6) fm4. We also discuss statistical techniques for the analysis of such systems, in which the correlation functions vary over many orders of magnitude. In particular, we observe that the many-pion correlation functions are well approximated by log-normal distributions, allowing the extraction of the energies of these systems. Using these energies, the large-isospin-density, zero-baryon-density region of the QCD phase diagram is explored. A peak is observed in the energy density at an isospin chemical potential μI∼1.5mπ, signalling the transition into a Bose-Einstein condensed phase. The isentropic speed of sound in the medium is seen to exceed the ideal-gas (conformal) limit (c2s≤1/3) over a wide range of chemical potential before falling towards the asymptotic expectation at μI∼15mπ. These, and other thermodynamic observables, indicate that the isospin chemical potential must be large for the system to be well described by an ideal gas or perturbative QCD.

Linear combination of Hamiltonian simulation for non-unitary dynamics with optimal state preparation cost - Dong An; Jin-Peng Liu; Lin Lin (Phys. Rev. Lett., 2023)
We propose a simple method for simulating a general class of non-unitary dynamics as a linear combination of Hamiltonian simulation (LCHS) problems. LCHS does not rely on converting the problem into a dilated linear system problem, or on the spectral mapping theorem. The latter is the mathematical foundation of many quantum algorithms for solving a wide variety of tasks involving non-unitary processes, such as the quantum singular value transformation (QSVT). The LCHS method can achieve optimal cost in terms of state preparation. We also demonstrate an application for open quantum dynamics simulation using the complex absorbing potential method with near-optimal dependence on all parameters.

Local Hamiltonians with no low-energy stabilizer states - Nolan J. Coble; Matthew Coudron; Jon Nelson; Seyed Sajjad Nezhadi (2023)
The recently-defined No Low-energy Sampleable States (NLSS) conjecture of Gharibian and Le Gall [GL22] posits the existence of a family of local Hamiltonians where all states of low-enough constant energy do not have succinct representations allowing perfect sampling access. States that can be prepared using only Clifford gates (i.e. stabilizer states) are an example of sampleable states, so the NLSS conjecture implies the existence of local Hamiltonians whose low-energy space contains no stabilizer states. We describe families that exhibit this requisite property via a simple alteration to local Hamiltonians corresponding to CSS codes. Our method can also be applied to the recent NLTS Hamiltonians of Anshu, Breuckmann, and Nirkhe [ABN22], resulting in a family of local Hamiltonians whose low-energy space contains neither stabilizer states nor trivial states. We hope that our techniques will eventually be helpful for constructing Hamiltonians which simultaneously satisfy NLSS and NLTS.

Logical quantum processor based on reconfigurable atom arrays - Bluvstein, Dolev; Evered, Simon J.; Geim, Alexandra A.; Li, Sophie H.; Zhou, Hengyun; Manovitz, Tom; Ebadi, Sepehr; Cain, Madelyn; Kalinowski, Marcin; Dominik Hangleiter; Ataides, J. Pablo Bonilla; Maskara, Nishad; et al. (Nature, 2023)

Lower Bounds on Quantum Annealing Times - García-Pintos, Luis Pedro; Brady, Lucas T.; Bringewatt, Jacob; Liu, Yi-Kai (Phys. Rev. Lett., 2023)
The adiabatic theorem provides sufficient conditions for the time needed to prepare a target ground state. While it is possible to prepare a target state much faster with more general quantum annealing protocols, rigorous results beyond the adiabatic regime are rare. Here, we provide such a result, deriving lower bounds on the time needed to successfully perform quantum annealing. The bounds are asymptotically saturated by three toy models where fast annealing schedules are known: the Roland and Cerf unstructured search model, the Hamming spike problem, and the ferromagnetic p-spin model. Our bounds demonstrate that these schedules have optimal scaling. Our results also show that rapid annealing requires coherent superpositions of energy eigenstates, singling out quantum coherence as a computational resource.
Keywords: FOS: Physical sciences; Quantum Physics (quant-ph)

The maximum refractive index of an atomic crystal - from quantum optics to quantum chemistry - Francesco Andreoli; Bennet Windt; Stefano Grava; Gian Marcello Andolina; Michael Gullans; Alexander A. High; Darrick E. Chang (2023)
All known optical materials have an index of refraction of order unity. Despite the tremendous implications that an ultrahigh index could have for optical technologies, little research has been done on why the refractive index of materials is universally small, and whether this observation is fundamental. Here, we investigate the index of an ordered arrangement of atoms, as a function of atomic density. At dilute densities, this problem falls into the realm of quantum optics, where atoms do not interact with one another except via the scattering of light. On the other hand, when the lattice constant becomes comparable to the Bohr radius, the electronic orbitals begin to overlap, giving rise to quantum chemistry. We present a minimal model that allows for a unifying theory of index spanning these two regimes. A key aspect is the treatment of multiple light scattering, which can be highly non-perturbative over a large density range, and which is the reason that conventional theories of the index break down. In the quantum optics regime, we show that ideal light-matter interactions can have a single-mode nature, allowing for a purely real refractive index that grows with density as (N/V)1/3. At the onset of quantum chemistry, we show how two physical mechanisms (excited electron tunneling dynamics and the buildup of electronic density-density correlations) can open up inelastic or spatial multi-mode light scattering processes, which ultimately reduce the index back to order unity while introducing absorption. Around the onset of chemistry, our theory predicts that ultrahigh index (n∼30), low-loss materials could in principle be allowed by the laws of nature.

Microwave signal processing using an analog quantum reservoir computer - Alen Senanian; Sridhar Prabhu; Vladimir Kremenetski; Saswata Roy; Yingkang Cao; Jeremy Kline; Tatsuhiro Onodera; Logan G. Wright; Xiaodi Wu; Valla Fatemi; Peter L. McMahon (2023)
Quantum reservoir computing (QRC) has been proposed as a paradigm for performing machine learning with quantum processors where the training is efficient in the number of required runs of the quantum processor and takes place in the classical domain, avoiding the issue of barren plateaus in parameterized-circuit quantum neural networks. It is natural to consider using a quantum processor based on superconducting circuits to classify microwave signals that are analog -- continuous in time. However, while theoretical proposals of analog QRC exist, to date QRC has been implemented using circuit-model quantum systems -- imposing a discretization of the incoming signal in time, with each time point input by executing a gate operation. In this paper we show how a quantum superconducting circuit comprising an oscillator coupled to a qubit can be used as an analog quantum reservoir for a variety of classification tasks, achieving high accuracy on all of them. Our quantum system was operated without artificially discretizing the input data, directly taking in microwave signals. Our work does not attempt to address the question of whether QRCs could provide a quantum computational advantage in classifying pre-recorded classical signals. However, beyond illustrating that sophisticated tasks can be performed with a modest-size quantum system and inexpensive training, our work opens up the possibility of achieving a different kind of advantage than a purely computational advantage: superconducting circuits can act as extremely sensitive detectors of microwave photons; our work demonstrates processing of ultra-low-power microwave signals in our superconducting circuit, and by combining sensitive detection with QRC processing within the same system, one could achieve a quantum sensing-computational advantage, i.e., an advantage in the overall analysis of microwave signals comprising just a few photons.

Minimum-entanglement protocols for function estimation - Adam Ehrenberg; Jacob Bringewatt; Alexey V. Gorshkov (Physical Review Research, 2023)
We derive a family of optimal protocols, in the sense of saturating the quantum Cramér-Rao bound, for measuring a linear combination of d field amplitudes with quantum sensor networks, a key subprotocol of general quantum sensor network applications. We demonstrate how to select different protocols from this family under various constraints. Focusing primarily on entanglement-based constraints, we prove the surprising result that highly entangled states are not necessary to achieve optimality in many cases. Specifically, we prove necessary and sufficient conditions for the existence of optimal protocols using at most k-partite entanglement. We prove that the protocols which satisfy these conditions use the minimum amount of entanglement possible, even when given access to arbitrary controls and ancilla. Our protocols require some amount of time-dependent control, and we show that a related class of time-independent protocols fail to achieve optimal scaling for generic functions.

Non-Abelian eigenstate thermalization hypothesis - Murthy, Chaitanya; Babakhani, Arman; Iniguez, Fernando; Srednicki, Mark; Nicole Yunger Halpern (Phys. Rev. Lett., 2023)
The eigenstate thermalization hypothesis (ETH) explains why chaotic quantum many-body systems thermalize internally if the Hamiltonian lacks symmetries. If the Hamiltonian conserves one quantity ("charge"), the ETH implies thermalization within a charge sector -- in a microcanonical subspace. But quantum systems can have charges that fail to commute with each other and so share no eigenbasis; microcanonical subspaces may not exist. Furthermore, the Hamiltonian will have degeneracies, so the ETH need not imply thermalization. We adapt the ETH to noncommuting charges by positing a non-Abelian ETH and invoking the approximate microcanonical subspace introduced in quantum thermodynamics. Illustrating with SU(2) symmetry, we apply the non-Abelian ETH in calculating local observables' time-averaged and thermal expectation values. In many cases, we prove, the time average thermalizes. However, we also find cases in which, under a physically reasonable assumption, the time average converges to the thermal average unusually slowly as a function of the global-system size. This work extends the ETH, a cornerstone of many-body physics, to noncommuting charges, recently a subject of intense activity in quantum thermodynamics.
Keywords: FOS: Physical sciences; High Energy Physics - Theory (hep-th); Quantum Gases (cond-mat.quant-gas); Quantum Physics (quant-ph); Statistical Mechanics (cond-mat.stat-mech); Strongly Correlated Electrons (cond-mat.str-el)

Non-Abelian symmetry can increase entanglement entropy - Shayan Majidy; Aleksander Lasek; David A. Huse; Nicole Yunger Halpern (Physical Review B, 2023)
The pillars of quantum theory include entanglement and operators' failure to commute. The Page curve quantifies the bipartite entanglement of a many-body system in a random pure state. This entanglement is known to decrease if one constrains extensive observables that commute with each other (Abelian ``charges''). Non-Abelian charges, which fail to commute with each other, are of current interest in quantum thermodynamics. For example, noncommuting charges were shown to reduce entropy-production rates and may enhance finite-size deviations from eigenstate thermalization. Bridging quantum thermodynamics to many-body physics, we quantify the effects of charges' noncommutation -- of a symmetry's non-Abelian nature -- on Page curves. First, we construct two models that are closely analogous but differ in whether their charges commute. We show analytically and numerically that the noncommuting-charge case has more entanglement. Hence charges' noncommutation can promote entanglement.

Nonclassical Advantage in Metrology Established via Quantum Simulations of Hypothetical Closed Timelike Curves - Arvidsson-Shukur, David R. M.; McConnell, Aidan G.; Yunger Halpern, Nicole (Phys. Rev. Lett., 2023)
We construct a metrology experiment in which the metrologist can sometimes amend the input state by simulating a closed timelike curve, a worldline that travels backward in time. The existence of closed timelike curves is hypothetical. Nevertheless, they can be simulated probabilistically by quantum-teleportation circuits. We leverage such simulations to pinpoint a counterintuitive nonclassical advantage achievable with entanglement. Our experiment echoes a common information-processing task: A metrologist must prepare probes to input into an unknown quantum interaction. The goal is to infer as much information per probe as possible. If the input is optimal, the information gained per probe can exceed any value achievable classically. The problem is that, only after the interaction does the metrologist learn which input would have been optimal. The metrologist can attempt to change the input by effectively teleporting the optimal input back in time, via entanglement manipulation. The effective time travel sometimes fails but ensures that, summed over trials, the metrologist’s winnings are positive. Our Gedankenexperiment demonstrates that entanglement can generate operational advantages forbidden in classical chronology-respecting theories.

Noncommuting conserved charges in quantum thermodynamics and beyond - Shayan Majidy; William F. Braasch; Aleksander Lasek; Twesh Upadhyaya; Amir Kalev; Nicole Yunger Halpern (Nature Reviews Physics, 2023)
Thermodynamic systems typically conserve quantities ("charges") such as energy and particle number. The charges are often assumed implicitly to commute with each other. Yet quantum phenomena such as uncertainty relations rely on observables' failure to commute. How do noncommuting charges affect thermodynamic phenomena? This question, upon arising at the intersection of quantum information theory and thermodynamics, spread recently across many-body physics. Charges' noncommutation has been found to invalidate derivations of the thermal state's form, decrease entropy production, conflict with the eigenstate thermalization hypothesis, and more. This Perspective surveys key results in, opportunities for, and work adjacent to the quantum thermodynamics of noncommuting charges. Open problems include a conceptual puzzle: Evidence suggests that noncommuting charges may hinder thermalization in some ways while enhancing thermalization in others.

Non-equilibrium critical scaling and universality in a quantum simulator - A. De; P. Cook; K. Collins; W. Morong; D. Paz; P. Titum; G. Pagano; Alexey V. Gorshkov; M. Maghrebi; C. Monroe (2023)
Universality and scaling laws are hallmarks of equilibrium phase transitions and critical phenomena. However, extending these concepts to non-equilibrium systems is an outstanding challenge. Despite recent progress in the study of dynamical phases, the universality classes and scaling laws for non-equilibrium phenomena are far less understood than those in equilibrium. In this work, using a trapped-ion quantum simulator with single-ion resolution, we investigate the non-equilibrium nature of critical fluctuations following a quantum quench to the critical point. We probe the scaling of spin fluctuations after a series of quenches to the critical Hamiltonian of a long-range Ising model. With systems of up to 50 spins, we show that the amplitude and timescale of the post-quench fluctuations scale with system size with distinct universal critical exponents. While a generic quench can lead to thermal critical behaviour, we find that a second quench from one critical state to another (i.e. a double quench) results in critical behaviour that does not have an equilibrium counterpart. Our results demonstrate the ability of quantum simulators to explore universal scaling beyond the equilibrium paradigm.

Non-invertible symmetry-protected topological order in a group-based cluster state - Christopher Fechisin; Nathanan Tantivasadakarn; Victor V. Albert (2023)
Despite growing interest in beyond-group symmetries in quantum condensed matter systems, there are relatively few microscopic lattice models explicitly realizing these symmetries, and many phenomena have yet to be studied at the microscopic level. We introduce a one-dimensional stabilizer Hamiltonian composed of group-based Pauli operators whose ground state is a G×Rep(G)-symmetric state: the G cluster state introduced in Brell, New Journal of Physics 17, 023029 (2015) [at this http URL]. We show that this state lies in a symmetry-protected topological (SPT) phase protected by G×Rep(G) symmetry, distinct from the symmetric product state by a duality argument. We identify several signatures of SPT order, namely protected edge modes, string order parameters, and topological response. We discuss how G cluster states may be used as a universal resource for measurement-based quantum computation, explicitly working out the case where G is a semidirect product of abelian groups.

Observation of a finite-energy phase transition in a one-dimensional quantum simulator - Alexander Schuckert; Or Katz; Lei Feng; Eleanor Crane; Arinjoy De; Mohammad Hafezi; Alexey V. Gorshkov; Christopher Monroe (2023)
One of the most striking many-body phenomena in nature is the sudden change of macroscopic properties as the temperature or energy reaches a critical value. Such equilibrium transitions have been predicted and observed in two and three spatial dimensions, but have long been thought not to exist in one-dimensional (1D) systems. Fifty years ago, Dyson and Thouless pointed out that a phase transition in 1D can occur in the presence of long-range interactions, but an experimental realization has so far not been achieved due to the requirement to both prepare equilibrium states and realize sufficiently long-range interactions. Here we report on the first experimental demonstration of a finite-energy phase transition in 1D. We use the simple observation that finite-energy states can be prepared by time-evolving product initial states and letting them thermalize under the dynamics of a many-body Hamiltonian. By preparing initial states with different energies in a 1D trapped-ion quantum simulator, we study the finite-energy phase diagram of a long-range interacting quantum system. We observe a ferromagnetic equilibrium phase transition as well as a crossover from a low-energy polarized paramagnet to a high-energy unpolarized paramagnet in a system of up to 23 spins, in excellent agreement with numerical simulations. Our work demonstrates the ability of quantum simulators to realize and study previously inaccessible phases at finite energy density.

Page curves and typical entanglement in linear optics - Joseph T. Iosue; Adam Ehrenberg; Dominik Hangleiter; Abhinav Deshpande; Alexey V. Gorshkov (Quantum, 2023)
Bosonic Gaussian states are a special class of quantum states in an infinite dimensional Hilbert space that are relevant to universal continuous-variable quantum computation as well as to near-term quantum sampling tasks such as Gaussian Boson Sampling. In this work, we study entanglement within a set of squeezed modes that have been evolved by a random linear optical unitary. We first derive formulas that are asymptotically exact in the number of modes for the Rényi-2 Page curve (the average Rényi-2 entropy of a subsystem of a pure bosonic Gaussian state) and the corresponding Page correction (the average information of the subsystem) in certain squeezing regimes. We then prove various results on the typicality of entanglement as measured by the Rényi-2 entropy by studying its variance. Using the aforementioned results for the Rényi-2 entropy, we upper and lower bound the von Neumann entropy Page curve and prove certain regimes of entanglement typicality as measured by the von Neumann entropy. Our main proofs make use of a symmetry property obeyed by the average and the variance of the entropy that dramatically simplifies the averaging over unitaries. In this light, we propose future research directions where this symmetry might also be exploited. We conclude by discussing potential applications of our results and their generalizations to Gaussian Boson Sampling and to illuminating the relationship between entanglement and computational complexity.

Parallel self-testing of EPR pairs under computational assumptions - Honghao Fu; Daochen Wang; Qi Zhao (2023)
Self-testing is a fundamental feature of quantum mechanics that allows a classical verifier to force untrusted quantum devices to prepare certain states and perform certain measurements on them. The standard approach assumes at least two spatially separated devices. Recently, Metger and Vidick [Quantum, 2021] showed that a single EPR pair of a single quantum device can be self-tested under computational assumptions. In this work, we generalize their results to give the first parallel self-test of N EPR pairs and measurements on them in the single-device setting under the same computational assumptions. We show that our protocol can be passed with probability negligibly close to 1 by an honest quantum device using poly(N) resources. Moreover, we show that any quantum device that fails our protocol with probability at most ϵ must be poly(N,ϵ)-close to being honest in the appropriate sense. In particular, our protocol can test any distribution over tensor products of computational or Hadamard basis measurements, making it suitable for applications such as device-independent quantum key distribution under computational assumptions. Moreover, a simplified version of our protocol is the first that can efficiently certify an arbitrary number of qubits of a single cloud quantum computer using only classical communication.

Parallel self-testing of EPR pairs under computational assumptions - Honghao Fu; Daochen Wang; Qi Zhao (2023)
Self-testing is a fundamental feature of quantum mechanics that allows a classical verifier to force untrusted quantum devices to prepare certain states and perform certain measurements on them. The standard approach assumes at least two spatially separated devices. Recently, Metger and Vidick [Quantum, 2021] showed that a single EPR pair of a single quantum device can be self-tested under computational assumptions. In this work, we generalize their results to give the first parallel self-test of N EPR pairs and measurements on them in the single-device setting under the same computational assumptions. We show that our protocol can be passed with probability negligibly close to 1 by an honest quantum device using poly(N) resources. Moreover, we show that any quantum device that fails our protocol with probability at most ϵ must be poly(N,ϵ)-close to being honest in the appropriate sense. In particular, our protocol can test any distribution over tensor products of computational or Hadamard basis measurements, making it suitable for applications such as device-independent quantum key distribution under computational assumptions. Moreover, a simplified version of our protocol is the first that can efficiently certify an arbitrary number of qubits of a single cloud quantum computer using only classical communication.

Parallelization techniques for quantum simulation of fermionic systems - Jacob Bringewatt; Zohreh Davoudi (2023)
Mapping fermionic operators to qubit operators is an essential step for simulating fermionic systems on a quantum computer. We investigate how the choice of such a mapping interacts with the underlying qubit connectivity of the quantum processor to enable (or impede) parallelization of the resulting Hamiltonian-simulation algorithm. It is shown that this problem can be mapped to a path coloring problem on a graph constructed from the particular choice of encoding fermions onto qubits and the fermionic interactions onto paths. The basic version of this problem is called the weak coloring problem. Taking into account the fine-grained details of the mapping yields what is called the strong coloring problem, which leads to improved parallelization performance. A variety of illustrative analytical and numerical examples are presented to demonstrate the amount of improvement for both weak and strong coloring-based parallelizations. Our results are particularly important for implementation on near-term quantum processors where minimizing circuit depth is necessary for algorithmic feasibility.

Partial Syndrome Measurement for Hypergraph Product Codes - Noah Berthusen; Daniel Gottesman (2023)
Hypergraph product codes are a promising avenue to achieving fault-tolerant quantum computation with constant overhead. When embedding these and other constant-rate qLDPC codes into 2D, a significant number of nonlocal connections are required, posing difficulties for some quantum computing architectures. In this work, we introduce a fault-tolerance scheme that aims to alleviate the effects of implementing this nonlocality by measuring generators acting on spatially distant qubits less frequently than those which do not. We investigate the performance of a simplified version of this scheme, where the measured generators are randomly selected. When applied to hypergraph product codes and a modified small-set-flip decoding algorithm, we prove that for a sufficiently high percentage of generators being measured, a threshold still exists. We also find numerical evidence that the logical error rate is exponentially suppressed even when a large constant fraction of generators are not measured.

Projective toric designs, difference sets, and quantum state designs - Joseph T. Iosue; T. C. Mooney; Adam Ehrenberg; Alexey V. Gorshkov (2023)
Trigonometric cubature rules of degree t are sets of points on the torus over which sums reproduce integrals of degree t monomials over the full torus. They can be thought of as t-designs on the torus. Motivated by the projective structure of quantum mechanics, we develop the notion of t-designs on the projective torus, which, surprisingly, have a much more restricted structure than their counterparts on full tori. We provide various constructions of these projective toric designs and prove some bounds on their size and characterizations of their structure. We draw connections between projective toric designs and a diverse set of mathematical objects, including difference and Sidon sets from the field of additive combinatorics, symmetric, informationally complete positive operator valued measures (SIC-POVMs) and complete sets of mutually unbiased bases (MUBs) (which are conjectured to relate to finite projective geometry) from quantum information theory, and crystal ball sequences of certain root lattices. Using these connections, we prove bounds on the maximal size of dense Btmodm sets. We also use projective toric designs to construct families of quantum state designs. Finally, we discuss many open questions about the properties of these projective toric designs and how they relate to other questions in number theory, geometry, and quantum information.

Provably Efficient Learning of Phases of Matter via Dissipative Evolutions - Emilio Onorati; Cambyse Rouzé; Daniel Stilck França; James D. Watson (2023)
The combination of quantum many-body and machine learning techniques has recently proved to be a fertile ground for new developments in quantum computing. Several works have shown that it is possible to classically efficiently predict the expectation values of local observables on all states within a phase of matter using a machine learning algorithm after learning from data obtained from other states in the same phase. However, existing results are restricted to phases of matter such as ground states of gapped Hamiltonians and Gibbs states that exhibit exponential decay of correlations. In this work, we drop this requirement and show how it is possible to learn local expectation values for all states in a phase, where we adopt the Lindbladian phase definition by Coser \& Pérez-García [Coser \& Pérez-García, Quantum 3, 174 (2019)], which defines states to be in the same phase if we can drive one to other rapidly with a local Lindbladian. This definition encompasses the better-known Hamiltonian definition of phase of matter for gapped ground state phases, and further applies to any family of states connected by short unitary circuits, as well as non-equilibrium phases of matter, and those stable under external dissipative interactions. Under this definition, we show that N=O(log(n/δ)2polylog(1/ϵ)) samples suffice to learn local expectation values within a phase for a system with n qubits, to error ϵ with failure probability δ. This sample complexity is comparable to previous results on learning gapped and thermal phases, and it encompasses previous results of this nature in a unified way. Furthermore, we also show that we can learn families of states which go beyond the Lindbladian definition of phase, and we derive bounds on the sample complexity which are dependent on the mixing time between states under a Lindbladian evolution.

Qafny: Quantum Program Verification Through Type-guided Classical Separation Logic - Liyi Li; Mingwei Zhu; Rance Cleaveland; Yi Lee; Le Chang; Xiaodi Wu (2023)
Formal verification has been proven instrumental to ensure that quantum programs implement their specifications but often requires a significant investment of time and labor. To address this challenge, we present Qafny, an automated proof system designed for verifying quantum programs. At its core, Qafny uses a type-guided quantum proof system that translates quantum operations to classical array operations. By modeling these operations as proof rules within a classical separation logic framework, Qafny provides automated support for the reasoning process that would otherwise be tedious and time-consuming. We prove the soundness and completeness of our proof system and implement a prototype compiler that transforms Qafny programs both into the Dafny programming language and into executable quantum circuits. Using Qafny, we demonstrate how to efficiently verify prominent quantum algorithms, including quantum-walk algorithms, Grover's search algorithm, and Shor's factoring algorithm, with significantly reduced human efforts.

Quantum algorithm for estimating volumes of convex bodies - Shouvanik Chakrabarti; Andrew M. Childs; Shih-Han Hung; Tongyang Li; Chunhao Wang; Xiaodi Wu (ACM Transactions on Quantum Computing, 2023)
Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates the volume of an n-dimensional convex body within multiplicative error ε using O~(n3.5+n2.5/ε) queries to a membership oracle and O~(n5.5+n4.5/ε) additional arithmetic operations. For comparison, the best known classical algorithm uses O~(n4+n3/ε2) queries and O~(n6+n5/ε2) additional arithmetic operations. To the best of our knowledge, this is the first quantum speedup for volume estimation. Our algorithm is based on a refined framework for speeding up simulated annealing algorithms that might be of independent interest. This framework applies in the setting of "Chebyshev cooling", where the solution is expressed as a telescoping product of ratios, each having bounded variance. We develop several novel techniques when implementing our framework, including a theory of continuous-space quantum walks with rigorous bounds on discretization error.

Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters - Dong An; Andrew M. Childs; Lin Lin (2023)
We introduce a family of identities that express general linear non-unitary evolution operators as a linear combination of unitary evolution operators, each solving a Hamiltonian simulation problem. This formulation can exponentially enhance the accuracy of the recently introduced linear combination of Hamiltonian simulation (LCHS) method [An, Liu, and Lin, Physical Review Letters, 2023]. For the first time, this approach enables quantum algorithms to solve linear differential equations with both optimal state preparation cost and near-optimal scaling in matrix queries on all parameters.

Quantum Algorithms and the Power of Forgetting - Andrew M. Childs; Coudron, Matthew; Gilani, Amin Shiraz (14th Innovations in Theoretical Computer Science Conference (ITCS 2023), 2023)
The so-called welded tree problem provides an example of a black-box problem that can be solved exponentially faster by a quantum walk than by any classical algorithm [Andrew M. Childs et al., 2003]. Given the name of a special entrance vertex, a quantum walk can find another distinguished exit vertex using polynomially many queries, though without finding any particular path from entrance to exit. It has been an open problem for twenty years whether there is an efficient quantum algorithm for finding such a path, or if the path-finding problem is hard even for quantum computers. We show that a natural class of efficient quantum algorithms provably cannot find a path from entrance to exit. Specifically, we consider algorithms that, within each branch of their superposition, always store a set of vertex labels that form a connected subgraph including the entrance, and that only provide these vertex labels as inputs to the oracle. While this does not rule out the possibility of a quantum algorithm that efficiently finds a path, it is unclear how an algorithm could benefit by deviating from this behavior. Our no-go result suggests that, for some problems, quantum algorithms must necessarily forget the path they take to reach a solution in order to outperform classical computation.

Quantum Algorithms for Simulating Nuclear Effective Field Theories - James D. Watson; Jacob Bringewatt; Alexander F. Shaw; Andrew M. Childs; Alexey V. Gorshkov; Zohreh Davoudi (2023)
Quantum computers offer the potential to simulate nuclear processes that are classically intractable. With the goal of understanding the necessary quantum resources, we employ state-of-the-art Hamiltonian-simulation methods, and conduct a thorough algorithmic analysis, to estimate the qubit and gate costs to simulate low-energy effective field theories (EFTs) of nuclear physics. In particular, within the framework of nuclear lattice EFT, we obtain simulation costs for the leading-order pionless and pionful EFTs. We consider both static pions represented by a one-pion-exchange potential between the nucleons, and dynamical pions represented by relativistic bosonic fields coupled to non-relativistic nucleons. We examine the resource costs for the tasks of time evolution and energy estimation for physically relevant scales. We account for model errors associated with truncating either long-range interactions in the one-pion-exchange EFT or the pionic Hilbert space in the dynamical-pion EFT, and for algorithmic errors associated with product-formula approximations and quantum phase estimation. Our results show that the pionless EFT is the least costly to simulate and the dynamical-pion theory is the costliest. We demonstrate how symmetries of the low-energy nuclear Hamiltonians can be utilized to obtain tighter error bounds on the simulation algorithm. By retaining the locality of nucleonic interactions when mapped to qubits, we achieve reduced circuit depth and substantial parallelization. We further develop new methods to bound the algorithmic error for classes of fermionic Hamiltonians that preserve the number of fermions, and demonstrate that reasonably tight Trotter error bounds can be achieved by explicitly computing nested commutators of Hamiltonian terms. This work highlights the importance of combining physics insights and algorithmic advancement in reducing quantum-simulation costs.

A quantum central path algorithm for linear optimization - Brandon Augustino; Jiaqi Leng; Giacomo Nannicini; Tamás Terlaky; Xiaodi Wu (2023)
We propose a novel quantum algorithm for solving linear optimization problems by quantum-mechanical simulation of the central path. While interior point methods follow the central path with an iterative algorithm that works with successive linearizations of the perturbed KKT conditions, we perform a single simulation working directly with the nonlinear complementarity equations. Combining our approach with iterative refinement techniques, we obtain an exact solution to a linear optimization problem involving m constraints and n variables using at most O((m+n)nnz(A)κ(M)L⋅polylog(m,n,κ(M))) elementary gates and O(nnz(A)L) classical arithmetic operations, where nnz(A) is the total number of non-zero elements found in the constraint matrix, L denotes binary input length of the problem data, and κ(M) is a condition number that depends only on the problem data.

Quantum computation of dynamical quantum phase transitions and entanglement tomography in a lattice gauge theory - Niklas Mueller; Joseph Carolan; Andrew Connelly; Zohreh Davoudi; Eugene F. Dumitrescu; Kübra Yeter-Aydeniz (2023)
Strongly-coupled gauge theories far from equilibrium may exhibit unique features that could illuminate the physics of the early universe and of hadron and ion colliders. Studying real-time phenomena has proven challenging with classical-simulation methods, but is a natural application of quantum simulation. To demonstrate this prospect, we quantum compute non-equal time correlation functions and perform entanglement tomography of non-equilibrium states of a simple lattice gauge theory, the Schwinger model, using a trapped-ion quantum computer by IonQ Inc. As an ideal target for near-term devices, a recently-predicted [Zache et al., Phys. Rev. Lett. 122, 050403 (2019)] dynamical quantum phase transition in this model is studied by preparing, quenching, and tracking the subsequent non-equilibrium dynamics in three ways: i) overlap echos signaling dynamical transitions, ii) non-equal time correlation functions with an underlying topological nature, and iii) the entanglement structure of non-equilibrium states, including entanglement Hamiltonians. These results constitute the first observation of a dynamical quantum phase transition in a lattice gauge theory on a quantum computer, and are a first step toward investigating topological phenomena in nuclear and high-energy physics using quantum technologies.

Quantum Hamiltonian Descent - Jiaqi Leng; Ethan Hickman; Joseph Li; Xiaodi Wu (2023)
Gradient descent is a fundamental algorithm in both theory and practice for continuous optimization. Identifying its quantum counterpart would be appealing to both theoretical and practical quantum applications. A conventional approach to quantum speedups in optimization relies on the quantum acceleration of intermediate steps of classical algorithms, while keeping the overall algorithmic trajectory and solution quality unchanged. We propose Quantum Hamiltonian Descent (QHD), which is derived from the path integral of dynamical systems referring to the continuous-time limit of classical gradient descent algorithms, as a truly quantum counterpart of classical gradient methods where the contribution from classically-prohibited trajectories can significantly boost QHD's performance for non-convex optimization. Moreover, QHD is described as a Hamiltonian evolution efficiently simulatable on both digital and analog quantum computers. By embedding the dynamics of QHD into the evolution of the so-called Quantum Ising Machine (including D-Wave and others), we empirically observe that the D-Wave-implemented QHD outperforms a selection of state-of-the-art gradient-based classical solvers and the standard quantum adiabatic algorithm, based on the time-to-solution metric, on non-convex constrained quadratic programming instances up to 75 dimensions. Finally, we propose a "three-phase picture" to explain the behavior of QHD, especially its difference from the quantum adiabatic algorithm.

Quantum Lego Expansion Pack: Enumerators from Tensor Networks - ChunJun Cao; Michael Gullans; Brad Lackey; Zitao Wang (2023)
We provide the first tensor network method for computing quantum weight enumerator polynomials in the most general form. As a corollary, if a quantum code has a known tensor network construction of its encoding map, our method produces an algorithm that computes its distance. For non-(Pauli)-stabilizer codes, this constitutes the current best algorithm for computing the code distance. For degenerate stabilizer codes, it can provide up to an exponential speed up compared to the current methods. We also introduce a few novel applications of different weight enumerators. In particular, for any code built from the quantum lego method, we use enumerators to construct its (optimal) decoders under any i.i.d. single qubit or qudit error channels and discuss their applications for computing logical error rates. As a proof of principle, we perform exact analyses of the deformed surface codes, the holographic pentagon code, and the 2d Bacon-Shor code under (biased) Pauli noise and limited instances of coherent error at sizes that are inaccessible by brute force.

Quantum Sensing with Erasure Qubits - Pradeep Niroula; Jack Dolde; Xin Zheng; Jacob Bringewatt; Adam Ehrenberg; Kevin C. Cox; Jeff Thompson; Michael Gullans; Shimon Kolkowitz; Alexey V. Gorshkov (2023)
The dominant noise in an "erasure qubit" is an erasure -- a type of error whose occurrence and location can be detected. Erasure qubits have potential to reduce the overhead associated with fault tolerance. To date, research on erasure qubits has primarily focused on quantum computing and quantum networking applications. Here, we consider the applicability of erasure qubits to quantum sensing and metrology. We show theoretically that, for the same level of noise, an erasure qubit acts as a more precise sensor or clock compared to its non-erasure counterpart. We experimentally demonstrate this by artificially injecting either erasure errors (in the form of atom loss) or dephasing errors into a differential optical lattice clock comparison, and observe enhanced precision in the case of erasure errors for the same injected error rate. Similar benefits of erasure qubits to sensing can be realized in other quantum platforms like Rydberg atoms and superconducting qubits

Quantum Simulating Nature's Fundamental Fields - Christian W. Bauer; Zohreh Davoudi; Natalie Klco; Martin J. Savage (Nature Reviews Physics, 2023)
Simulating key static and dynamic properties of matter -- from creation in the Big Bang to evolution into sub-atomic and astrophysical environments -- arising from the underlying fundamental quantum fields of the Standard Model and their effective descriptions, lies beyond the capabilities of classical computation alone. Advances in quantum technologies have improved control over quantum entanglement and coherence to the point where robust simulations are anticipated to be possible in the foreseeable future. We discuss the emerging area of quantum simulations of Standard-Model physics, challenges that lie ahead, and opportunities for progress in the context of nuclear and high-energy physics.

Quantum simulations of time travel can power nonclassical metrology - David R. M. Arvidsson-Shukur; Aidan G. McConnell; Nicole Yunger Halpern (Phys. Rev. Lett., 2023)
We construct a metrology experiment in which the metrologist can sometimes amend her input state by simulating a closed timelike curve, a worldline that travels backward in time. The existence of closed timelike curves is hypothetical. Nevertheless, they can be simulated probabilistically by quantum-teleportation circuits. We leverage such simulations to pinpoint a counterintuitive nonclassical advantage achievable with entanglement. Our experiment echoes a common information-processing task: A metrologist must prepare probes to input into an unknown quantum interaction. The goal is to infer as much information per probe as possible. If the input is optimal, the information gained per probe can exceed any value achievable classically. The problem is that, only after the interaction does the metrologist learn which input would have been optimal. The metrologist can attempt to change her input by effectively teleporting the optimal input back in time, via entanglement manipulation. The effective time travel sometimes fails but ensures that, summed over trials, the metrologist's winnings are positive. Our Gedankenexperiment demonstrates that entanglement can generate operational advantages forbidden in classical chronology-respecting theories.

Quantum spherical codes - Shubham P. Jain; Joseph T. Iosue; Alexander Barg; Victor V. Albert (2023)
We introduce a framework for constructing quantum codes defined on spheres by recasting such codes as quantum analogues of the classical spherical codes. We apply this framework to bosonic coding, obtaining multimode extensions of the cat codes that can outperform previous constructions while requiring a similar type of overhead. Our polytope-based cat codes consist of sets of points with large separation that at the same time form averaging sets known as spherical designs. We also recast concatenations of CSS codes with cat codes as quantum spherical codes, revealing a new way to autonomously protect against dephasing noise

Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions - Yuri Alexeev; Maximilian Amsler; Paul Baity; Marco Antonio Barroca; Sanzio Bassini; Torey Battelle; Daan Camps; David Casanova; Young jai Choi; Frederic T. Chong; Charles Chung; Chris Codella; et al. (2023)
Computational models are an essential tool for the design, characterization, and discovery of novel materials. Hard computational tasks in materials science stretch the limits of existing high-performance supercomputing centers, consuming much of their simulation, analysis, and data resources. Quantum computing, on the other hand, is an emerging technology with the potential to accelerate many of the computational tasks needed for materials science. In order to do that, the quantum technology must interact with conventional high-performance computing in several ways: approximate results validation, identification of hard problems, and synergies in quantum-centric supercomputing. In this paper, we provide a perspective on how quantum-centric supercomputing can help address critical computational problems in materials science, the challenges to face in order to solve representative use cases, and new suggested directions.

A quantum-classical performance separation in nonconvex optimization - Jiaqi Leng; Yufan Zheng; Xiaodi Wu (2023)
In this paper, we identify a family of nonconvex continuous optimization instances, each d-dimensional instance with 2d local minima, to demonstrate a quantum-classical performance separation. Specifically, we prove that the recently proposed Quantum Hamiltonian Descent (QHD) algorithm [Leng et al., arXiv:2303.01471] is able to solve any d-dimensional instance from this family using O˜(d3) quantum queries to the function value and O˜(d4) additional 1-qubit and 2-qubit elementary quantum gates. On the other side, a comprehensive empirical study suggests that representative state-of-the-art classical optimization algorithms/solvers (including Gurobi) would require a super-polynomial time to solve such optimization instances.

Qubit-Oscillator Concatenated Codes: Decoding Formalism and Code Comparison - Xu, Yijia; Wang, Yixu; Kuo, En-Jui; Victor V. Albert (PRX Quantum, 2023)
Concatenating bosonic error-correcting codes with qubit codes can substantially boost the error-correcting power of the original qubit codes. It is not clear how to concatenate optimally, given that there are several bosonic codes and concatenation schemes to choose from, including the recently discovered Gottesman-Kitaev-Preskill (GKP) – stabilizer codes [Phys. Rev. Lett. 125, 080503 (2020)] that allow protection of a logical bosonic mode from fluctuations of the conjugate variables of the mode. We develop efficient maximum-likelihood decoders for and analyze the performance of three different concatenations of codes taken from the following set: qubit stabilizer codes, analog or Gaussian stabilizer codes, GKP codes, and GKP-stabilizer codes. We benchmark decoder performance against additive Gaussian white noise, corroborating our numerics with analytical calculations. We observe that the concatenation involving GKP-stabilizer codes outperforms the more conventional concatenation of a qubit stabilizer code with a GKP code in some cases. We also propose a GKP-stabilizer code that suppresses fluctuations in both conjugate variables without extra quadrature squeezing and formulate qudit versions of GKP-stabilizer codes.

Random Pulse Sequences for Qubit Noise Spectroscopy - Kaixin Huang; Demitry Farfurnik; Alireza Seif; Mohammad Hafezi; Yi-Kai Liu (2023)
Qubit noise spectroscopy is an important tool for the experimental investigation of open quantum systems. However, conventional techniques for implementing noise spectroscopy are time-consuming, because they require multiple measurements of the noise spectral density at different frequencies. Here we describe an alternative method for quickly characterizing the spectral density. Our method utilizes random pulse sequences, with carefully-controlled correlations among the pulses, to measure arbitrary linear functionals of the noise spectrum. Such measurements allow us to estimate k'th-order moments of the noise spectrum, as well as to reconstruct sparse noise spectra via compressed sensing. Our simulations of the performance of the random pulse sequences on a realistic physical system, self-assembled quantum dots, reveal a speedup of an order of magnitude in extracting the noise spectrum compared to conventional dynamical decoupling approaches.

On the Rational Degree of Boolean Functions and Applications - Vishnu Iyer; Siddhartha Jain; Matt Kovacs-Deak; Vinayak M. Kumar; Luke Schaeffer; Daochen Wang; Michael Whitmeyer (2023)
We study a natural complexity measure of Boolean functions known as the (exact) rational degree. For total functions f, it is conjectured that rdeg(f) is polynomially related to deg(f), where deg(f) is the Fourier degree. Towards this conjecture, we show that symmetric functions have rational degree at least deg(f)/2 and monotone functions have rational degree at least deg(f)−−−−−√. We observe that both of these lower bounds are tight. In addition, we show that all read-once depth-d Boolean formulae have rational degree at least Ω(deg(f)1/d). Furthermore, we show that almost every Boolean function on n variables has rational degree at least n/2−O(n−−√). In contrast to total functions, we exhibit partial functions that witness unbounded separations between rational and approximate degree, in both directions. As a consequence, we show that for quantum computers, post-selection and bounded-error are incomparable resources in the black-box model.

Realization of 1D Anyons with Arbitrary Statistical Phase - Joyce Kwan; Perrin Segura; Yanfei Li; Sooshin Kim; Alexey V. Gorshkov; André Eckardt; Brice Bakkali-Hassani; Markus Greiner (2023)
Low-dimensional quantum systems can host anyons, particles with exchange statistics that are neither bosonic nor fermionic. Despite indications of a wealth of exotic phenomena, the physics of anyons in one dimension (1D) remains largely unexplored. Here, we realize Abelian anyons in 1D with arbitrary exchange statistics using ultracold atoms in an optical lattice, where we engineer the statistical phase via a density-dependent Peierls phase. We explore the dynamical behavior of two anyons undergoing quantum walks, and observe the anyonic Hanbury Brown-Twiss effect, as well as the formation of bound states without on-site interactions. Once interactions are introduced, we observe spatially asymmetric transport in contrast to the symmetric dynamics of bosons and fermions. Our work forms the foundation for exploring the many-body behavior of 1D anyons.

Secret extraction attacks against obfuscated IQP circuits - David Gross; Dominik Hangleiter (2023)
Quantum computing devices can now perform sampling tasks which, according to complexity-theoretic and numerical evidence, are beyond the reach of classical computers. This raises the question of how one can efficiently verify that a quantum computer operating in this regime works as intended. In 2008, Shepherd and Bremner proposed a protocol in which a verifier constructs a unitary from the comparatively easy-to-implement family of so-called IQP circuits, and challenges a prover to execute it on a quantum computer. The challenge problem is designed to contain an obfuscated secret, which can be turned into a statistical test that accepts samples from a correct quantum implementation. It was conjectured that extracting the secret from the challenge problem is NP-hard, so that the ability to pass the test constitutes strong evidence that the prover possesses a quantum device and that it works as claimed. Unfortunately, about a decade later, Kahanamoku-Meyer found an efficient classical secret extraction attack. Bremner, Cheng, and Ji very recently followed up by constructing a wide-ranging generalization of the original protocol. Their IQP Stabilizer Scheme has been explicitly designed to circumvent the known weakness. They also suggested that the original construction can be made secure by adjusting the problem parameters. In this work, we develop a number of secret extraction attacks which are effective against both new approaches in a wide range of problem parameters. The important problem of finding an efficient and reliable verification protocol for sampling-based proofs of quantum supremacy thus remains open.

Self-dual quasiperiodic percolation - Sommers, Grace M.; Michael Gullans; Huse, David A. (Phys. Rev. E, 2023)
How does the percolation transition behave in the absence of quenched randomness? To address this question, we study two nonrandom self-dual quasiperiodic models of square-lattice bond percolation. In both models, the critical point has emergent discrete scale invariance, but none of the additional emergent conformal symmetry of critical random percolation. From the discrete sequences of critical clusters, we find fractal dimensions of Df=1.911943(1) and Df=1.707234(40) for the two models, significantly different from Df=91/48=1.89583... of random percolation. The critical exponents ν, determined through a numerical study of cluster sizes and wrapping probabilities on a torus, are also well below the ν=4/3 of random percolation. While these new models do not appear to belong to a universality class, they demonstrate how the removal of randomness can fundamentally change the critical behavior.

Shadow process tomography of quantum channels - Jonathan Kunjummen; Minh C. Tran; Daniel Carney; Jacob M. Taylor (Phys. Rev. A, 2023)
Quantum process tomography is a critical capability for building quantum computers, enabling quantum networks, and understanding quantum sensors. Like quantum state tomography, the process tomography of an arbitrary quantum channel requires a number of measurements that scale exponentially in the number of quantum bits affected. However, the recent field of shadow tomography, applied to quantum states, has demonstrated the ability to extract key information about a state with only polynomially many measurements. In this work, we apply the concepts of shadow state tomography to the challenge of characterizing quantum processes. We make use of the Choi isomorphism to directly apply rigorous bounds from shadow state tomography to shadow process tomography, and we find additional bounds on the number of measurements that are unique to process tomography. Our results, which include algorithms for implementing shadow process tomography enable new techniques including evaluation of channel concatenation and the application of channels to shadows of quantum states. This provides a dramatic improvement for understanding large-scale quantum systems.

A sharp phase transition in linear cross-entropy benchmarking - Brayden Ware; Abhinav Deshpande; Dominik Hangleiter; Pradeep Niroula; Bill Fefferman; Alexey V. Gorshkov; Michael Gullans (2023)
Demonstrations of quantum computational advantage and benchmarks of quantum processors via quantum random circuit sampling are based on evaluating the linear cross-entropy benchmark (XEB). A key question in the theory of XEB is whether it approximates the fidelity of the quantum state preparation. Previous works have shown that the XEB generically approximates the fidelity in a regime where the noise rate per qudit ε satisfies εN≪1 for a system of N qudits and that this approximation breaks down at large noise rates. Here, we show that the breakdown of XEB as a fidelity proxy occurs as a sharp phase transition at a critical value of εN that depends on the circuit architecture and properties of the two-qubit gates, including in particular their entangling power. We study the phase transition using a mapping of average two-copy quantities to statistical mechanics models in random quantum circuit architectures with full or one-dimensional connectivity. We explain the phase transition behavior in terms of spectral properties of the transfer matrix of the statistical mechanics model and identify two-qubit gate sets that exhibit the largest noise robustness.

SimuQ: A Domain-Specific Language For Quantum Simulation With Analog Compilation - Yuxiang Peng; Jacob Young; Pengyu Liu; Xiaodi Wu (2023)
Hamiltonian simulation is one of the most promising applications of quantum computing. Recent experimental results suggest that continuous-time analog quantum simulation would be advantageous over gate-based digital quantum simulation in the Noisy Intermediate-Size Quantum (NISQ) machine era. However, programming such analog quantum simulators is much more challenging due to the lack of a unified interface between hardware and software, and the only few known examples are all hardware-specific. In this paper, we design and implement SimuQ, the first domain-specific language for Hamiltonian simulation that supports pulse-level compilation to heterogeneous analog quantum simulators. Specifically, in SimuQ, front-end users will specify the target Hamiltonian evolution with a Hamiltonian modeling language, and the programmability of analog simulators is specified through a new abstraction called the abstract analog instruction set by hardware providers. Through a solver-based compilation, SimuQ will generate the pulse-level instruction schedule on the target analog simulator for the desired Hamiltonian evolution, which has been demonstrated on pulse-controlled superconducting (Qiskit Pulse) and neutral-atom (QuEra Bloqade) quantum systems, as well as on normal circuit-based digital quantum machines. Moreover, we also demonstrate the advantage of analog compilation over digital compilation on IBM machines, the use of SimuQ for resource estimation for hypothetical machines, and a scalability test of SimuQ's compilation.

Spin-selective strong light-matter coupling in a 2D hole gas-microcavity system - Daniel G. Suarez-Forero; Deric Weston Session; Mahmoud Jalali Mehrabad; Patrick Knuppel; Stefan Faelt; Werner Wegscheider; Mohammad Hafezi (2023)
The interplay between time-reversal symmetry breaking and strong light-matter coupling in 2D gases brings intriguing aspects to polariton physics. This combination can lead to polarization/spin selective light-matter interaction in the strong coupling regime. In this work, we report such a selective strong light-matter interaction by harnessing a 2D gas in the quantum Hall regime coupled to a microcavity. Specifically, we demonstrate circular-polarization dependence of the vacuum Rabi splitting, as a function of magnetic field and hole density. We provide a quantitative understanding of the phenomenon by modeling the coupling of optical transitions between Landau levels to the microcavity. This method introduces a control tool over the spin degree of freedom in polaritonic semiconductor systems, paving the way for new experimental possibilities in light-matter hybrids.

On the stability of solutions to Schrödinger's equation short of the adiabatic limit - Jacob Bringewatt; Michael Jarret; T. C. Mooney (2023)
We prove an adiabatic theorem that applies at timescales short of the adiabatic limit. Our proof analyzes the stability of solutions to Schrodinger's equation under perturbation. We directly characterize cross-subspace effects of perturbation, which are typically significantly less than suggested by the perturbation's operator norm. This stability has numerous consequences: we can (1) find timescales where the solution of Schrodinger's equation converges to the ground state of a block, (2) lower bound the convergence to the global ground state by demonstrating convergence to some other known quantum state, (3) guarantee faster convergence than the standard adiabatic theorem when the ground state of the perturbed Hamiltonian (H) is close to that of the unperturbed H, and (4) bound tunneling effects in terms of the global spectral gap when H is ``stoquastic'' (a Z-matrix). Our results apply to quantum annealing protocols with faster convergence than usually guaranteed by a standard adiabatic theorem. Our upper and lower bounds demonstrate that at timescales short of the adiabatic limit, subspace dynamics can dominate over global dynamics. Thus, we see that convergence to particular target states can be understood as the result of otherwise local dynamics.

Streaming quantum state purification - Andrew M. Childs; Honghao Fu; Debbie Leung; Zhi Li; Maris Ozols; Vedang Vyas (2023)
Quantum state purification is the task of recovering a nearly pure copy of an unknown pure quantum state using multiple noisy copies of the state. This basic task has applications to quantum communication over noisy channels and quantum computation with imperfect devices, but has only been studied previously for the case of qubits. We derive an efficient purification procedure based on the swap test for qudits of any dimension, starting with any initial error parameter. Treating the initial error parameter and the dimension as constants, we show that our procedure has sample complexity asymptotically optimal in the final error parameter. Our protocol has a simple recursive structure that can be applied when the states are provided one at a time in a streaming fashion, requiring only a small quantum memory to implement.

Strongly incoherent gravity - Daniel Carney; Jacob M. Taylor (2023)
While most fundamental interactions in nature are known to be mediated by quantized fields, the possibility has been raised that gravity may behave differently. Making this concept precise enough to test requires consistent models. Here we construct an explicit example of a theory where a non-entangling version of an arbitrary two-body potential V(r) arises from local measurements and feedback forces. While a variety of such theories exist, our construction causes particularly strong decoherence compared to more subtle approaches. Regardless, expectation values of observables obey the usual classical dynamics, while the interaction generates no entanglement. Applied to the Newtonian potential, this produces a non-relativistic model of gravity with fundamental loss of unitarity. The model contains a pair of free parameters, a substantial range of which is not excluded by observations to date. As an alternative to testing entanglement properties, we show that the entire remaining parameter space can be tested by looking for loss of quantum coherence in small systems like atom interferometers coupled to oscillating source masses.

Subsystem CSS codes, a tighter stabilizer-to-CSS mapping, and Goursat's Lemma - Michael Liaofan Liu; Nathanan Tantivasadakarn; Victor V. Albert (2023)
The CSS code construction is a powerful framework used to express features of a quantum code in terms of a pair of underlying classical codes. Its subsystem extension allows for similar expressions, but the general case has not been fully explored. Extending previous work of Aly et. al. [quant-ph/0610153], we determine subsystem CSS code parameters, express codewords, and develop a Steane-type decoder using only data from the two underlying classical codes. We show that any subsystem stabilizer code can be ``doubled'' to yield a subsystem CSS code with twice the number of physical, logical, and gauge qudits and up to twice the code distance. This mapping preserves locality and is tighter than the Majorana-based mapping of Bravyi, Leemhuis, and Terhal [New J. Phys. 12 083039 (2010)]. Using Goursat's Lemma, we show that every subsystem stabilizer code can be constructed from two nested subsystem CSS codes satisfying certain constraints, and we characterize subsystem stabilizer codes based on the nested codes' properties.

Symphony: Expressive Secure Multiparty Computation with Coordination - Ian Sweet; David Darais; David Heath; William Harris; Ryan Estes; Michael Hicks (The Art, Science, and Engineering of Programming, 2023)
Context: Secure Multiparty Computation (MPC) refers to a family of cryptographic techniques where mutually untrusting parties may compute functions of their private inputs while revealing only the function output. Inquiry: It can be hard to program MPCs correctly and efficiently using existing languages and frameworks, especially when they require coordinating disparate computational roles. How can we make this easier? Approach: We present Symphony, a new functional programming language for MPCs among two or more parties. Symphony starts from the single-instruction, multiple-data (SIMD) semantics of prior MPC languages, in which each party carries out symmetric responsibilities, and generalizes it using constructs that can coordinate many parties. Symphony introduces **first-class shares** and **first-class party sets** to provide unmatched language-level expressive power with high efficiency. Knowledge: Developing a core formal language called λ-Symphony, we prove that the intuitive, generalized SIMD view of a program coincides with its actual distributed semantics. Thus the programmer can reason about her programs by reading them from top to bottom, even though in reality the program runs in a coordinated fashion, distributed across many machines. We implemented a prototype interpreter for Symphony leveraging multiple cryptographic backends. With it we wrote a variety of MPC programs, finding that Symphony can express optimized protocols that other languages cannot, and that in general Symphony programs operate efficiently. [ full abstract at https://doi.org/10.22152/programming-journal.org/2023/7/14 ]

A theory of quantum differential equation solvers: limitations and fast-forwarding - Dong An; Jin-Peng Liu; Daochen Wang; Qi Zhao (2023)
We study the limitations and fast-forwarding of quantum algorithms for linear ordinary differential equation (ODE) systems with a particular focus on non-quantum dynamics, where the coefficient matrix in the ODE is not anti-Hermitian or the ODE is inhomogeneous. On the one hand, for generic homogeneous linear ODEs, by proving worst-case lower bounds, we show that quantum algorithms suffer from computational overheads due to two types of ``non-quantumness'': real part gap and non-normality of the coefficient matrix. We then show that homogeneous ODEs in the absence of both types of ``non-quantumness'' are equivalent to quantum dynamics, and reach the conclusion that quantum algorithms for quantum dynamics work best. We generalize our results to the inhomogeneous case and find that existing generic quantum ODE solvers cannot be substantially improved. To obtain these lower bounds, we propose a general framework for proving lower bounds on quantum algorithms that are amplifiers, meaning that they amplify the difference between a pair of input quantum states. On the other hand, we show how to fast-forward quantum algorithms for solving special classes of ODEs which leads to improved efficiency. More specifically, we obtain quadratic improvements in the evolution time T for inhomogeneous ODEs with a negative semi-definite coefficient matrix, and exponential improvements in both T and the spectral norm of the coefficient matrix for inhomogeneous ODEs with efficiently implementable eigensystems, including various spatially discretized linear evolutionary partial differential equations. We give fast-forwarding algorithms that are conceptually different from existing ones in the sense that they neither require time discretization nor solving high-dimensional linear systems.

Thermally driven quantum refrigerator autonomously resets superconducting qubit - Mohammed Ali Aamir; Paul Jamet Suria; José Antonio Marín Guzmán; Claudia Castillo-Moreno; Jeffrey M. Epstein; Nicole Yunger Halpern; Simone Gasparinetti (2023)
The first thermal machines steered the industrial revolution, but their quantum analogs have yet to prove useful. Here, we demonstrate a useful quantum absorption refrigerator formed from superconducting circuits. We use it to reset a transmon qubit to a temperature lower than that achievable with any one available bath. The process is driven by a thermal gradient and is autonomous -- requires no external control. The refrigerator exploits an engineered three-body interaction between the target qubit and two auxiliary qudits coupled to thermal environments. The environments consist of microwave waveguides populated with synthesized thermal photons. The target qubit, if initially fully excited, reaches a steady-state excited-level population of 5×10−4±5×10−4 (an effective temperature of 23.5~mK) in about 1.6~μs. Our results epitomize how quantum thermal machines can be leveraged for quantum information-processing tasks. They also initiate a path toward experimental studies of quantum thermodynamics with superconducting circuits coupled to propagating thermal microwave fields.

Thresholds in the Robustness of Error Mitigation in Noisy Quantum Dynamics - Pradeep Niroula; Sarang Gopalakrishnan; Michael Gullans (2023)
Extracting useful information from noisy near-term quantum simulations requires error mitigation strategies. A broad class of these strategies rely on precise characterization of the noise source. We study the robustness of such strategies when the noise is imperfectly characterized. We adapt an Imry-Ma argument to predict the existence of a threshold in the robustness of error mitigation for random spatially local circuits in spatial dimensions D≥2: noise characterization disorder below the threshold rate allows for error mitigation up to times that scale with the number of qubits. For one-dimensional circuits, by contrast, mitigation fails at an O(1) time for any imperfection in the characterization of disorder. As a result, error mitigation is only a practical method for sufficiently well-characterized noise. We discuss further implications for tests of quantum computational advantage, fault-tolerant probes of measurement-induced phase transitions, and quantum algorithms in near-term devices.

Time-energy uncertainty relation for noisy quantum metrology - Faist, Philippe; Woods, Mischa P.; Victor V. Albert; Renes, Joseph M.; Eisert, Jens; Preskill, John (PRX Quantum, 2023)
Detection of weak forces and precise measurement of time are two of the many applications of quantum metrology to science and technology. We consider a quantum system initialized in a pure state and whose evolution is goverened by a Hamiltonian H; a measurement can later estimate the time t for which the system has evolved. In this work, we introduce and study a fundamental trade-off which relates the amount by which noise reduces the accuracy of a quantum clock to the amount of information about the energy of the clock that leaks to the environment. Specifically, we consider an idealized scenario in which Alice prepares an initial pure state of the clock, allows the clock to evolve for a time t that is not precisely known, and then transmits the clock through a noisy channel to Bob. The environment (Eve) receives any information that is lost. We prove that Bob's loss of quantum Fisher information (QFI) about t is equal to Eve's gain of QFI about a complementary energy parameter. We also prove a more general trade-off that applies when Bob and Eve wish to estimate the values of parameters associated with two non-commuting observables. We derive the necessary and sufficient conditions for the accuracy of the clock to be unaffected by the noise. These are a subset of the Knill-Laflamme error-correction conditions; states satisfying these conditions are said to form a metrological code. We provide a scheme to construct metrological codes in the stabilizer formalism. We show that there are metrological codes that cannot be written as a quantum error-correcting code with similar distance in which the Hamiltonian acts as a logical operator, potentially offering new schemes for constructing states that do not lose any sensitivity upon application of a noisy channel. We discuss applications of our results to sensing using a many-body state subject to erasure or amplitude-damping noise.
Keywords: FOS: Physical sciences; Quantum Physics (quant-ph)

Transition of Anticoncentration in Gaussian Boson Sampling - Adam Ehrenberg; Joseph T. Iosue; Abhinav Deshpande; Dominik Hangleiter; Alexey V. Gorshkov (2023)
Gaussian Boson Sampling is a promising method for experimental demonstrations of quantum advantage because it is easier to implement than other comparable schemes. While most of the properties of Gaussian Boson Sampling are understood to the same degree as for these other schemes, we understand relatively little about the statistical properties of its output distribution. The most relevant statistical property, from the perspective of demonstrating quantum advantage, is the anticoncentration of the output distribution as measured by its second moment. The degree of anticoncentration features in arguments for the complexity-theoretic hardness of Gaussian Boson Sampling, and it is also important to know when using cross-entropy benchmarking to verify experimental performance. In this work, we develop a graph-theoretic framework for analyzing the moments of the Gaussian Boson Sampling distribution. Using this framework, we show that Gaussian Boson Sampling undergoes a transition in anticoncentration as a function of the number of modes that are initially squeezed compared to the number of photons measured at the end of the circuit. When the number of initially squeezed modes scales sufficiently slowly with the number of photons, there is a lack of anticoncentration. However, if the number of initially squeezed modes scales quickly enough, the output probabilities anticoncentrate weakly.

On the Two-sided Permutation Inversion Problem - Gorjan Alagic; Chen Bai; Alexander Poremba; Kaiyan Shi (2023)
In the permutation inversion problem, the task is to find the preimage of some challenge value, given oracle access to the permutation. This is a fundamental problem in query complexity, and appears in many contexts, particularly cryptography. In this work, we examine the setting in which the oracle allows for quantum queries to both the forward and the inverse direction of the permutation -- except that the challenge value cannot be submitted to the latter. Within that setting, we consider two options for the inversion algorithm: whether it can get quantum advice about the permutation, and whether it must produce the entire preimage (search) or only the first bit (decision). We prove several theorems connecting the hardness of the resulting variations of the inversion problem, and establish a number of lower bounds. Our results indicate that, perhaps surprisingly, the inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse, provided it cannot query the challenge itself.

An Uncertainty Principle for the Curvelet Transform, and the Infeasibility of Quantum Algorithms for Finding Short Lattice Vectors - Yi-Kai Liu (2023)
The curvelet transform is a special type of wavelet transform, which is useful for estimating the locations and orientations of waves propagating in Euclidean space. We prove an uncertainty principle that lower-bounds the variance of these estimates, for radial wave functions in n dimensions. As an application of this uncertainty principle, we show the infeasibility of one approach to constructing quantum algorithms for solving lattice problems, such as the approximate shortest vector problem (approximate-SVP), and bounded distance decoding (BDD). This gives insight into the computational intractability of approximate-SVP, which plays an important role in algorithms for integer programming, and in post-quantum cryptosystems. In this approach to solving lattice problems, one prepares quantum superpositions of Gaussian-like wave functions centered at lattice points. A key step in this procedure requires finding the center of each Gaussian-like wave function, using the quantum curvelet transform. We show that, for any choice of the Gaussian-like wave function, the error in this step will be above the threshold required to solve BDD and approximate-SVP.

An Uncertainty Principle for the Curvelet Transform, and the Infeasibility of Quantum Algorithms for Finding Short Lattice Vectors - Yi-Kai Liu (2023)
The curvelet transform is a special type of wavelet transform, which is useful for estimating the locations and orientations of waves propagating in Euclidean space. We prove an uncertainty principle that lower-bounds the variance of these estimates, for radial wave functions in n dimensions.  As an application of this uncertainty principle, we show the infeasibility of one approach to constructing quantum algorithms for solving lattice problems, such as the approximate shortest vector problem (approximate-SVP), and bounded distance decoding (BDD). This gives insight into the computational intractability of approximate-SVP, which plays an important role in algorithms for integer programming, and in post-quantum cryptosystems. In this approach to solving lattice problems, one prepares quantum superpositions of Gaussian-like wave functions centered at lattice points. A key step in this procedure requires finding the center of each Gaussian-like wave function, using the quantum curvelet transform. We show that, for any choice of the Gaussian-like wave function, the error in this step will be above the threshold required to solve BDD and approximate-SVP.

Verifiable measurement-based quantum random sampling with trapped ions - Martin Ringbauer; Marcel Hinsche; Thomas Feldker; Paul K. Faehrmann; Juani Bermejo-Vega; Claire Edmunds; Lukas Postler; Roman Stricker; Christian D. Marciniak; Michael Meth; Ivan Pogorelov; Rainer Blatt; et al. (2023)
Quantum computers are now on the brink of outperforming their classical counterparts. One way to demonstrate the advantage of quantum computation is through quantum random sampling performed on quantum computing devices. However, existing tools for verifying that a quantum device indeed performed the classically intractable sampling task are either impractical or not scalable to the quantum advantage regime. The verification problem thus remains an outstanding challenge. Here, we experimentally demonstrate efficiently verifiable quantum random sampling in the measurement-based model of quantum computation on a trapped-ion quantum processor. We create random cluster states, which are at the heart of measurement-based computing, up to a size of 4 x 4 qubits. Moreover, by exploiting the structure of these states, we are able to recycle qubits during the computation to sample from entangled cluster states that are larger than the qubit register. We then efficiently estimate the fidelity to verify the prepared states--in single instances and on average--and compare our results to cross-entropy benchmarking. Finally, we study the effect of experimental noise on the certificates. Our results and techniques provide a feasible path toward a verified demonstration of a quantum advantage.

A Watermark for Large Language Models - John Kirchenbauer; Jonas Geiping; Yuxin Wen; Jonathan Katz; Ian Miers; Tom Goldstein (2023)
Potential harms of large language models can be mitigated by watermarking model output, i.e., embedding signals into generated text that are invisible to humans but algorithmically detectable from a short span of tokens. We propose a watermarking framework for proprietary language models. The watermark can be embedded with negligible impact on text quality, and can be detected using an efficient open-source algorithm without access to the language model API or parameters. The watermark works by selecting a randomized set of "green" tokens before a word is generated, and then softly promoting use of green tokens during sampling. We propose a statistical test for detecting the watermark with interpretable p-values, and derive an information-theoretic framework for analyzing the sensitivity of the watermark. We test the watermark using a multi-billion parameter model from the Open Pretrained Transformer (OPT) family, and discuss robustness and security.

What happens to entropy production when conserved quantities fail to commute with each other - Twesh Upadhyaya; William F. Braasch, Jr.; Gabriel T. Landi; Nicole Yunger Halpern (2023)
We extend entropy production to a deeply quantum regime involving noncommuting conserved quantities. Consider a unitary transporting conserved quantities ("charges") between two systems initialized in thermal states. Three common formulae model the entropy produced. They respectively cast entropy as an extensive thermodynamic variable, as an information-theoretic uncertainty measure, and as a quantifier of irreversibility. Often, the charges are assumed to commute with each other (e.g., energy and particle number). Yet quantum charges can fail to commute. Noncommutation invites generalizations, which we posit and justify, of the three formulae. Charges' noncommutation, we find, breaks the formulae's equivalence. Furthermore, different formulae quantify different physical effects of charges' noncommutation on entropy production. For instance, entropy production can signal contextuality - true nonclassicality - by becoming nonreal. This work opens up stochastic thermodynamics to noncommuting - and so particularly quantum - charges.

Æ codes - Shubham P. Jain; Eric R. Hudson; Wesley C. Campbell; Victor V. Albert (2023)
Diatomic molecular codes [{arXiv:1911.00099}] are designed to encode quantum information in the orientation of a diatomic molecule, allowing error correction from small torques and changes in angular momentum. Here, we directly study noise native to atomic and molecular platforms -- spontaneous emission, stray electromagnetic fields, and Raman scattering -- and derive simple necessary and sufficient conditions for codes to protect against such noise. We identify existing and develop new absorption-emission (Æ) codes that are more practical than molecular codes, require lower average momentum, can directly protect against photonic processes up to arbitrary order, and are applicable to a broader set of atomic and molecular systems.

Accurate and Efficient Quantum Computations of Molecular Properties Using Daubechies Wavelet Molecular Orbitals: A Benchmark Study against Experimental Data - Cheng-Lin Hong; Ting Tsai; Jyh-Pin Chou; Peng-Jen Chen; Pei-Kai Tsai; Yu-Cheng Chen; En-Jui Kuo; David Srolovitz; Alice Hu; Yuan-Chung Cheng; Hsi-Sheng Goan (PRX Quantum, 2022)
Although quantum computation (QC) is regarded as a promising numerical method for computational quantum chemistry, current applications of quantum-chemistry calculations on quantum computers are limited to small molecules. This limitation can be ascribed to technical problems in building and manipulating more qubits and the associated complicated operations of quantum gates in a quantum circuit when the size of the molecular system becomes large. As a result, reducing the number of required qubits is necessary to make QC practical. Currently, the minimal STO-3G basis set is commonly used in benchmark studies because it requires the minimum number of spin orbitals. Nonetheless, the accuracy of using STO-3G is generally low and thus cannot provide useful predictions. We propose to adopt Daubechies wavelet functions as an accurate and efficient method for QCs of molecular electronic properties. We demonstrate that a minimal basis set constructed from Daubechies wavelet basis can yield accurate results through a better description of the molecular Hamiltonian, while keeping the number of spin orbitals minimal. With the improved Hamiltonian through Daubechies wavelets, we calculate vibrational frequencies for H2 and LiH using quantum-computing algorithm to show that the results are in excellent agreement with experimental data. As a result, we achieve quantum calculations in which accuracy is comparable with that of the full configuration interaction calculation using the cc-pVDZ basis set, whereas the computational cost is the same as that of a STO-3G calculation. Thus, our work provides a more efficient and accurate representation of the molecular Hamiltonian for efficient QCs of molecular systems, and for the first time demonstrates that predictions in agreement with experimental measurements are possible to be achieved with quantum resources available in near-term quantum computers.

Analogue Quantum Simulation: A New Instrument for Scientific Understanding - Dominik Hangleiter; Jacques Carolan; Karim P. Y. Thébault (Springer Nature, 2022)
Analyzes analogue quantum simulation philosophically. Provides a framework to support the goals of scientists. Useful to both working scientists and philosophers of science.

Approximating Output Probabilities of Shallow Quantum Circuits which are Geometrically-local in any Fixed Dimension - Dontha, Suchetan; Tan, Shi Jie Samuel; Smith, Stephen; Choi, Sangheon; Matthew Coudron (Leibniz International Proceedings in Informatics (LIPIcs), 2022)
We present a classical algorithm that, for any D-dimensional geometrically-local, quantum circuit C of polylogarithmic-depth, and any bit string x∈0,1n, can compute the quantity |<x|C|0⊗n>|2 to within any inverse-polynomial additive error in quasi-polynomial time, for any fixed dimension D. This is an extension of the result [CC21], which originally proved this result for D=3. To see why this is interesting, note that, while the D=1 case of this result follows from standard use of Matrix Product States, known for decades, the D=2 case required novel and interesting techniques introduced in [BGM19]. Extending to the case D=3 was even more laborious and required further new techniques introduced in [CC21]. Our work here shows that, while handling each new dimension has historically required a new insight, and fixed algorithmic primitive, based on known techniques for D≤3, we can now handle any fixed dimension D>3. Our algorithm uses the Divide-and-Conquer framework of [CC21] to approximate the desired quantity via several instantiations of the same problem type, each involving D-dimensional circuits on about half the number of qubits as the original. This division step is then applied recursively, until the width of the recursively decomposed circuits in the Dth dimension is so small that they can effectively be regarded as (D−1)-dimensional problems by absorbing the small width in the Dth dimension into the qudit structure at the cost of a moderate increase in runtime. The main technical challenge lies in ensuring that the more involved portions of the recursive circuit decomposition and error analysis from [CC21] still hold in higher dimensions, which requires small modifications to the analysis in some places.
Keywords: Computational Complexity (cs.CC); FOS: Computer and information sciences; FOS: Physical sciences; Quantum Physics (quant-ph)

Approximating the two-mode two-photon Rabi model - David H. Wu; Victor V. Albert (Physics Letters A, 2022)
The Rabi model describes the simplest nontrivial interaction between a few-level system and a bosonic mode, featuring in multiple seemingly unrelated systems of importance to quantum science and technology. While exact expressions for the energies of this model and its few-mode extensions have been obtained, they involve roots of transcendental functions and are thus cumbersome and unintuitive. Utilizing the symmetric generalized rotating wave approximation (S-GRWA), we develop a family of approximations to the energies of the two-mode two-photon Rabi model. The simplest elements of the family are analytically tractable, providing good approximations in regimes of interest such as ultra- and deep-strong coupling. Higher-order approximate energies can be used if more accuracy is required.

Arline Benchmarks: Automated Benchmarking Platform for Quantum Compilers - Kharkov, Y.; Ivanova, A.; Mikhantiev, E.; Kotelnikov, A. (2022)
Efficient compilation of quantum algorithms is vital in the era of Noisy Intermediate-Scale Quantum (NISQ) devices. While multiple open-source quantum compilation and circuit optimization frameworks are available, e.g. IBM Qiskit, CQC Tket, Google Cirq, Rigetti Quilc, PyZX, their relative performance is not always clear to a quantum programmer. The growth of complexity and diversity of quantum circuit compilation algorithms creates a demand for a dedicated tool for cross-benchmarking and profiling of inner workflow of the quantum compilation stack. We present an open-source software package, Arline Benchmarks, that is designed to perform automated benchmarking of quantum compilers with the focus on NISQ applications. The name "Arline" was given in honour of Arline Greenbaum Feynman, the first wife of Richard Feynman, the pioneer of quantum computing. We compared several quantum compilation frameworks based on a set of important metrics such as post-optimization gate counts, circuit depth, hardware-dependent circuit cost function, compiler run time etc. with a detailed analysis of metrics for each compilation stage. We performed a variety of compiler tests for random circuits and structured quantum algorithms (VQE, Trotter decomposition, Grover search, Option Pricing via Amplitude Estimation) for several popular quantum hardware architectures. Leveraging cross-platform functionality of Arline, we propose a concept of composite compilation pipeline that combines compiler-specific circuit optimization subroutines in a single compilation stack and finds an optimized sequence of compilation passes. By providing detailed insights into the compilation flow of quantum compilers, Arline Benchmarks offers a valuable toolkit for quantum computing researchers and software developers to gain additional insights into compilers' characteristics.
Keywords: FOS: Computer and information sciences; FOS: Physical sciences; Quantum Physics (quant-ph); Software Engineering (cs.SE)

Boson Sampling for Generalized Bosons - En-Jui Kuo; Yijia Xu; Dominik Hangleiter; Andrey Grankin; Mohammad Hafezi (2022)
We introduce the notion of "generalized bosons" whose exchange statistics resemble those of bosons, but the local bosonic commutator [ai,a†i]=1 is replaced by an arbitrary single-mode operator that is diagonal in the generalized Fock basis. Examples of generalized bosons include boson pairs and spins. We consider the analogue of the boson sampling task for these particles and observe that its output probabilities are still given by permanents, so that the results regarding hardness of sampling directly carry over. Finally, we propose implementations of generalized boson sampling in circuit-QED and ion-trap platforms.

Bosonic coding: introduction and use cases - Victor V. Albert (2022)
Bosonic or continuous-variable coding is a field concerned with robust quantum information processing and communication with electromagnetic signals or mechanical modes. I review bosonic quantum memories, characterizing them as either bosonic stabilizer or bosonic Fock-state codes. I then enumerate various applications of bosonic encodings, four of which circumvent no-go theorems due to the intrinsic infinite-dimensionality of bosonic systems.
Keywords: FOS: Computer and information sciences; FOS: Physical sciences; Information Theory (cs.IT); Quantum Physics (quant-ph)

Bosonic Qiskit - Stavenger, Timothy J; Crane, Eleanor; Smith, Kevin; Kang, Christopher T; Girvin, Steven M; Wiebe, Nathan (2022)
The practical benefits of hybrid quantum information processing hardware that contains continuous-variable objects (bosonic modes such as mechanical or electromagnetic oscillators) in addition to traditional (discrete-variable) qubits have recently been demonstrated by experiments with bosonic codes that reach the break-even point for quantum error correction and by efficient Gaussian boson sampling simulation of the Franck-Condon spectra of triatomic molecules that is well beyond the capabilities of current qubit-only hardware. The goal of this Co-design Center for Quantum Advantage (C2QA) project is to develop an instruction set architecture (ISA) for hybrid qubit/bosonic mode systems that contains an inventory of the fundamental operations and measurements that are possible in such hardware. The corresponding abstract machine model (AMM) would also contain a description of the appropriate error models associated with the gates, measurements and time evolution of the hardware. This information has been implemented as an extension of Qiskit. Qiskit is an opensource software development toolkit (SDK) for simulating the quantum state of a quantum circuit on a system with Python 3.7+ and for running the same circuits on prototype hardware within the IBM Quantum Lab. We introduce the Bosonic Qiskit software to enable the simulation of hybrid qubit/bosonic systems using the existing Qiskit software development kit. This implementation can be used for simulating new hybrid systems, verifying proposed physical systems, and modeling systems larger than can currently be constructed. We also cover tutorials and example use cases included within the software to study Jaynes- Cummings models, bosonic Hubbard models, plotting Wigner functions and animations, and calculating maximum likelihood estimations using Wigner functions.
Keywords: Emerging Technologies (cs.ET); FOS: Computer and information sciences; FOS: Physical sciences; Quantum Physics (quant-ph)

Bounding the Minimum Time of a Quantum Measurement - Shettell, Nathan; Centrone, Federico; García-Pintos, Luis Pedro (2022)
Measurements take a singular role in quantum theory. While they are often idealized as an instantaneous process, this is in conflict with all other physical processes in nature. In this Letter, we adopt a standpoint where the interaction with an environment is a crucial ingredient for the occurrence of a measurement. Within this framework, we derive lower bounds on the time needed for a measurement to occur. Our bound scales proportionally to the change in entropy of the measured system, and inversely proportional to the number of possible measurement outcomes and the interaction strength driving the measurement. We evaluate our bound in two examples where the environment is modelled by bosonic modes and the measurement apparatus is modelled by spins or bosons.
Keywords: FOS: Physical sciences; Quantum Physics (quant-ph)

Candidate for a self-correcting quantum memory in two dimensions - Simon Lieu; Yu-Jie Liu; Alexey V. Gorshkov (2022)
An interesting problem in the field of quantum error correction involves finding a physical system that hosts a "self-correcting quantum memory," defined as an encoded qubit coupled to an environment that naturally wants to correct errors. To date, a quantum memory stable against finite-temperature effects is only known in four spatial dimensions or higher. Here, we take a different approach to realize a stable quantum memory by relying on a driven-dissipative environment. We propose a new model which appears to self correct against both bit-flip and phase-flip errors in two dimensions: A square lattice composed of photonic "cat qubits" coupled via dissipative terms which tend to fix errors locally. Inspired by the presence of two distinct Z2-symmetry-broken phases, our scheme relies on Ising-like dissipators to protect against bit flips and on a driven-dissipative photonic environment to protect against phase flips.

Certifying Temporal Correlations - Harshank Shrotriya; Leong-Chuan Kwek, Kishor Bharti; Kishor Bharti (2022)
Self-testing has been established as a major approach for quantum device certification based on experimental statistics under minimal assumptions. However, despite more than 20 years of research effort most of the self-testing protocols are restricted to spatial scenarios (Bell scenarios), without any temporal generalisations known. Under the scenario of sequential measurements performed on a single quantum system, we build upon previous works which used semi-definite programming (SDP) based methods to bound sequential measurement inequalities. For such SDPs, we show that the optimiser matrix is unique and moreover this uniqueness is robust to small deviations from the quantum bound. Further, we consider a generalised scenario in presence of quantum channels and draw analogies in the structure of Bell and sequential inequalities using the pseudo-density matrix formalism. These analogies allow us to show a practical use of maximal violations of sequential inequalities in the form of certification of quantum channels up to isometries.

Chiral central charge from a single bulk wave function - Isaac H. Kim; Bowen Shi; Kohtaro Kato; Victor V. Albert (Phys. Rev. Lett., 2022)
A (2+1)-dimensional gapped quantum many-body system can have a topologically protected energy current at its edge. The magnitude of this current is determined entirely by the temperature and the chiral central charge, a quantity associated with the effective field theory of the edge. We derive a formula for the chiral central charge that, akin to the topological entanglement entropy, is completely determined by the many-body ground state wave function in the bulk. According to our formula, nonzero chiral central charge gives rise to a topological obstruction that prevents the ground state wave function from being real-valued in any local product basis.

Classification of (2+1)D invertible fermionic topological phases with symmetry - Maissam Barkeshli; Yu-An Chen; Po-Shen Hsin; Naren Manjunath (Phys. Rev. B, 2022)
We provide a classification of invertible topological phases of interacting fermions with symmetry in two spatial dimensions for general fermionic symmetry groups Gf and general values of the chiral central charge c−. Here Gf is a central extension of a bosonic symmetry group Gb by fermion parity, (−1)F, specified by a second cohomology class [ω2]∈H2(Gb,Z2). Our approach proceeds by gauging fermion parity and classifying the resulting Gb symmetry-enriched topological orders while keeping track of certain additional data and constraints. We perform this analysis through two perspectives, using G-crossed braided tensor categories and Spin(2c−)1 Chern-Simons theory coupled to a background G gauge field. These results give a way to characterize and classify invertible fermionic topological phases in terms of a concrete set of data and consistency equations, which is more physically transparent and computationally simpler than the more abstract methods using cobordism theory and spectral sequences. Our results also generalize and provide a different approach to the recent classification of fermionic symmetry-protected topological phases by Wang and Gu, which have chiral central charge c−=0. We show how the 10-fold way classification of topological insulators and superconductors fits into our scheme, along with general non-perturbative constraints due to certain choices of c− and Gf. Mathematically, our results also suggest an explicit general parameterization of deformation classes of (2+1)D invertible topological quantum field theories with Gf symmetry.

Closing the Locality and Detection Loopholes in Multiparticle Entanglement Self-Testing - Dian Wu; Qi Zhao; Can Wang; Liang Huang; Yang-Fan Jiang; Bing Bai; You Zhou; Xue-Mei Gu; Feng-Ming Liu; Ying-Qiu Mao; Qi-Chao Sun; Ming-Cheng Chen; et al. (Physical Review Letters, 2022)
First proposed by Mayers and Yao, self-testing provides a certification method to infer the underlying physics of quantum experiments in a black-box scenario. Numerous demonstrations have been reported to self-test various types of entangled states. However, all the multiparticle self-testing experiments reported so far suffer from both detection and locality loopholes. Here, we report the first experimental realization of multiparticle entanglement self-testing closing the locality loophole in a photonic system, and the detection loophole in a superconducting system, respectively. We certify three-party and four-party GHZ states with at least 0.84 (1) and 0.86 (3) fidelities in a device-independent way. These results can be viewed as a meaningful advance in multiparticle loophole-free self-testing, and also significant progress on the foundations of quantum entanglement certification.

Codimension-2 defects and higher symmetries in (3+1)D topological phases - Barkeshli, Maissam; Chen, Yu-An; Huang, Sheng-Jie; Kobayashi, Ryohei; Tantivasadakarn, Nathanan; Zhu, Guanyu (2022)
(3+1)D topological phases of matter can host a broad class of non-trivial topological defects of codimension-1, 2, and 3, of which the well-known point charges and flux loops are special cases. The complete algebraic structure of these defects defines a higher category, and can be viewed as an emergent higher symmetry. This plays a crucial role both in the classification of phases of matter and the possible fault-tolerant logical operations in topological quantum error correcting codes. In this paper, we study several examples of such higher codimension defects from distinct perspectives. We mainly study a class of invertible codimension-2 topological defects, which we refer to as twist strings. We provide a number of general constructions for twist strings, in terms of gauging lower dimensional invertible phases, layer constructions, and condensation defects. We study some special examples in the context of Z2 gauge theory with fermionic charges, in Z2×Z2 gauge theory with bosonic charges, and also in non-Abelian discrete gauge theories based on dihedral (Dn) and alternating (A6) groups. The intersection between twist strings and Abelian flux loops sources Abelian point charges, which defines an H4 cohomology class that characterizes part of an underlying 3-group symmetry of the topological order. The equations involving background gauge fields for the 3-group symmetry have been explicitly written down for various cases. We also study examples of twist strings interacting with non-Abelian flux loops (defining part of a non-invertible higher symmetry), examples of non-invertible codimension-2 defects, and examples of interplay of codimension-2 defects with codimension-1 defects. We also find an example of geometric, not fully topological, twist strings in (3+1)D A6 gauge theory.
Keywords: FOS: Mathematics; FOS: Physical sciences; High Energy Physics - Theory (hep-th); Mathematical Physics (math-ph); Quantum Algebra (math.QA); Quantum Physics (quant-ph); Strongly Correlated Electrons (cond-mat.str-el)

Combining machine learning with physics: A framework for tracking and sorting multiple dark solitons - Shangjie Guo; Sophia M. Koh; Amilson R. Fritsch; I. B. Spielman; Justyna P. Zwolak (Phys. Rev. Research, 2022)
In ultracold-atom experiments, data often comes in the form of images which suffer information loss inherent in the techniques used to prepare and measure the system. This is particularly problematic when the processes of interest are complicated, such as interactions among excitations in Bose-Einstein condensates (BECs). In this paper, we describe a framework combining machine learning (ML) models with physics-based traditional analyses to identify and track multiple solitonic excitations in images of BECs. We use an ML-based object detector to locate the solitonic excitations and develop a physics-informed classifier to sort solitonic excitations into physically motivated subcategories. Lastly, we introduce a quality metric quantifying the likelihood that a specific feature is a longitudinal soliton. Our trained implementation of this framework, SolDet, is publicly available as an open-source python package. SolDet is broadly applicable to feature identification in cold-atom images when trained on a suitable user-provided dataset.

Computational advantage of quantum random sampling - Dominik Hangleiter; Jens Eisert (2022)
Quantum random sampling is the leading proposal for demonstrating a computational advantage of quantum computers over classical computers. Recently, first large-scale implementations of quantum random sampling have arguably surpassed the boundary of what can be simulated on existing classical hardware. In this article, we comprehensively review the theoretical underpinning of quantum random sampling in terms of computational complexity and verifiability, as well as the practical aspects of its experimental implementation using superconducting and photonic devices and its classical simulation. We discuss in detail open questions in the field and provide perspectives for the road ahead, including potential applications of quantum random sampling.

Computational self-testing of multi-qubit states and measurements - Fu, Honghao; Daochen Wang; Zhao, Qi (2022)
Self-testing is a fundamental technique within quantum information theory that allows a classical verifier to force (untrusted) quantum devices to prepare certain states and perform certain measurements on them. The standard approach assumes at least two spatially separated devices. Recently, Metger and Vidick [Quantum, 2021] showed that a single EPR pair of a single quantum device can be self-tested under standard computational assumptions. In this work, we generalize their techniques to give the first protocol that self-tests N EPR pairs and measurements in the single-device setting under the same computational assumptions. We show that our protocol can be passed with probability negligibly close to 1 by an honest quantum device using poly(N) resources. Moreover, we show that any quantum device that fails our protocol with probability at most ϵ must be poly(N,ϵ)-close to being honest in the appropriate sense. In particular, a simplified version of our protocol is the first that can efficiently certify an arbitrary number of qubits of a cloud quantum computer, on which we cannot enforce spatial separation, using only classical communication.
Keywords: FOS: Physical sciences; Quantum Physics (quant-ph)

Constant-sized correlations are sufficient to robustly self-test maximally entangled states with unbounded dimension - Honghao Fu (Quantum, 2022)
We show that for any prime odd integer d, there exists a correlation of size Θ(r) that can robustly self-test a maximally entangled state of dimension 4d−4, where r is the smallest multiplicative generator of Z∗d. The construction of the correlation uses the embedding procedure proposed by Slofstra (Forum of Mathematics, Pi. Vol. 7, (2019)). Since there are infinitely many prime numbers whose smallest multiplicative generator is at most 5 (M. Murty The Mathematical Intelligencer 10.4 (1988)), our result implies that constant-sized correlations are sufficient for robust self-testing of maximally entangled states with unbounded local dimension.

Continuous Symmetry Breaking in a Trapped-Ion Spin Chain - Feng, Lei; Katz, Or; Haack, Casey; Maghrebi, Mohammad; Alexey V. Gorshkov; Gong, Zhexuan; Cetina, Marko; Monroe, Christopher (2022)
One-dimensional systems exhibiting a continuous symmetry can host quantum phases of matter with true long-range order only in the presence of sufficiently long-range interactions. In most physical systems, however, the interactions are short-ranged, hindering the emergence of such phases in one dimension. Here we use a one-dimensional trapped-ion quantum simulator to prepare states with long-range spin order that extends over the system size of up to 23 spins and is characteristic of the continuous symmetry-breaking phase of matter. Our preparation relies on simultaneous control over an array of tightly focused individual-addressing laser beams, generating long-range spin-spin interactions. We also observe a disordered phase with frustrated correlations. We further study the phases at different ranges of interaction and the out-of-equilibrium response to symmetry-breaking perturbations. This work opens an avenue to study new quantum phases and out-of-equilibrium dynamics in low-dimensional systems.
Keywords: FOS: Physical sciences; Quantum Gases (cond-mat.quant-gas); Quantum Physics (quant-ph); Statistical Mechanics (cond-mat.stat-mech); Strongly Correlated Electrons (cond-mat.str-el)

Continuous-Variable Shadow Tomography - Gandhari, Srilekha; Victor V. Albert; Gerrits, Thomas; Taylor, Jacob M.; Michael Gullans (2022)
Shadow tomography is a framework for constructing succinct descriptions of quantum states, called classical shadows, with powerful methods to bound the estimators used. We recast existing experimental protocols for continuous-variable tomography in the classical-shadow framework, obtaining rigorous bounds on the sample complexity for estimating density matrices from these protocols. We analyze the efficiency of homodyne, heterodyne, photon number resolving (PNR), and photon-parity protocols. To reach a desired precision on the classical shadow of an N-photon density matrix with a high probability, we show that homodyne detection requires an order O(N5) measurements in the worst case, whereas PNR and photon-parity detection require O(N4) measurements in the worst case (both up to logarithmic corrections). We benchmark these results against numerical simulation as well as experimental data from optical homodyne experiments. We find that numerical and experimental homodyne tomography significantly outperforms our bounds, exhibiting a more typical scaling of the number of measurements that is close to linear in N. We extend our single-mode results to an efficient construction of multimode shadows based on local measurements.
Keywords: FOS: Physical sciences; Quantum Physics (quant-ph)

A Convergence Theory for Over-parameterized Variational Quantum Eigensolvers - Xuchen You; Shouvanik Chakrabarti; Xiaodi Wu (2022)
The Variational Quantum Eigensolver (VQE) is a promising candidate for quantum applications on near-term Noisy Intermediate-Scale Quantum (NISQ) computers. Despite a lot of empirical studies and recent progress in theoretical understanding of VQE's optimization landscape, the convergence for optimizing VQE is far less understood. We provide the first rigorous analysis of the convergence of VQEs in the over-parameterization regime. By connecting the training dynamics with the Riemannian Gradient Flow on the unit-sphere, we establish a threshold on the sufficient number of parameters for efficient convergence, which depends polynomially on the system dimension and the spectral ratio, a property of the problem Hamiltonian, and could be resilient to gradient noise to some extent. We further illustrate that this overparameterization threshold could be vastly reduced for specific VQE instances by establishing an ansatz-dependent threshold paralleling our main result. We showcase that our ansatz-dependent threshold could serve as a proxy of the trainability of different VQE ansatzes without performing empirical experiments, which hence leads to a principled way of evaluating ansatz design. Finally, we conclude with a comprehensive empirical study that supports our theoretical findings

Convex optimization for non-equilibrium steady states on a hybrid quantum processor - Lau, Jonathan Wei Zhong; Lim, Kian Hwee; Bharti, Kishor; Kwek, Leong-Chuan; Vinjanampathy, Sai (2022)
Finding the transient and steady state properties of open quantum systems is a central problem in various fields of quantum technologies. Here, we present a quantum-assisted algorithm to determine the steady states of open system dynamics. By reformulating the problem of finding the fixed point of Lindblad dynamics as a feasibility semi-definite program, we bypass several well known issues with variational quantum approaches to solving for steady states. We demonstrate that our hybrid approach allows us to estimate the steady states of higher dimensional open quantum systems and discuss how our method can find multiple steady states for systems with symmetries.
Keywords: FOS: Physical sciences; Quantum Physics (quant-ph)

CoVault: A Secure Analytics Platform - De Viti, Roberta; Sheff, Isaac; Glaeser, Noemi; Dinis, Baltasar; Rodrigues, Rodrigo; Katz, Jonathan; Bhattacharjee, Bobby; Hithnawi, Anwar; Garg, Deepak; Druschel, Peter (2022)
In a secure analytics platform, data sources consent to the exclusive use of their data for a pre-defined set of analytics queries performed by a specific group of analysts, and for a limited period. If the platform is secure under a sufficiently strong threat model, it can provide the missing link to enabling powerful analytics of sensitive personal data, by alleviating data subjects' concerns about leakage and misuse of data. For instance, many types of powerful analytics that benefit public health, mobility, infrastructure, finance, or sustainable energy can be made differentially private, thus alleviating concerns about privacy. However, no platform currently exists that is sufficiently secure to alleviate concerns about data leakage and misuse; as a result, many types of analytics that would be in the interest of data subjects and the public are not done. CoVault uses a new multi-party implementation of functional encryption (FE) for secure analytics, which relies on a unique combination of secret sharing, multi-party secure computation (MPC), and different trusted execution environments (TEEs). CoVault is secure under a very strong threat model that tolerates compromise and side-channel attacks on any one of a small set of parties and their TEEs. Despite the cost of MPC, we show that CoVault scales to very large data sizes using map-reduce based query parallelization. For example, we show that CoVault can perform queries relevant to epidemic analytics at scale.
Keywords: and Cluster Computing (cs.DC); Cryptography and Security (cs.CR); Distributed; FOS: Computer and information sciences; Parallel

Dark Solitons in Bose-Einstein Condensates: A Dataset for Many-body Physics Research - Amilson R. Fritsch; Shangjie Guo; Sophia M. Koh; I. B. Spielman; Justyna P. Zwolak (2022)
We establish a dataset of over 1.6×104 experimental images of Bose-Einstein condensates containing solitonic excitations to enable machine learning (ML) for many-body physics research. About 33 % of this dataset has manually assigned and carefully curated labels. The remainder is automatically labeled using SolDet -- an implementation of a physics-informed ML data analysis framework -- consisting of a convolutional-neural-network-based classifier and object detector as well as a statistically motivated physics-informed classifier and a quality metric. This technical note constitutes the definitive reference of the dataset, providing an opportunity for the data science community to develop more sophisticated analysis tools, to further understand nonlinear many-body physics, and even advance cold atom experiments.

Deconfinement and Error Thresholds in Holography - Bao, Ning; Cao, Charles; Zhu, Guanyu (2022)
We study the error threshold properties of holographic quantum error-correcting codes. We demonstrate that holographic CFTs admit an algebraic threshold, which is related to the confinement-deconfinement phase transition. We then apply geometric intuition from holography and the Hawking-Page phase transition to motivate the CFT result, and comment on potential extensions to other confining theories.
Keywords: FOS: Physical sciences; High Energy Physics - Theory (hep-th); Nuclear Theory (nucl-th); Quantum Physics (quant-ph); Strongly Correlated Electrons (cond-mat.str-el)

Demonstration of three- and four-body interactions between trapped-ion spins - Katz, Or; Feng, Lei; Risinger, Andrew; Monroe, Christopher; Cetina, Marko (2022)
Quantum processors use the native interactions between effective spins to simulate Hamiltonians or execute quantum gates. In most processors, the native interactions are pairwise, limiting the efficiency of controlling entanglement between many qubits. Here we experimentally demonstrate a new class of native interactions between trapped-ion qubits, extending conventional pairwise interactions to higher order. We realize three- and four-body spin interactions as examples, showing that high-order spin polynomials may serve as a new toolbox for quantum information applications.
Keywords: Atomic Physics (physics.atom-ph); FOS: Physical sciences; Quantum Physics (quant-ph)

Differentiable Quantum Programming with Unbounded Loops - Fang, Wang; Ying, Mingsheng; Wu, Xiaodi (2022)
The emergence of variational quantum applications has led to the development of automatic differentiation techniques in quantum computing. Recently, Zhu et al. (PLDI 2020) have formulated differentiable quantum programming with bounded loops, providing a framework for scalable gradient calculation by quantum means for training quantum variational applications. However, promising parameterized quantum applications, e.g., quantum walk and unitary implementation, cannot be trained in the existing framework due to the natural involvement of unbounded loops. To fill in the gap, we provide the first differentiable quantum programming framework with unbounded loops, including a newly designed differentiation rule, code transformation, and their correctness proof. Technically, we introduce a randomized estimator for derivatives to deal with the infinite sum in the differentiation of unbounded loops, whose applicability in classical and probabilistic programming is also discussed. We implement our framework with Python and Q#, and demonstrate a reasonable sample efficiency. Through extensive case studies, we showcase an exciting application of our framework in automatically identifying close-to-optimal parameters for several parameterized quantum applications.
Keywords: FOS: Computer and information sciences; FOS: Physical sciences; Machine Learning (cs.LG); Programming Languages (cs.PL); Quantum Physics (quant-ph)

Disordered Lieb-Robinson bounds in one dimension - Baldwin, Christopher L.; Ehrenberg, Adam; Guo, Andrew Y.; Alexey V. Gorshkov (2022)
By tightening the conventional Lieb-Robinson bounds to better handle systems which lack translation invariance, we determine the extent to which "weak links" suppress operator growth in disordered one-dimensional spin chains. In particular, we prove that ballistic growth is impossible when the distribution of coupling strengths μ(J) has a sufficiently heavy tail at small J, and identify the correct dynamical exponent to use instead. Furthermore, through a detailed analysis of the special case in which the couplings are genuinely random and independent, we find that the standard formulation of Lieb-Robinson bounds is insufficient to capture the complexity of the dynamics -- we must distinguish between bounds which hold for all sites of the chain and bounds which hold for a subsequence of sites, and we show by explicit example that these two can have dramatically different behaviors. All the same, our result for the dynamical exponent is tight, in that we prove by counterexample that there cannot exist any Lieb-Robinson bound with a smaller exponent. We close by discussing the implications of our results, both major and minor, for numerous applications ranging from quench dynamics to the structure of ground states.
Keywords: Disordered Systems and Neural Networks (cond-mat.dis-nn); FOS: Physical sciences; Mathematical Physics (math-ph); Quantum Physics (quant-ph)

Efficient and practical quantum compiler towards multi-qubit systems with deep reinforcement learning - Chen, Qiuhao; Du, Yuxuan; Zhao, Qi; Jiao, Yuling; Lu, Xiliang; Wu, Xingyao (2022)
Efficient quantum compiling tactics greatly enhance the capability of quantum computers to execute complicated quantum algorithms. Due to its fundamental importance, a plethora of quantum compilers has been designed in past years. However, there are several caveats to current protocols, which are low optimality, high inference time, limited scalability, and lack of universality. To compensate for these defects, here we devise an efficient and practical quantum compiler assisted by advanced deep reinforcement learning (RL) techniques, i.e., data generation, deep Q-learning, and AQ* search. In this way, our protocol is compatible with various quantum machines and can be used to compile multi-qubit operators. We systematically evaluate the performance of our proposal in compiling quantum operators with both inverse-closed and inverse-free universal basis sets. In the task of single-qubit operator compiling, our proposal outperforms other RL-based quantum compilers in the measure of compiling sequence length and inference time. Meanwhile, the output solution is near-optimal, guaranteed by the Solovay-Kitaev theorem. Notably, for the inverse-free universal basis set, the achieved sequence length complexity is comparable with the inverse-based setting and dramatically advances previous methods. These empirical results contribute to improving the inverse-free Solovay-Kitaev theorem. In addition, for the first time, we demonstrate how to leverage RL-based quantum compilers to accomplish two-qubit operator compiling. The achieved results open an avenue for integrating RL with quantum compiling to unify efficiency and practicality and thus facilitate the exploration of quantum advantages.
Keywords: FOS: Computer and information sciences; FOS: Physical sciences; Machine Learning (cs.LG); Quantum Physics (quant-ph)

Efficient Product Formulas for Commutators and Applications to Quantum Simulation - Yu-An Chen; Andrew M. Childs; Mohammad Hafezi; Zhang Jiang; Hwanmun Kim; Yijia Xu (Physical Review Research, 2022)
We construct product formulas for exponentials of commutators and explore their applications. First, we directly construct a third-order product formula with six exponentials by solving polynomial equations obtained using the operator differential method. We then derive higher-order product formulas recursively from the third-order formula. We improve over previous recursive constructions, reducing the number of gates required to achieve the same accuracy. In addition, we demonstrate that the constituent linear terms in the commutator can be included at no extra cost. As an application, we show how to use the product formulas in a digital protocol for counterdiabatic driving, which increases the fidelity for quantum state preparation. We also discuss applications to quantum simulation of one-dimensional fermion chains with nearest- and next-nearest-neighbor hopping terms, and two-dimensional fractional quantum Hall phases.

Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation - Dong An; Di Fang; Stephen Jordan; Jin-Peng Liu; Guang Hao Low; Jiasu Wang (2022)
Nonlinear differential equations exhibit rich phenomena in many fields but are notoriously challenging to solve. Recently, Liu et al. [1] demonstrated the first efficient quantum algorithm for dissipative quadratic differential equations under the condition R<1, where R measures the ratio of nonlinearity to dissipation using the ℓ2 norm. Here we develop an efficient quantum algorithm based on [1] for reaction-diffusion equations, a class of nonlinear partial differential equations (PDEs). To achieve this, we improve upon the Carleman linearization approach introduced in [1] to obtain a faster convergence rate under the condition RD<1, where RD measures the ratio of nonlinearity to dissipation using the ℓ∞ norm. Since RD is independent of the number of spatial grid points n while R increases with n, the criterion RD<1 is significantly milder than R<1 for high-dimensional systems and can stay convergent under grid refinement for approximating PDEs. As applications of our quantum algorithm we consider the Fisher-KPP and Allen-Cahn equations, which have interpretations in classical physics. In particular, we show how to estimate the mean square kinetic energy in the solution by postprocessing the quantum state that encodes it to extract derivative information.

Error-correcting codes for fermionic quantum simulation - Chen, Yu-An; Alexey V. Gorshkov; Xu, Yijia (2022)
We provide ways to simulate fermions by qubits on 2d lattices using Z2 gauge theories (stabilizer codes). By studying the symplectic automorphisms of the Pauli module over the Laurent polynomial ring, we develop a systematic way to increase the code distances of stabilizer codes. We identify a family of stabilizer codes that can be used to simulate fermions with code distances of d=2,3,4,5,6,7 such that any ⌊d−12⌋-qubit error can be corrected. In particular, we demonstrate three stabilizer codes with code distances of d=3, d=4, and d=5, respectively, with all stabilizers and logical operators shown explicitly. The syndromes for all Pauli errors are provided. Finally, we introduce a syndrome-matching method to compute code distances numerically.
Keywords: FOS: Mathematics; FOS: Physical sciences; Mathematical Physics (math-ph); Quantum Algebra (math.QA); Quantum Physics (quant-ph); Strongly Correlated Electrons (cond-mat.str-el)

Estimating gate complexities for the site-by-site preparation of fermionic vacua - Troy Sewell; Aniruddha Bapat; Stephen Jordan (2022)
An important aspect of quantum simulation is the preparation of physically interesting states on a quantum computer, and this task can often be costly or challenging to implement. A digital, ``site-by-site'' scheme of state preparation was introduced in arXiv:1911.03505 as a way to prepare the vacuum state of certain fermionic field theory Hamiltonians with a mass gap. More generally, this algorithm may be used to prepare ground states of Hamiltonians by adding one site at a time as long as successive intermediate ground states share a non-zero overlap and the Hamiltonian has a non-vanishing spectral gap at finite lattice size. In this paper, we study the ground state overlap as a function of the number of sites for a range of quadratic fermionic Hamiltonians. Using analytical formulas known for free fermions, we are able to explore the large-N behavior and draw conclusions about the state overlap. For all models studied, we find that the overlap remains large (e.g. >0.1) up to large lattice sizes (N=64,72) except near quantum phase transitions or in the presence of gapless edge modes. For one-dimensional systems, we further find that two N/2-site ground states also share a large overlap with the N-site ground state everywhere except a region near the phase boundary. Based on these numerical results, we additionally propose a recursive alternative to the site-by-site state preparation algorithm.

Euler-obstructed Cooper pairing: Nodal superconductivity and hinge Majorana zero modes - Jiabin Yu; Yu-An Chen; Sankar Das Sarma (Physical Review B, 2022)
Since the proposal of monopole Cooper pairing in [Phys. Rev. Lett. 120, 067003 (2018)], considerable research efforts have been dedicated to the study of Cooper pairing order parameters constrained (or obstructed) by the nontrivial normal-state band topology at Fermi surfaces in 3D systems. In the current work, we generalize the topologically obstructed pairings between Chern states (like the monopole Cooper pairing) by proposing Euler obstructed Cooper pairing in 3D systems. The Euler obstructed Cooper pairing widely exists between two Fermi surfaces with nontrivial band topology characterized by nonzero Euler numbers; such Fermi surfaces can exist in 3D PT-protected spinless-Dirac/nodal-line semimetals with negligible spin-orbit coupling, where PT is the space-time inversion symmetry. An Euler obstructed pairing channel must have pairing nodes on the pairing-relevant Fermi surfaces, and the total winding number of the pairing nodes is determined by the sum or difference of the Euler numbers on the Fermi surfaces. In particular, we find that when the normal state is time-reversal invariant and the pairing is weak, a sufficiently-dominant Euler obstructed pairing channel with zero total momentum leads to nodal superconductivity. If the Fermi surface splitting is small, the resultant nodal superconductor hosts hinge Majorana zero modes. The possible dominance of the Euler obstructed pairing channel near the superconducting transition and the robustness of the hinge Majorana zero modes against disorder are explicitly demonstrated using effective or tight-binding models. Our work presents the first class of higher-order nodal superconductivity originating from the topologically obstructed Cooper pairing.

Experimental Implementation of an Efficient Test of Quantumness - Lewis, Laura; Zhu, Daiwei; Gheorghiu, Alexandru; Noel, Crystal; Katz, Or; Harraz, Bahaa; Wang, Qingfeng; Risinger, Andrew; Feng, Lei; Biswas, Debopriyo; Egan, Laird; Vidick, Thomas; et al. (2022)
A test of quantumness is a protocol where a classical user issues challenges to a quantum device to determine if it exhibits non-classical behavior, under certain cryptographic assumptions. Recent attempts to implement such tests on current quantum computers rely on either interactive challenges with efficient verification, or non-interactive challenges with inefficient (exponential time) verification. In this paper, we execute an efficient non-interactive test of quantumness on an ion-trap quantum computer. Our results significantly exceed the bound for a classical device's success.
Keywords: FOS: Physical sciences; Other Condensed Matter (cond-mat.other); Quantum Physics (quant-ph)

Experimental observation of thermalisation with noncommuting charges - Kranzl, Florian; Lasek, Aleksander; Joshi, Manoj K.; Kalev, Amir; Blatt, Rainer; Roos, Christian F.; Nicole Yunger Halpern (2022)
Quantum simulators have recently enabled experimental observations of quantum many-body systems' internal thermalisation. Often, the global energy and particle number are conserved, and the system is prepared with a well-defined particle number - in a microcanonical subspace. However, quantum evolution can also conserve quantities, or charges, that fail to commute with each other. Noncommuting charges have recently emerged as a subfield at the intersection of quantum thermodynamics and quantum information. Until now, this subfield has remained theoretical. We initiate the experimental testing of its predictions, with a trapped-ion simulator. We prepare 6-15 spins in an approximate microcanonical subspace, a generalisation of the microcanonical subspace for accommodating noncommuting charges, which cannot necessarily have well-defined nontrivial values simultaneously. We simulate a Heisenberg evolution using laser-induced entangling interactions and collective spin rotations. The noncommuting charges are the three spin components. We find that small subsystems equilibrate to near a recently predicted non-Abelian thermal state. This work bridges quantum many-body simulators to the quantum thermodynamics of noncommuting charges, whose predictions can now be tested.
Keywords: FOS: Physical sciences; Quantum Physics (quant-ph); Statistical Mechanics (cond-mat.stat-mech)

Experimentally Measuring Rolling and Sliding in Three-Dimensional Dense Granular Packings - Zackery A. Benson; Anton Peshkov; Nicole Yunger Halpern; Derek C. Richardson; Wolfgang Losert (Phys. Rev. Lett., 2022)
We experimentally measure a three-dimensional (3D) granular system’s reversibility under cyclic compression. We image the grains using a refractive-index-matched fluid, then analyze the images using the artificial intelligence of variational autoencoders. These techniques allow us to track all the grains’ translations and 3D rotations with accuracy sufficient to infer sliding and rolling displacements. Our observations reveal unique roles played by 3D rotational motions in granular flows. We find that rotations and contact-point motion dominate the dynamics in the bulk, far from the perturbation’s source. Furthermore, we determine that 3D rotations are irreversible under cyclic compression. Consequently, contact-point sliding, which is dissipative, accumulates throughout the cycle. Using numerical simulations whose accuracy our experiment supports, we discover that much of the dissipation occurs in the bulk, where grains rotate more than they translate. Our observations suggest that the analysis of 3D rotations is needed for understanding granular materials’ unique and powerful ability to absorb and dissipate energy.

Extracting Wilson loop operators and fractional statistics from a single bulk ground state - Cian, Ze-Pei; Hafezi, Mohammad; Barkeshli, Maissam (2022)
An essential aspect of topological phases of matter is the existence of Wilson loop operators that keep the ground state subspace invariant. Here we present and implement an unbiased numerical optimization scheme to systematically find the Wilson loop operators given a single ground state wave function of a gapped Hamiltonian on a disk. We then show how these Wilson loop operators can be cut and glued through further optimization to give operators that can create, move, and annihilate anyon excitations. We subsequently use these operators to determine the braiding statistics and topological twists of the anyons, yielding a way to fully extract topological order from a single wave function. We apply our method to the ground state of the perturbed toric code and doubled semion models with a magnetic field that is up to a half of the critical value. From a contemporary perspective, this can be thought of as a machine learning approach to discover emergent 1-form symmetries of a ground state wave function. From an application perspective, our approach can be relevant to find Wilson loop operators in current quantum simulators.
Keywords: FOS: Physical sciences; Quantum Physics (quant-ph); Strongly Correlated Electrons (cond-mat.str-el)

FIPS Compliant Quantum Secure Communication using Quantum Permutation Pad - He, Alex; Lou, Dafu; She, Eric; Guo, Shangjie; Watson, Hareesh; Weng, Sibyl; Perepechaenko, Maria; Kuang, Rand (2022)
Quantum computing has entered fast development track since Shor's algorithm was proposed in 1994. Multi-cloud services of quantum computing farms are currently available. One of which, IBM quantum computing, presented a road map showing their Kookaburra system with over 4158 qubits will be available in 2025. For the standardization of Post-Quantum Cryptography or PQC, the National Institute of Standards and Technology or NIST recently announced the first candidates for standardization with one algorithm for key encapsulation mechanism (KEM), Kyber, and three algorithms for digital signatures. NIST has also issued a new call for quantum-safe digital signature algorithms due June 1, 2023. This timeline shows that FIPS-certified quantum-safe TLS protocol would take a predictably long time. However, "steal now, crack later" tactic requires protecting data against future quantum threat actors today. NIST recommended the use of a hybrid mode of TLS 1.3 with its extensions to support PQC. The hybrid mode works for certain cases but FIPS certification for the hybridized cryptomodule might still be required. This paper proposes to take a nested mode to enable TLS 1.3 protocol with quantum-safe data, which can be made available today and is FIPS compliant. We discussed the performance impacts of the handshaking phase of the nested TLS 1.3 with PQC and the symmetric encryption phase. The major impact on performance using the nested mode is in the data symmetric encryption with AES. To overcome this performance reduction, we suggest using quantum encryption with a quantum permutation pad for the data encryption with a minor performance reduction of less than 10 percent.
Keywords: Cryptography and Security (cs.CR); FOS: Computer and information sciences; FOS: Physical sciences; Quantum Physics (quant-ph)

Group coset monogamy games and an application to device-independent continuous-variable QKD - Culf, Eric; Vidick, Thomas; Victor V. Albert (2022)
We develop an extension of a recently introduced subspace coset state monogamy-of-entanglement game [Coladangelo, Liu, Liu, and Zhandry; Crypto'21] to general group coset states, which are uniform superpositions over elements of a subgroup to which has been applied a group-theoretic generalization of the quantum one-time pad. We give a general bound on the winning probability of a monogamy game constructed from subgroup coset states that applies to a wide range of finite and infinite groups. To study the infinite-group case, we use and further develop a measure-theoretic formalism that allows us to express continuous-variable measurements as operator-valued generalizations of probability measures. We apply the monogamy game bound to various physically relevant groups, yielding realizations of the game in continuous-variable modes as well as in rotational states of a polyatomic molecule. We obtain explicit strong bounds in the case of specific group-space and subgroup combinations. As an application, we provide the first proof of one sided-device independent security of a squeezed-state continuous-variable quantum key distribution protocol against general coherent attacks.
Keywords: Cryptography and Security (cs.CR); FOS: Computer and information sciences; FOS: Physical sciences; Quantum Physics (quant-ph)

Hamiltonian simulation with random inputs - Qi Zhao; You Zhou; Alexander F. Shaw; Tongyang Li; Andrew M. Childs (Phys. Rev. Lett. 129, 270502, 2022)
The algorithmic error of digital quantum simulations is usually explored in terms of the spectral norm distance between the actual and ideal evolution operators. In practice, this worst-case error analysis may be unnecessarily pessimistic. To address this, we develop a theory of average-case performance of Hamiltonian simulation with random initial states. We relate the average-case error to the Frobenius norm of the multiplicative error and give upper bounds for the product formula (PF) and truncated Taylor series methods. As applications, we estimate average-case error for digital Hamiltonian simulation of general lattice Hamiltonians and k-local Hamiltonians. In particular, for the nearest-neighbor Heisenberg chain with n spins, the error is quadratically reduced from O(n) in the worst case to O(n−−√) on average for both the PF method and the Taylor series method. Numerical evidence suggests that this theory accurately characterizes the average error for concrete models. We also apply our results to error analysis in the simulation of quantum scrambling.

Higher-group symmetry in finite gauge theory and stabilizer codes - Barkeshli, Maissam; Chen, Yu-An; Hsin, Po-Shen; Kobayashi, Ryohei (2022)
A large class of gapped phases of matter can be described by topological finite group gauge theories. In this paper, we derive the d-group global symmetry and its 't Hooft anomaly for topological finite group gauge theories in (d+1) space-time dimensions, including non-Abelian gauge groups and Dijkgraaf-Witten twists. We focus on the 1-form symmetry generated by invertible (Abelian) magnetic defects and the higher-form symmetries generated by invertible topological defects decorated with lower dimensional gauged symmetry-protected topological (SPT) phases. We show that due to a generalization of the Witten effect and charge-flux attachment, the 1-form symmetry generated by the magnetic defects mixes with other symmetries into a higher group. We describe such higher-group symmetry in various lattice model examples. We discuss several applications, including the classification of fermionic SPT phases in (3+1)D for general fermionic symmetry groups, where we also derive a simpler formula for the [O5]∈H5(BG,U(1)) obstruction than has appeared in previous work. We also show how the d-group symmetry is related to fault-tolerant non-Pauli logical gates and a refined Clifford hierarchy in stabilizer codes. We construct new logical gates in stabilizer codes using the d-group symmetry, such as the control-Z gate in (3+1)D Z2 toric code.
Keywords: FOS: Mathematics; FOS: Physical sciences; High Energy Physics - Theory (hep-th); Quantum Algebra (math.QA); Quantum Physics (quant-ph); Strongly Correlated Electrons (cond-mat.str-el)

How to build Hamiltonians that transport noncommuting charges in quantum thermodynamics - Nicole Yunger Halpern; Shayan Majidy (npj Quantum Inf, 2022)
Noncommuting conserved quantities have recently launched a subfield of quantum thermodynamics. In conventional thermodynamics, a system of interest and a bath exchange quantities -- energy, particles, electric charge, etc. -- that are globally conserved and are represented by Hermitian operators. These operators were implicitly assumed to commute with each other, until a few years ago. Freeing the operators to fail to commute has enabled many theoretical discoveries -- about reference frames, entropy production, resource-theory models, etc. Little work has bridged these results from abstract theory to experimental reality. This paper provides a methodology for building this bridge systematically: We present an algorithm for constructing Hamiltonians that conserve noncommuting quantities globally while transporting the quantities locally. The Hamiltonians can couple arbitrarily many subsystems together and can be integrable or nonintegrable. Special cases of our construction have appeared in quantum chromodynamics (QCD). Our Hamiltonians may be realized physically with superconducting qudits, with ultracold atoms, with trapped ions, and in QCD.

Implementing a Fast Unbounded Quantum Fanout Gate Using Power-Law Interactions - Andrew Y. Guo; Abhinav Deshpande; Su-Kuan Chu; Zachary Eldredge; Przemyslaw Bienias; Dhruv Devulapalli; Yuan Su; Andrew M. Childs; Alexey V. Gorshkov (Phys. Rev. Research, 2022)
The standard circuit model for quantum computation presumes the ability to directly perform gates between arbitrary pairs of qubits, which is unlikely to be practical for large-scale experiments. Power-law interactions with strength decaying as 1/rα in the distance r provide an experimentally realizable resource for information processing, whilst still retaining long-range connectivity. We leverage the power of these interactions to implement a fast quantum fanout gate with an arbitrary number of targets. Our implementation allows the quantum Fourier transform (QFT) and Shor's algorithm to be performed on a D-dimensional lattice in time logarithmic in the number of qubits for interactions with α≤D. As a corollary, we show that power-law systems with α≤D are difficult to simulate classically even for short times, under a standard assumption that factoring is classically intractable. Complementarily, we develop a new technique to give a general lower bound, linear in the size of the system, on the time required to implement the QFT and the fanout gate in systems that are constrained by a linear light cone. This allows us to prove an asymptotically tighter lower bound for long-range systems than is possible with previously available techniques.

Importance of the Spectral gap in Estimating Ground-State Energies - Abhinav Deshpande; Alexey V. Gorshkov; Bill Fefferman (PRX Quantum, 2022)
The field of quantum Hamiltonian complexity lies at the intersection of quantum many-body physics and computational complexity theory, with deep implications to both fields. The main object of study is the LocalHamiltonian problem, which is concerned with estimating the ground-state energy of a local Hamiltonian and is complete for the class QMA, a quantum generalization of the class NP. A major challenge in the field is to understand the complexity of the LocalHamiltonian problem in more physically natural parameter regimes. One crucial parameter in understanding the ground space of any Hamiltonian in many-body physics is the spectral gap, which is the difference between the smallest two eigenvalues. Despite its importance in quantum many-body physics, the role played by the spectral gap in the complexity of the LocalHamiltonian is less well-understood. In this work, we make progress on this question by considering the precise regime, in which one estimates the ground-state energy to within inverse exponential precision. Computing ground-state energies precisely is a task that is important for quantum chemistry and quantum many-body physics. In the setting of inverse-exponential precision, there is a surprising result that the complexity of LocalHamiltonian is magnified from QMA to PSPACE, the class of problems solvable in polynomial space. We clarify the reason behind this boost in complexity. Specifically, we show that the full complexity of the high precision case only comes about when the spectral gap is exponentially small. As a consequence of the proof techniques developed to show our results, we uncover important implications for the representability and circuit complexity of ground states of local Hamiltonians, the theory of uniqueness of quantum witnesses, and techniques for the amplification of quantum witnesses in the presence of postselection.

Infinite-randomness criticality in monitored quantum dynamics with static disorder - Aidan Zabalo; Justin H. Wilson; Michael Gullans; Romain Vasseur; Sarang Gopalakrishnan; David A. Huse; J. H. Pixley (2022)
We consider a model of monitored quantum dynamics with quenched spatial randomness: specifically, random quantum circuits with spatially varying measurement rates. These circuits undergo a measurement-induced phase transition (MIPT) in their entanglement structure, but the nature of the critical point differs drastically from the case with constant measurement rate. In particular, at the critical measurement rate, we find that the entanglement of a subsystem of size ℓ scales as S∼ℓ√; moreover, the dynamical critical exponent z=∞. The MIPT is flanked by Griffiths phases with continuously varying dynamical exponents. We argue for this infinite-randomness scenario on general grounds and present numerical evidence that it captures some features of the universal critical properties of MIPT using large-scale simulations of Clifford circuits. These findings demonstrate that the relevance and irrelevance of perturbations to the MIPT can naturally be interpreted using a powerful heuristic known as the Harris criterion.

Isolation and manipulation of a single-donor detector in a silicon quantum dot - Lasek, A. A.; Barnes, C. H. W.; Ferrus, T. (Phys. Rev. B, 2022)
We demonstrate the isolation and electrostatic control of a single phosphorus donor in a silicon quantum dot by making use of source-drain bias during cooldown and biases applied to capacitively coupled gates. Characterization of the device at low temperatures and in magnetic fields shows single donors can be electrostatically isolated near one of the quantum dot's tunnel barriers with either single or double occupancy. This model is well supported by capacitance-based simulations. The ability to use the D 0 state of such isolated donors as a charge detector is demonstrated by observing the charge stability diagram of a nearby and capacitively coupled semiconnected double quantum dot.

Kramers' degeneracy for open systems in thermal equilibrium - Simon Lieu; Max McGinley; Oles Shtanko; Nigel R. Cooper; Alexey V. Gorshkov (Phys. Rev. B, 2022)

Lattice-Based Quantum Advantage from Rotated Measurements - Yusuf Alnawakhtha; Mantri, Atul; Carl Miller; Wang, Daochen (2022)
Trapdoor claw-free functions (TCFs) are immensely valuable in cryptographic interactions between a classical client and a quantum server. Typically, a protocol has the quantum server prepare a superposition of two-bit strings of a claw and then measure it using Pauli-X or Z measurements. In this paper, we demonstrate a new technique that uses the entire range of qubit measurements from the XY-plane. We show the advantage of this approach in two applications. First, building on (Brakerski et al. 2018, Kalai et al. 2022), we show an optimized two-round proof of quantumness whose security can be expressed directly in terms of the hardness of the LWE (learning with errors) problem. Second, we construct a one-round protocol for blind remote preparation of an arbitrary state on the XY-plane up to a Pauli-Z correction.
Keywords: Cryptography and Security (cs.CR); Emerging Technologies (cs.ET); FOS: Computer and information sciences; FOS: Physical sciences; Quantum Physics (quant-ph)

Linear growth of quantum circuit complexity - Jonas Haferkamp; Philippe Faist; Naga B. T. Kothakonda; Jens Eisert; Nicole Yunger Halpern (Nat. Phys., 2022)
The complexity of quantum states has become a key quantity of interest across various subfields of physics, from quantum computing to the theory of black holes. The evolution of generic quantum systems can be modelled by considering a collection of qubits subjected to sequences of random unitary gates. Here we investigate how the complexity of these random quantum circuits increases by considering how to construct a unitary operation from Haar-random two-qubit quantum gates. Implementing the unitary operation exactly requires a minimal number of gates—this is the operation’s exact circuit complexity. We prove a conjecture that this complexity grows linearly, before saturating when the number of applied gates reaches a threshold that grows exponentially with the number of qubits. Our proof overcomes difficulties in establishing lower bounds for the exact circuit complexity by combining differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits.

Machine-assisted discovery of integrable symplectic mappings - Zolkin, Timofey; Kharkov, Yaroslav; Nagaitsev, Sergei (2022)
We present a new automated method for finding integrable symplectic maps of the plane. These dynamical systems possess a hidden symmetry associated with an existence of conserved quantities, i.e. integrals of motion. The core idea of the algorithm is based on the knowledge that the evolution of an integrable system in the phase space is restricted to a lower-dimensional submanifold. Limiting ourselves to polygon invariants of motion, we analyze the shape of individual trajectories thus successfully distinguishing integrable motion from chaotic cases. For example, our method rediscovers some of the famous McMillan-Suris integrable mappings and discrete Painlevé equations. In total, over 100 new integrable families are presented and analyzed; some of them are isolated in the space of parameters, and some of them are families with one parameter (or the ratio of parameters) being continuous or discrete. At the end of the paper, we suggest how newly discovered maps are related to a general 2D symplectic map via an introduction of discrete perturbation theory and propose a method on how to construct smooth near-integrable dynamical systems based on mappings with polygon invariants.
Keywords: Accelerator Physics (physics.acc-ph); Adaptation and Self-Organizing Systems (nlin.AO); Exactly Solvable and Integrable Systems (nlin.SI); FOS: Physical sciences

Mana and thermalization: Probing the feasibility of near-Clifford Hamiltonian simulation - Troy J. Sewell; Christopher David White (Physical Review B, 2022)
Quantum hydrodynamics is the emergent classical dynamics governing transport of conserved quantities in generic strongly-interacting quantum systems. Recent matrix product operator methods have made simulations of quantum hydrodynamics in 1+1d tractable, but they do not naturally generalize to 2+1d or higher, and they offer limited guidance as to the difficulty of simulations on quantum computers. Near-Clifford simulation algorithms are not limited to one dimension, and future error-corrected quantum computers will likely be bottlenecked by non-Clifford operations. We therefore investigate the non-Clifford resource requirements for simulation of quantum hydrodynamics using ``mana'', a resource theory of non-Clifford operations. For infinite-temperature starting states we find that the mana of subsystems quickly approaches zero, while for starting states with energy above some threshold the mana approaches a nonzero value. Surprisingly, in each case the finite-time mana is governed by the subsystem entropy, not the thermal state mana; we argue that this is because mana is a sensitive diagnostic of finite-time deviations from canonical typicality.

Many-Body Quantum Teleportation via Operator Spreading in the Traversable Wormhole Protocol - Thomas Schuster; Bryce Kobrin; Ping Gao; Iris Cong; Emil T. Khabiboulline; Norbert M. Linke; Mikhail D. Lukin; Christopher Monroe; Beni Yoshida; Norman Y. Yao (Physical Review X, 2022)
By leveraging shared entanglement between a pair of qubits, one can teleport a quantum state from one particle to another. Recent advances have uncovered an intrinsically many-body generalization of quantum teleportation, with an elegant and surprising connection to gravity. In particular, the teleportation of quantum information relies on many-body dynamics, which originate from strongly-interacting systems that are holographically dual to gravity; from the gravitational perspective, such quantum teleportation can be understood as the transmission of information through a traversable wormhole. Here, we propose and analyze a new mechanism for many-body quantum teleportation -- dubbed peaked-size teleportation. Intriguingly, peaked-size teleportation utilizes precisely the same type of quantum circuit as traversable wormhole teleportation, yet has a completely distinct microscopic origin: it relies upon the spreading of local operators under generic thermalizing dynamics and not gravitational physics. We demonstrate the ubiquity of peaked-size teleportation, both analytically and numerically, across a diverse landscape of physical systems, including random unitary circuits, the Sachdev-Ye-Kitaev model (at high temperatures), one-dimensional spin chains and a bulk theory of gravity with stringy corrections. Our results pave the way towards using many-body quantum teleportation as a powerful experimental tool for: (i) characterizing the size distributions of operators in strongly-correlated systems and (ii) distinguishing between generic and intrinsically gravitational scrambling dynamics. To this end, we provide a detailed experimental blueprint for realizing many-body quantum teleportation in both trapped ions and Rydberg atom arrays; effects of decoherence and experimental imperfections are analyzed.

The Mathematics of Quantum Coin-Flipping - Carl Miller (Notices of the American Mathematical Society, 2022)