We describe a class of spin chains with new physical and computational properties. On the physical side, the spin chains give examples of symmetry-protected topological phases that are defined by non-onsite symmetries, i.e. symmetries that are not a tensor product of single-site operators. These phases can be detected by string-order parameters, but notably do not exhibit entanglement spectrum degeneracy. On the computational side, the spin chains represent a new class of states that can be used to deterministically teleport information across long distances, with the novel property that the necessary classical side processing is a non-linear function of the measurement outcomes. We also give examples of states that can serve as universal resources for measurement-based quantum computation, providing the first examples of such resources without entanglement spectrum degeneracy. The key tool in our analysis is a new kind of tensor network representation which we call split-index matrix product states (SIMPS). We develop the basic formalism of SIMPS, compare them to matrix product states, show how they are better equipped to describe certain kinds of non-onsite symmetries including anomalous symmetries, and discuss how they are also well-suited to describing quantum teleportation and constrained spin chains.
We introduce the spanning tree matching (STM) decoder for surface codes, which guarantees the error correction capability up to the code's designed distance by first employing an instance of the minimum spanning tree on a subset of ancilla qubits within the lattice. Then, a perfect matching graph is simply obtained, by selecting the edges more likely to be faulty. A comparative analysis reveals that the STM decoder, at the cost of a slight performance degradation, provides a substantial advantage in decoding time compared to the minimum weight perfect matching (MWPM) decoder. Finally, we propose an even more simplified and faster algorithm, the Rapid-Fire (RFire) decoder, designed for scenarios where decoding speed is a critical requirement.
This paper introduces a method for calculating the quantum relative entropy of channels, an essential quantity in quantum channel discrimination and resource theories of quantum channels. By building on recent developments in the optimization of relative entropy for quantum states [Kossmann and Schwonnek, arXiv:2404.17016], we introduce a discretized linearization of the integral representation for the relative entropy for states, enabling us to handle maximization tasks of the relative entropy of a channel over input states. Our approach here extends previous work on minimizing relative entropy to the more complicated domain of maximization. It also provides efficiently computable upper and lower bounds that sandwich the true value with any desired precision, leading to a practical method for computing the relative entropy of channels.
Cryptographic group actions are a leading contender for post-quantum cryptography, and have also been used in the development of quantum cryptographic protocols. In this work, we explore quantum state group actions, which consist of a group acting on a set of quantum states. We show the following results: 1. In certain settings, statistical (even query bounded) security is impossible, analogously to post-quantum classical group actions. 2. We construct quantum state group actions and prove that many computational problems that have been proposed by cryptographers hold it. Depending on the construction, our proofs are either unconditional, rely on LWE, or rely on the quantum random oracle model. While our analysis does not directly apply to classical group actions, we argue it gives at least a sanity check that there are no obvious flaws in the post-quantum assumptions made by cryptographers. 3. Our quantum state group action allows for unifying two existing quantum money schemes: those based on group actions, and those based on non-collapsing hashes. We also explain how they can unify classical and quantum key distribution.
We establish a holographic duality between d-dimensional mixed-state symmetry-protected topological phases (mSPTs) and (d+1)-dimensional subsystem symmetry-protected topological states (SSPTs). Specifically, we show that the reduced density matrix of the boundary layer of a (d+1)-dimensional SSPT with subsystem symmetry $\mathcal{S}$ and global symmetry $\mathcal{G}$ corresponds to a d-dimensional mSPT with strong $\mathcal{S}$ and weak $\mathcal{G}$ symmetries. Conversely, we demonstrate that the wavefunction of an SSPT can be constructed by replicating the density matrix of the corresponding lower-dimensional mSPT. This mapping links the density matrix in lower dimensions to the entanglement properties of higher-dimensional wavefunctions, providing an approach for analyzing nonlinear quantities and quantum information metrics in mixed-state systems. Our duality offers a new perspective for studying intrinsic mSPTs that are unique to open quantum systems, without pure state analogs. We show that strange correlators and twisted Renyi-N correlators can diagnose these nontrivial phases and explore their connection to strange correlators in pure-state SSPTs.
We study the effect of shared non-signaling correlations for the problem of simulating a channel using noiseless communication in the one-shot setting. For classical channels, we show how to round any non-signaling-assisted simulation strategy--which corresponds to the natural linear programming meta-converse for channel simulation--to a strategy that only uses shared randomness. For quantum channels, we round any non-signaling-assisted simulation strategy to a strategy that only uses shared entanglement. Our main result is for classical and classical-quantum channels, for which we employ ideas from approximation algorithms to give a guarantee on the ratio of success probabilities of at least $(1-\mathrm{e}^{-1})$. We further show this ratio to be optimal for the purely classical case. It can be improved to $(1-t^{-1})$ using $O(\ln \ln(t))$ additional bits of communication.
Tensor networks are a compressed format for multi-dimensional data. One-dimensional tensor networks -- often referred to as tensor trains (TT) or matrix product states (MPS) -- are increasingly being used as a numerical ansatz for continuum functions by "quantizing" the inputs into discrete binary digits. Here we demonstrate the power of more general tree tensor networks for this purpose. We provide direct constructions of a number of elementary functions as generic tree tensor networks and interpolative constructions for more complicated functions via a generalization of the tensor cross interpolation algorithm. For a range of multi-dimensional functions we show how more structured tree tensor networks offer a significantly more efficient ansatz than the commonly used tensor train. We demonstrate an application of our methods to solving multi-dimensional, non-linear Fredholm equations, providing a rigorous bound on the rank of the solution which, in turn, guarantees exponentially scaling accuracy with the size of the tree tensor network for certain problems.
Quantum signal processing (QSP) and quantum singular value transformation (QSVT) have provided a unified framework for understanding many quantum algorithms, including factorization, matrix inversion, and Hamiltonian simulation. As a multivariable version of QSP, multivariable quantum signal processing (M-QSP) is proposed. M-QSP interleaves signal operators corresponding to each variable with signal processing operators, which provides an efficient means to perform multivariable polynomial transformations. However, the necessary and sufficient condition for what types of polynomials can be constructed by M-QSP is unknown. In this paper, we propose a classical algorithm to determine whether a given pair of multivariable Laurent polynomials can be implemented by M-QSP, which returns True or False. As one of the most important properties of this algorithm, it returning True is the necessary and sufficient condition. The proposed classical algorithm runs in polynomial time in the number of variables and signal operators. Our algorithm also provides a constructive method to select the necessary parameters for implementing M-QSP. These findings offer valuable insights for identifying practical applications of M-QSP.
We propose a new scheme for near-term photonic quantum device that allows to increase the expressive power of the quantum models beyond what linear optics can do. This scheme relies upon state injection, a measurement-based technique that can produce states that are more controllable, and solve learning tasks that are not believed to be tackled classically. We explain how circuits made of linear optical architectures separated by state injections are keen for experimental implementation. In addition, we give theoretical results on the evolution of the purity of the resulting states, and we discuss how it impacts the distinguishability of the circuit outputs. Finally, we study a computational subroutines of learning algorithms named probability estimation, and we show the state injection scheme we propose may offer a potential quantum advantage in a regime that can be more easily achieved that state-of-the-art adaptive techniques. Our analysis offers new possibilities for near-term advantage that require to tackle fewer experimental difficulties.
The effect of decoherence on topological order (TO) has been most deeply understood for the toric code, the paragon of Abelian TOs. We show that certain non-Abelian TOs can be analyzed and understood to a similar degree, despite being significantly richer. We consider both wavefunction deformations and quantum channels acting on $D_4$ TO, which has recently been realized on a quantum processor. By identifying the corresponding local statistical mechanical spin or rotor model with $D_4$ symmetry, we find a remarkable stability against proliferating non-Abelian anyons. This is shown by leveraging a reformulation in terms of the tractable O$(2)$ loop model in the pure state case, and $n$ coupled O$(2)$ loop models for Rényi-$n$ quantities in the decoherence case -- corresponding to worldlines of the proliferating anyon with quantum dimension $2$. In particular, we find that the purity ($n=2$) remains deep in the $D_4$ TO for any decoherence strength, while the $n \to \infty$ limit becomes critical upon maximally decohering a particular anyon type, similar to our wavefunction deformation result. The information-theoretic threshold ($n\to 1$) appears to be controlled by a disordered version of these stat-mech models, akin to the toric code case although significantly more robust. We furthermore use Monte Carlo simulations to explore the phase diagrams when multiple anyon types proliferate at the same time, leading to a continued stability of the $D_4$ TO in addition to critical phases with emergent $U(1)$ symmetry. Instead of loop models, these are now described by net models corresponding to different anyon types coupled together according to fusion rules.This opens up the exploration of statistical mechanical models for decohered non-Abelian TO, which can inform optimal decoders, and which in an ungauged formulation examples of non-Abelian strong-to-weak symmetry breaking.
This work considers a teleportation task for Alice and Bob in a scenario where Bob cannot perform corrections. In particular, we analyse the task of \textitmulticopy state teleportation, where Alice has $k$ identical copies of an arbitrary unknown $d$-dimensional qudit state $\vert\psi\rangle$ to teleport a single copy of $\vert\psi\rangle$ to Bob using a maximally entangled two-qudit state shared between Alice and Bob without Bob's correction. Alice may perform a joint measurement on her half of the entangled state and the $k$ copies of $\vert\psi\rangle$. We prove that the maximal probability of success for teleporting the exact state $\vert\psi\rangle$ to Bob is $p(d,k)=\frac{k}{d(k-1+d)}$ and present an explicit protocol to attain this performance. Then, by utilising $k$ copies of an arbitrary target state $\vert\psi\rangle$, we show how the multicopy state teleportation protocol can be employed to enhance the success probability of storage and retrieval of quantum programs, which aims to universally retrieve the action of an arbitrary quantum channel that is stored in a state. Our proofs make use of group representation theory methods, which may find applications beyond the problems addressed in this work.
We present the first implementation of text-level quantum natural language processing, a field where quantum computing and AI have found a fruitful intersection. We focus on the QDisCoCirc model, which is underpinned by a compositional approach to rendering AI interpretable: the behaviour of the whole can be understood in terms of the behaviour of parts, and the way they are put together. Interpretability is crucial for understanding the unwanted behaviours of AI. By leveraging the compositional structure in the model's architecture, we introduce a novel setup which enables 'compositional generalisation': we classically train components which are then composed to generate larger test instances, the evaluation of which asymptotically requires a quantum computer. Another key advantage of our approach is that it bypasses the trainability challenges arising in quantum machine learning. The main task that we consider is the model-native task of question-answering, and we handcraft toy scale data that serves as a proving ground. We demonstrate an experiment on Quantinuum's H1-1 trapped-ion quantum processor, which constitutes the first proof of concept implementation of scalable compositional QNLP. We also provide resource estimates for classically simulating the model. The compositional structure allows us to inspect and interpret the word embeddings the model learns for each word, as well as the way in which they interact. This improves our understanding of how it tackles the question-answering task. As an initial comparison with classical baselines, we considered transformer and LSTM models, as well as GPT-4, none of which succeeded at compositional generalisation.
Scaling fault-tolerant quantum computing is essential to realize the potential of quantum computation. Surface code has been the best choice over the last decade because of its effective error suppression capability. However, it suffers from a low encoding rate, requiring a vast number of physical qubits for large-scale quantum computation. In contrast, hypergraph product codes present a promising alternative, as both their encoding rate and distance scale with block size. Despite this, their non-local stabilizers necessitate long-range connectivity for stabilizer measurements, posing significant experimental challenges. Recent advancements have shown how to deterministically perform high-fidelity cavity enabled non-local many-body gates, enabling the creation of non-local cat states. We integrate the non-local resource into the DiVincenzo-Aliferis method for fault-tolerant stabilizer measurement. We apply the scheme to long-range quantum hypergraph product codes, performing circuit-level noise simulations including the the cavity error model, achieving a promising threshold. Additionally, we propose a tri-layer architectural layout for scheduling stabilizer measurements, enhancing circuit parallelizability.
We study real-time operator evolution using sparse Pauli dynamics, a recently developed method for simulating expectation values of quantum circuits. On the examples of energy and charge diffusion in 1D spin chains and sudden quench dynamics in the 2D transverse-field Ising model, it is shown that this approach can compete with state-of-the-art tensor network methods. We further demonstrate the flexibility of the approach by studying quench dynamics in the 3D transverse-field Ising model which is highly challenging for tensor network methods. For the simulation of expectation value dynamics starting in a computational basis state, we introduce an extension of sparse Pauli dynamics that truncates the growing sum of Pauli operators by discarding terms with a large number of X and Y matrices. This is validated by our 2D and 3D simulations. Finally, we argue that sparse Pauli dynamics is not only capable of converging challenging observables to high accuracy, but can also serve as a reliable approximate approach even when given only limited computational resources.
Understanding the interface between quantum and relativistic theories is crucial for fundamental and practical advances, especially given that key physical concepts such as causality take different forms in these theories. Bell's no-go theorem reveals limits on classical processes, arising from relativistic causality principles. Considering whether similar fundamental limits exist on quantum processes, we derive no-go theorems for quantum experiments realisable in classical background spacetimes. We account for general processes allowed by quantum theory, including those with indefinite causal order (ICO), which have also been the subject of recent experiments. Our first theorem implies that realisations of ICO processes that do not violate relativistic causality must involve the non-localization of systems in spacetime. The second theorem shows that for any such realisation of an ICO process, there exists a more fine-grained description in terms of a definite and acyclic causal order process. This enables a general reconciliation of quantum and relativistic notions of causality and, in particular, applies to experimental realisations of the quantum switch, a prominent ICO process. By showing what is impossible to achieve in classical spacetimes, these no-go results also offer insights into how causality and information processing may differ in future quantum experiments in relativistic regimes beyond classical spacetimes.
Triorthogonal matrices were introduced in Quantum Information Theory in connection with distillation of magic states (Bravyi and Haah (2012)). We give an algorithm to construct binary triorthogonal matrices from binary self-dual codes. Further, we generalize to this setting the classical coding techniques of shortening and extending. We also give some simple propagation rules.
The detection of quantum and classical phase transitions in the absence of an order parameter is possible using the Fisher information metric (FIM), also known as fidelity susceptibility. Here, we propose and investigate an unsupervised machine learning (ML) task: estimating the FIM given limited samples from a multivariate probability distribution of measurements made throughout the phase diagram. We utilize an unsupervised ML method called ClassiFIM (developed in a companion paper) to solve this task and demonstrate its empirical effectiveness in detecting both quantum and classical phase transitions using a variety of spin and fermionic models, for which we generate several publicly available datasets with accompanying ground-truth FIM. We find that ClassiFIM reliably detects both topological (e.g., XXZ chain) and dynamical (e.g., metal-insulator transition in Hubbard model) quantum phase transitions. We perform a detailed quantitative comparison with prior unsupervised ML methods for detecting quantum phase transitions. We demonstrate that ClassiFIM is competitive with these prior methods in terms of appropriate accuracy metrics while requiring significantly less resource-intensive training data compared to the original formulation of the prior methods. In particular, ClassiFIM only requires classical (single-basis) measurements. As part of our methodology development, we prove several theorems connecting the classical and quantum fidelity susceptibilities through equalities or bounds. We also significantly expand the existence conditions of the fidelity susceptibility, e.g., by relaxing standard differentiability conditions. These results may be of independent interest to the mathematical physics community.
Given a tripartite quantum state on $A,B,C$ and the erasure channel on $C$, the rotated Petz map is a recovery channel that acts on $B$ to recover the erased quantum information. The infidelity of the best recovery is upper-bounded by the conditional mutual information (CMI). In this work, we study the infidelity of the rotated Petz map on several physically-relevant long-range entangled quantum states. Specifically, we study three classes of quantum phases: (i) steady states of measurement-induced phase transitions, (ii) critical ground state under local measurements, and (iii) chiral states under local measurements. We find that the averaged infidelity of the Petz map recovery sharply distinguishes the three classes: (i) and (ii) are distinguished by the scaling of the infidelity with CMI and (iii) is characterized by an asymmetry of the infidelity with the rotation parameter. We also study Petz map recovery for topological order and find an operational interpretation of the topological entanglement entropy. Our result indicates that recovery fidelity of the Petz map is a useful diagnostic of quantum phases of matter.
We study how to extend Sanov theorem to the quantum setting. Although a quantum version of the Sanov theorem was proposed in Bjelakovic et al (Commun. Math. Phys., 260, p.659 (2005)), the classical case of their statement is not the same as Sanov theorem because Sanov theorem discusses the behavior of the empirical distribution when the empirical distribution is different from the true distribution, but they studied a problem related to quantum hypothesis testing, whose classical version can be shown by classical Sanov theorem. We propose another quantum version of Sanov theorem by considering the quantum analog of the empirical distribution.
Kostka, Littlewood-Richardson, Plethysm and Kronecker coefficients are the multiplicities of irreducible representations in decomposition of representations of the symmetric group that play an important role in representation theory and algebraic combinatorics. We give quantum algorithms for computing these coefficients whenever the ratio of dimensions of the representations is polynomial and study the computational complexity of this problem. We show that there is an efficient classical algorithm for computing the Kostka numbers under this restriction and conjecture the existence of an analogous algorithm for the Littlewood-Richardson coefficients. We argue why such classical algorithm does not straightforwardly work for the Plethysm and Kronecker coefficients and conjecture that our quantum algorithms lead to superpolynomial speedups for this problem. We support this conjecture by showing how our quantum algorithm avoids some hardness obstructions in computation of these coefficients. We give another quantum algorithm that estimates the multiplicities using induction and has a different cost-to-input dependence.
Measurements can detect errors in a decohered quantum memory allowing active error correction to increase the memory time. Previous understanding of this mechanism has focused on evaluating the performance of error correction algorithms based on measurement results. In this work, we instead intrinsically characterize the information dynamics in a quantum memory under repeated measurements, using coherent information and relative entropy. We consider the dynamics of a $d$-dimensional stabilizer code subject to Pauli errors and noisy stabilizer measurements and develop a $(d+1)$-dimensional statistical mechanics model for the information-theoretic diagnostics. Our model is dual to the model previously obtained for the optimal decoding algorithm, and the potential decoding transition in the quantum memory again manifests as a thermal phase transition in the statistical mechanics model. We explicitly derive the model and study the phase transition in information encoding in three examples: surface codes, repetition codes, and the XZZX code.
We provide a complete solution to the problem of infinite quantum signal processing for the class of Szegő functions, which are functions that satisfy a logarithmic integrability condition and include almost any function that allows for a quantum signal processing representation. We do so by introducing a new algorithm called the Riemann-Hilbert-Weiss algorithm, which can compute any individual phase factor independent of all other phase factors. Our algorithm is also the first provably stable numerical algorithm for computing phase factors of any arbitrary Szegő function. The proof of stability involves solving a Riemann-Hilbert factorization problem in nonlinear Fourier analysis using elements of spectral theory.
We study the entanglement entropy of a random tensor network (RTN) using tools from free probability theory. Random tensor networks are simple toy models that help the understanding of the entanglement behavior of a boundary region in the ADS/CFT context. One can think of random tensor networks are specific probabilistic models for tensors having some particular geometry dictated by a graph (or network) structure. We first introduce our model of RTN, obtained by contracting maximally entangled states (corresponding to the edges of the graph) on the tensor product of Gaussian tensors (corresponding to the vertices of the graph). We study the entanglement spectrum of the resulting random spectrum along a given bipartition of the local Hilbert spaces. We provide the limiting eigenvalue distribution of the reduced density operator of the RTN state, in the limit of large local dimension. The limit value is described via a maximum flow optimization problem in a new graph corresponding to the geometry of the RTN and the given bipartition. In the case of series-parallel graphs, we provide an explicit formula for the limiting eigenvalue distribution using classical and free multiplicative convolutions. We discuss the physical implications of our results, allowing us to go beyond the semiclassical regime without any cut assumption, specifically in terms of finite corrections to the average entanglement entropy of the RTN.
There are possible physical theories that give greater violations of Bell's inequalities than the corresponding Tsirelson bound, termed post-quantum non-locality. Such theories do not violate special relativity, but could give an advantage in certain information processing tasks. There is another way in which entangled quantum states exhibit non-classical phenomena, with one notable example being Einstein-Podolsky-Rosen (EPR) steering; a violation of a bipartite Bell inequality implies EPR steering, but the converse is not necessarily true. The study of post-quantum EPR steering is more intricate, but it has been shown that it does not always imply post-quantum non-locality in a conventional Bell test. In this work we show how to distribute resources in a larger network that individually do not demonstrate post-quantum non-locality but violate a Tsirelson bound for the network. That is, we show how to activate post-quantum steering so that it can now be witnessed as post-quantum correlations in a Bell scenario. One element of our work that may be of independent interest is we show how to self-test a bipartite quantum assemblage in a network, even assuming post-quantum resources.
In the current framework of Geometric Quantum Machine Learning, the canonical method for constructing a variational ansatz that respects the symmetry of some group action is by forcing the circuit to be equivariant, i.e., to commute with the action of the group. This can, however, be an overzealous constraint that greatly limits the expressivity of the circuit, especially in the case of continuous symmetries. We propose an alternative paradigm for the symmetry-informed construction of variational quantum circuits, based on homogeneous spaces, relaxing the overly stringent requirement of equivariance. We achieve this by introducing horizontal quantum gates, which only transform the state with respect to the directions orthogonal to those of the symmetry. We show that horizontal quantum gates are much more expressive than equivariant gates, and thus can solve problems that equivariant circuits cannot. For instance, a circuit comprised of horizontal gates can find the ground state of an $\mathrm{SU}(2)$-symmetric model where the ground state spin sector is unknown--a task where equivariant circuits fall short. Moreover, for a particular subclass of horizontal gates based on symmetric spaces, we can obtain efficient circuit decompositions for our gates through the KAK theorem. Finally, we highlight a particular class of horizontal quantum gates that behave similarly to general $\mathrm{SU}(4)$ gates, while achieving a quadratic reduction in the number of parameters for a generic problem.
Bell nonlocality is the resource that enables device-independent quantum information processing tasks. It is revealed through the violation of so-called Bell inequalities, indicating that the observed correlations cannot be reproduced by any local hidden variable model. While well explored in few-body settings, the question of which Bell inequalities are best suited for a given task remains quite open in the many-body scenario. One natural approach is to assign Bell inequalities to physical Hamiltonians, mapping their interaction graph to two-body, nearest-neighbor terms. Here, we investigate the effect of boundary conditions in a two-dimensional square lattice, which can induce different topologies in lattice systems. We find a relation between the induced topology and the Bell inequality's effectiveness in revealing nonlocal correlations. By using a combination of tropical algebra and tensor networks, we quantify their detection capacity for nonlocality. Our work can act as a guide to certify Bell nonlocality in many-qubit devices by choosing a suitable Hamiltonian and measuring its ground state energy; a task that many quantum experiments are purposely built for.
Simulation of quantum systems of a large number of strongly interacting particles persists as one of the most challenging, and computationally demanding, tasks in classical simulation, involving both non-relativistic applications like condensed matter physics and quantum chemistry, as well as relativistic applications like lattice gauge theory simulation. One of the major motivations for building a fault-tolerant quantum computer is the efficient simulation of many-body systems on such a device. While significant developments have been made in the quantum simulation of non-relativistic systems, the simulation of lattice gauge theories has lagged behind, with state-of-the-art Trotterized simulations requiring many orders of magnitude more resources than non-relativistic simulation, in stark contrast to the similar difficulty of these tasks in classical simulation. In this work, we conduct an in-depth analysis of the cost of simulating Abelian and non-Abelian lattice gauge theories in the Kogut-Susskind formulation using simulation methods with near-optimal scaling in system size, evolution time, and error. We provide explicit circuit constructions, as well as T-gate counts and qubit counts for the entire simulation algorithm. This investigation, the first of its kind, leads to up to 25 orders of magnitude improvement over Trotterization in spacetime volume for non-Abelian simulations. Such a dramatic improvement results largely from our algorithm having polynomial scaling with the number of colors, as opposed to exponential scaling in existing approaches. Our work demonstrates that the use of advanced algorithmic techniques leads to dramatic reductions in the cost of ab initio simulations of fundamental interactions, bringing it in step with resources required for first principles quantum simulation of chemistry and condensed matter physics.
Finding the minimal relative entropy of two quantum states under semi definite constraints is a pivotal problem located at the mathematical core of various applications in quantum information theory. In this work, we provide a method that addresses this optimisation. Our primordial motivation stems form the essential task of estimating secret key rates for QKD from the measurement statistics of a real device. Further applications include the computation of channel capacities, the estimation of entanglement measures from experimental data and many more. For all those tasks it is highly relevant to provide both, provable upper and lower bounds. An efficient method for this is the central result of this work. We build on a recently introduced integral representation of quantum relative entropy by P.E. Frenkel and provide reliable bounds as a sequence of semi definite programs (SDPs). Our approach ensures provable quadratic order convergence, while also maintaining resource efficiency in terms of SDP matrix dimensions. Additionally, we can provide gap estimates to the optimum at each iteration stage.
This study presents a roadmap towards utilizing a single arbitrary gate for universal quantum computing. Since two decades ago, it has been widely accepted that almost any single arbitrary gate with qubit number $>2$ is universal. Utilizing a single arbitrary gate for compiling is beneficial for systems with limited degrees of freedom, e.g. the scattering based quantum computing schemes. However, how to efficiently compile the wanted gate with a single arbitrary gate, and finally achieve fault-tolerant quantum computing is unknown. In this work, we show almost any target gate can be compiled to precision $\epsilon$ with a circuit depth of approximately $\log(\epsilon^{-1})$ with an improved brute-force compiling method. Under the assumption of reasonable classical resource, we show the gate imperfection can be lowered to $10^{-3}$. By treating the imperfection as coherent error, we show that the error can be further reduced by roughly two orders of magnitude with a measurement-free quantum error correction method.
Harald Putterman, Kyungjoo Noh, Rishi N. Patel, Gregory A. Peairs, Gregory S. MacCabe, Menyoung Lee, Shahriar Aghaeimeibodi, Connor T. Hann, Ignace Jarrige, Guillaume Marcaud, Yuan He, Hesam Moradinejad, John Clai Owens, Thomas Scaffidi, Patricio Arrangoiz-Arriola, Joe Iverson, Harry Levine, Fernando G.S.L. Brandão, Matthew H. Matheny, Oskar Painter Cat qubits, a type of bosonic qubit encoded in a harmonic oscillator, can exhibit an exponential noise bias against bit-flip errors with increasing mean photon number. Here, we focus on cat qubits stabilized by two-photon dissipation, where pairs of photons are added and removed from a harmonic oscillator by an auxiliary, lossy buffer mode. This process requires a large loss rate and strong nonlinearities of the buffer mode that must not degrade the coherence and linearity of the oscillator. In this work, we show how to overcome this challenge by coloring the loss environment of the buffer mode with a multi-pole filter and optimizing the circuit to take into account additional inductances in the buffer mode. Using these techniques, we achieve near-ideal enhancement of cat-qubit bit-flip times with increasing photon number, reaching over $0.1$ seconds with a mean photon number of only $4$. Concurrently, our cat qubit remains highly phase coherent, with phase-flip times corresponding to an effective lifetime of $T_{1,\text{eff}} \simeq 70$ $\mu$s, comparable with the bare oscillator lifetime. We achieve this performance even in the presence of an ancilla transmon, used for reading out the cat qubit states, by engineering a tunable oscillator-ancilla dispersive coupling. Furthermore, the low nonlinearity of the harmonic oscillator mode allows us to perform pulsed cat-qubit stabilization, an important control primitive, where the stabilization can remain off for a significant fraction (e.g., two thirds) of a $3~\mathrm{\mu s}$ cycle without degrading bit-flip times. These advances are important for the realization of scalable error-correction with cat qubits, where large noise bias and low phase-flip error rate enable the use of hardware-efficient outer error-correcting codes.
Exactly solvable models in quantum many body dynamics provide valuable insights into many interesting physical phenomena, and serve as platforms to rigorously investigate fundamental theoretical questions. Nevertheless, they are extremely rare and existing solvable models and solution techniques have serious limitations. In this paper we introduce a new family of exactly solvable unitary circuits which model quantum many body dynamics in discrete space and time. Unlike many previous solvable models, one can exactly compute the full quantum dynamics initialized from any matrix product state in this new family of models. The time evolution of local observables and correlations, the linear growth of Renyi entanglement entropy, spatiotemporal correlations, and outof-time-order correlations are all exactly computable. A key property of these models enabling the exact solution is that any time evolved local operator is an exact matrix product operator with finite bond dimension, even at arbitrarily long time, which we prove using the underlying (weak) Hopf algebra structure along with tensor network techniques. We lay down the general framework for the construction and solution of this family of models, and give several explicit examples. In particular, we study in detail a model constructed out of a weak Hopf algebra that is very close to a floquet version of the PXP model, and the exact results we obtain may shed light on the phenomenon of quantum many body scars, and more generally, floquet quantum dynamics in constrained systems.
Quantum dynamics compilation is an important task for improving quantum simulation efficiency: It aims to synthesize multi-qubit target dynamics into a circuit consisting of as few elementary gates as possible. Compared to deterministic methods such as Trotterization, variational quantum compilation (VQC) methods employ variational optimization to reduce gate costs while maintaining high accuracy. In this work, we explore the potential of a VQC scheme by making use of out-of-distribution generalization results in quantum machine learning (QML): By learning the action of a given many-body dynamics on a small data set of product states, we can obtain a unitary circuit that generalizes to highly entangled states such as the Haar random states. The efficiency in training allows us to use tensor network methods to compress such time-evolved product states by exploiting their low entanglement features. Our approach exceeds state-of-the-art compilation results in both system size and accuracy in one dimension ($1$D). For the first time, we extend VQC to systems on two-dimensional (2D) strips with a quasi-1D treatment, demonstrating a significant resource advantage over standard Trotterization methods, highlighting the method's promise for advancing quantum simulation tasks on near-term quantum processors.
CoVarince Root finding with classical shadows (CoVaR) was recently introduced as a new paradigm for training variational quantum circuits. Common approaches, such as variants of the Variational Quantum Eigensolver, aim to optimise a non-linear classical cost function and thus suffer from, e.g., poor local minima, high shot requirements and barren plateaus. In contrast, CoVaR fully exploits powerful classical shadows and finds joint roots of a very large number of covariances using only a logarithmic number of shots and linearly scaling classical HPC compute resources. As a result, CoVaR has been demonstrated to be particularly robust against local traps, however, its main limitation has been that it requires a sufficiently good initial state. We address this limitation by introducing an adiabatic morphing of the target Hamiltonian and demonstrate in a broad range of application examples that CoVaR can successfully prepare eigenstates of the target Hamiltonian when no initial warm start is known. CoVaR succeeds even when Hamiltonian energy gaps are very small -- this is in stark contrast to adiabatic evolution and phase estimation algorithms where circuit depths scale inversely with the Hamiltonian energy gaps. On the other hand, when the energy gaps are relatively small then adiabatic CoVaR may converge to higher excited states as opposed to a targeted specific low-lying state. Nevertheless, we exploit this feature of adiabatic CoVaR and demonstrate that it can be used to map out the low lying spectrum of a Hamiltonian which can be useful in practical applications, such as estimating thermal properties or in high-energy physics.
Quantum algorithms exploiting real-time evolution under a target Hamiltonian have demonstrated remarkable efficiency in extracting key spectral information. However, the broader potential of these methods, particularly beyond ground state calculations, is underexplored. In this work, we introduce the framework of multi-observable dynamic mode decomposition (MODMD), which combines the observable dynamic mode decomposition, a measurement-driven eigensolver tailored for near-term implementation, with classical shadow tomography. MODMD leverages random scrambling in the classical shadow technique to construct, with exponentially reduced resource requirements, a signal subspace that encodes rich spectral information. Notably, we replace typical Hadamard-test circuits with a protocol designed to predict low-rank observables, thus marking a new application of classical shadow tomography for predicting many low-rank observables. We establish theoretical guarantees on the spectral approximation from MODMD, taking into account distinct sources of error. In the ideal case, we prove that the spectral error scales as $\exp(- \Delta E t_{\rm max})$, where $\Delta E$ is the Hamiltonian spectral gap and $t_{\rm max}$ is the maximal simulation time. This analysis provides a rigorous justification of the rapid convergence observed across simulations. To demonstrate the utility of our framework, we consider its application to fundamental tasks, such as determining the low-lying, i.e. ground or excited, energies of representative many-body systems. Our work paves the path for efficient designs of measurement-driven algorithms on near-term and early fault-tolerant quantum devices.
Out-of-equilibrium fermionic quantum impurity models (QIM), describing a small interacting system coupled to a continuous fermionic bath, play an important role in condensed matter physics. Solving such models is a computationally demanding task, and a variety of computational approaches are based on finding approximate representations of the bath by a finite number of modes. In this paper, we formulate the problem of finding efficient bath representations as that of approximating a kernel of the bath's Feynman-Vernon influence functional by a sum of complex exponentials, with each term defining a fermionic pseudomode. Under mild assumptions on the analytic properties of the bath spectral density, we provide an analytic construction of pseudomodes, and prove that their number scales polylogarithmically with the maximum evolution time $T$ and the approximation error $\varepsilon$. We then demonstrate that the number of pseudomodes can be significantly reduced by an interpolative matrix decomposition (ID). Furthermore, we present a complementary approach, based on constructing rational approximations of the bath's spectral density using the ``AAA'' algorithm, followed by compression with ID. The combination of two approaches yields a pseudomode count scaling as $N_\text{ID} \sim \log(T)\log(1/\varepsilon)$, and the agreement between the two approches suggests that the result is close to optimal. Finally, to relate our findings to QIM, we derive an explicit Liouvillian that describes the time evolution of the combined impurity-pseudomodes system. These results establish bounds on the computational resources required for solving out-of-equilibrium QIMs, providing an efficient starting point for tensor-network methods for QIMs.
We introduce a new framework to study the dynamics of open quantum systems with linearly coupled Gaussian baths. Our approach replaces the continuous bath with an auxiliary discrete set of pseudomodes with dissipative dynamics, but we further relax the complete positivity requirement in the Lindblad master equation and formulate a quasi-Lindblad pseudomode theory. We show that this quasi-Lindblad pseudomode formulation directly leads to a representation of the bath correlation function in terms of a complex weighted sum of complex exponentials, an expansion that is known to be rapidly convergent in practice and thus leads to a compact set of pseudomodes. The pseudomode representation is not unique and can differ by a gauge choice. When the global dynamics can be simulated exactly, the system dynamics is unique and independent of the specific pseudomode representation. However, the gauge choice may affect the stability of the global dynamics, and we provide an analysis of why and when the global dynamics can retain stability despite losing positivity. We showcase the performance of this formulation across various spectral densities in both bosonic and fermionic problems, finding significant improvements over conventional pseudomode formulations.
Bosonic quantum error correction codes encode logical qubits in the Hilbert space of one or multiple harmonic oscillators. A prominent class of bosonic codes are Gottesman-Kitaev-Preskill (GKP) codes of which implementations have been demonstrated with trapped ions and microwave cavities. In this work, we investigate theoretically the preparation and error correction of a GKP qubit in a vibrational mode of a neutral atom stored in an optical dipole trap. This platform has recently shown remarkable progress in simultaneously controlling the motional and electronic degrees of freedom of trapped atoms. The protocols we develop make use of motional states and, additionally, internal electronic states of the trapped atom to serve as an ancilla qubit. We compare optical tweezer arrays and optical lattices and find that the latter provide more flexible control over the confinement in the out-of-plane direction, which can be utilized to optimize the conditions for the implementation of GKP codes. Concretely, the different frequency scales that the harmonic oscillators in the axial and radial lattice directions exhibit and a small oscillator anharmonicity prove to be beneficial for robust encodings of GKP states. Finally, we underpin the experimental feasibility of the proposed protocols by numerically simulating the preparation of GKP qubits in optical lattices with realistic parameters.
We present Astra, a novel and scalable decoder using graph neural networks. Our decoder works similarly to solving a Sudoku puzzle of constraints represented by the Tanner graph. In general, Quantum Low Density Parity Check (QLDPC) decoding is based on Belief Propagation (BP, a variant of message-passing) and requires time intensive post-processing methods such as Ordered Statistics Decoding (OSD). Without using any post-processing, Astra achieves higher thresholds and better logical error rates when compared to BP+OSD, both for surface codes trained up to distance 11 and Bivariate Bicycle (BB) codes trained up to distance 18. Moreover, we can successfully extrapolate the decoding functionality: we decode high distances (surface code up to distance 25 and BB code up to distance 34) by using decoders trained on lower distances. Astra+OSD is faster than BP+OSD. We show that with decreasing physical error rates, Astra+OSD makes progressively fewer calls to OSD when compared to BP+OSD, even in the context of extrapolated decoding. Astra(+OSD) achieves orders of magnitude lower logical error rates for BB codes compared to BP(+OSD). The source code is open-sourced at \urlhttps://github.com/arshpreetmaan/astra.
Blayney W. Walshe, Ben Q. Baragiola, Hugo Ferretti, José Gefaell, Michael Vasmer, Ryohei Weil, Takaya Matsuura, Thomas Jaeken, Giacomo Pantaleoni, Zhihua Han, Timo Hillmann, Nicolas C. Menicucci, Ilan Tzitrin, Rafael N. Alexander High-rate quantum error correcting codes mitigate the imposing scale of fault-tolerant quantum computers but require the efficient generation of non-local many-body entanglement. We provide a linear-optical architecture with these properties, compatible with arbitrary codes and Gottesman-Kitaev-Preskill qubits on generic lattices, and featuring a natural way to leverage physical noise bias. Simulations involving hyperbolic surface codes, promising quantum low-density parity-check codes, reveal a threshold comparable to the 2D surface code at about a ten-fold improvement in encoding rate.
In quantum computing, knowing the symmetries a given system or state obeys or disobeys is often useful. For example, Hamiltonian symmetries may limit allowed state transitions or simplify learning parameters in machine learning applications, and certain asymmetric quantum states are known to be resourceful in various applications. Symmetry testing algorithms provide a means to identify and quantify these properties with respect to a representation of a group. In this paper, we present a collection of quantum algorithms that realize projections onto the symmetric subspace, as well as the asymmetric subspace, of quantum systems. We describe how this can be modified to realize an antisymmetric projection as well, and we show how projectors can be combined in a systematic way to effectively measure various projections in a single quantum circuit. Using these constructions, we demonstrate applications such as testing for Werner-state symmetry and estimating Schmidt ranks of bipartite states, supported by experimental data from IBM Quantum systems. This work underscores the pivotal role of symmetry in simplifying quantum calculations and advancing quantum information tasks.
We present a scheme for speeding up quantum measurement. The scheme builds on previous protocols that entangle the system to be measured with ancillary systems. In the idealised situation of perfect entangling operations and no decoherence, it gives an exact space-time trade-off meaning the readout speed increases linearly with the number of ancilla. We verify this scheme is robust against experimental imperfections through numerical modelling of gate noise and readout errors, and under certain circumstances our scheme can even lead to better than linear improvement in the speed of measurement with the number of systems measured. This hardware-agnostic approach is broadly applicable to a range of quantum technology platforms and offers a route to accelerate mid-circuit measurement as required for effective quantum error correction.
Physical devices operating out of equilibrium are inherently affected by thermal fluctuations, limiting their operational precision. This issue is pronounced at microscopic and especially quantum scales and can only be mitigated by incurring additional entropy dissipation. Understanding this constraint is crucial for both fundamental physics and technological design. For instance, clocks are inherently governed by the second law of thermodynamics and need a thermodynamic flux towards equilibrium to measure time, which results in a minimum entropy dissipation per clock tick. Classical and quantum models and experiments often show a linear relationship between precision and dissipation, but the ultimate bounds on this relationship are unknown. Our theoretical discovery presents an extensible quantum many-body system that achieves clock precision scaling exponentially with entropy dissipation. This finding demonstrates that coherent quantum dynamics can surpass the traditional thermodynamic precision limits, potentially guiding the development of future high-precision, low-dissipation quantum devices.
Deciding which sets of quantum measurements allow a simultaneous readout is a central problem in quantum measurement theory. The problem is relevant not only from the foundational perspective but also has direct applications in quantum correlation problems fueled by incompatible measurements. Although central, only a few analytical criteria exist for deciding the incompatibility of general sets of measurements. This work approaches the problem through functions defined on the Boolean hypercube and their Fourier transformations. We show that this reformulation of the problem leads to a complete geometric characterisation of joint measurability of any finite set of unbiased binary qubit measurements and gives a necessary condition for the biased case. We discuss our results in the realm of quantum steering, where they translate into a family of steering inequalities. When certain unbiasedness conditions are fulfilled, these criteria are tight, hence fully characterizing the steering problem when the trusted party holds a qubit, and the untrusted party performs any finite number of binary measurements. We further discuss how our results point towards a second-order cone programming approach to measurement incompatibility and compare this to the predominantly used semi-definite programming-based techniques. We use our approach to falsify an existing conjecture on measurement incompatibility of special sets of measurements.
Quantum resource theories (QRTs) provide a comprehensive and practical framework for the analysis of diverse quantum phenomena. A fundamental task within QRTs is the quantification of resources inherent in a given quantum state. In this letter, we introduce a unified computational framework for a class of widely utilized quantum resource measures, derived from convex roof extensions. We establish that the computation of these convex roof resource measures can be reformulated as an optimization problem over a Stiefel manifold, which can be further unconstrained through polar projection. Compared to existing methods employing semi-definite programming (SDP), gradient-based techniques or seesaw strategy, our approach not only demonstrates superior computational efficiency but also maintains applicability across various scenarios within a streamlined workflow. We substantiate the efficacy of our method by applying it to several key quantum resources, including entanglement, coherence, and magic states. Moreover, our methodology can be readily extended to other convex roof quantities beyond the domain of resource theories, suggesting broad applicability in the realm of quantum information theory.
The seminal work by Impagliazzo and Rudich (STOC'89) demonstrated the impossibility of constructing classical public key encryption (PKE) from one-way functions (OWF) in a black-box manner. However, the question remains: can quantum PKE (QPKE) be constructed from quantumly secure OWF? A recent line of work has shown that it is indeed possible to build QPKE from OWF, but with one caveat -- they rely on quantum public keys, which cannot be authenticated and reused. In this work, we re-examine the possibility of perfect complete QPKE in the quantum random oracle model (QROM), where OWF exists. Our first main result: QPKE with classical public keys, secret keys and ciphertext, does not exist in the QROM, if the key generation only makes classical queries. Therefore, a necessary condition for constructing such QPKE from OWF is to have the key generation classically ``un-simulatable''. Previous discussions (Austrin et al. CRYPTO'22) on the impossibility of QPKE from OWF rely on a seemingly strong conjecture. Our work makes a significant step towards a complete and unconditional quantization of Impagliazzo and Rudich's results. Our second main result extends to QPKE with quantum public keys. The second main result: QPKE with quantum public keys, classical secret keys and ciphertext, does not exist in the QROM, if the key generation only makes classical queries and the quantum public key is either pure or ``efficiently clonable''. The result is tight due to all existing QPKEs constructions. Our result further gives evidence on why existing QPKEs lose reusability. To achieve these results, we use a novel argument based on conditional mutual information and quantum Markov chain by Fawzi and Renner (Communications in Mathematical Physics). We believe the techniques used in the work will find other usefulness in separations in quantum cryptography/complexity.
We present an exact synthesis algorithm for qutrit unitaries in $\mathcal{U}_{3^n}(\mathbb{Z}[1/3,e^{2\pi i/3}])$ over the Clifford$+T$ gate set with at most one ancilla. This extends the already known result of qutrit metaplectic gates being a subset of Clifford$+T$ gate set with one ancilla. As an intermediary step, we construct an algorithm to convert 3-level unitaries into multiply-controlled gates, analogous to Gray codes converting 2-level unitaries into multiply-controlled gates. Finally, using catalytic embeddings, we present an algorithm to exactly synthesize unitaries $\mathcal{U}_{3^n}(\mathbb{Z}[1/3,e^{2\pi i/9}])$ over the Clifford$+T$ gate set with at most 2 ancillas. This, in particular, gives an exact synthesis algorithm of single-qutrit Clifford$+\mathcal{D}$ over the multi-qutrit Clifford$+T$ gate set with at most two ancillas.
Generative machine learning models aim to learn the underlying distribution of the data in order to generate new samples. Quantum circuit Born machines (QCBMs) are a popular choice of quantum generative models which can be implemented on shallow circuits. Within the framework of photonic quantum computing, we present a QCBM designed for linear optics. We show that a new error mitigation technique, called recycling mitigation, greatly improves the training of QCBMs in realistic scenarios with photon loss, both through simulations and an experiment on a quantum photonic integrated processor.
Photon loss rates set an effective upper limit on the size of computations that can be run on current linear optical quantum devices. We present a family of techniques to mitigate the effects of photon loss on both output probabilities and expectation values derived from noisy linear optical circuits composed of an input of $n$ photons, an $m$-mode interferometer, and $m$ single photon detectors. Central to these techniques is the construction of objects called recycled probabilities. Recycled probabilities are constructed from output statistics affected by loss, and are designed to amplify the signal of the ideal (lossless) probabilities. Classical postprocessing techniques then take recycled probabilities as input and output a set of loss-mitigated probabilities, or expectation values. We provide analytical and numerical evidence that these methods can be applied, up to large sample sizes, to produce more accurate outputs than those obtained from postselection - which is currently the standard method of coping with photon loss when sampling from discrete variable linear optical quantum circuits. In contrast, we provide strong evidence that the popular zero noise extrapolation technique cannot improve on on the performance of postselection for any photon loss rate.
Nonstabilizerness, also known as magic, is a crucial resource for quantum computation. The growth in complexity of quantum processing units (QPUs) demands robust and scalable techniques for characterizing this resource. We introduce the notion of set magic: a set of states has this property if at least one state in the set is a non-stabilizer state. We show that certain two-state overlap inequalities, recently introduced as witnesses of basis-independent coherence, are also witnesses of multi-qubit set magic. We also show it is possible to certify the presence of magic across multiple QPUs without the need for entanglement between them and reducing the demands on each individual QPU.
The quantum dichotomies problem asks at what rate one pair of quantum states can be approximately mapped into another pair of quantum states. In the many copy limit and for vanishing error, the optimal rate is known to be given by the ratio of the respective quantum relative distances. Here, we study the large-deviation behavior of quantum dichotomies and determine the exact strong converse exponent based on the purified distance. Our result is characterized by a simple optimization of quantum Rényi information measures involving all four mutually non-commuting quantum states. Our findings thus constitute an operational example of studying multivariate extensions of quantum Rényi information measure.
Braneshop, and
the US National Science Foundation.
SciRate