Unclonable cryptography utilizes the principles of quantum mechanics to addresses cryptographic tasks that are impossible classically. We introduce a novel unclonable primitive in the context of secret sharing, called unclonable secret sharing (USS). In a USS scheme, there are $n$ shareholders, each holding a share of a classical secret represented as a quantum state. They can recover the secret once all parties (or at least $t$ parties) come together with their shares. Importantly, it should be infeasible to copy their own shares and send the copies to two non-communicating parties, enabling both of them to recover the secret. Our work initiates a formal investigation into the realm of unclonable secret sharing, shedding light on its implications, constructions, and inherent limitations. ** Connections: We explore the connections between USS and other quantum cryptographic primitives such as unclonable encryption and position verification, showing the difficulties to achieve USS in different scenarios. **Limited Entanglement: In the case where the adversarial shareholders do not share any entanglement or limited entanglement, we demonstrate information-theoretic constructions for USS. **Large Entanglement: If we allow the adversarial shareholders to have unbounded entanglement resources (and unbounded computation), we prove that unclonable secret sharing is impossible. On the other hand, in the quantum random oracle model where the adversary can only make a bounded polynomial number of queries, we show a construction secure even with unbounded entanglement. Furthermore, even when these adversaries possess only a polynomial amount of entanglement resources, we establish that any unclonable secret sharing scheme with a reconstruction function implementable using Cliffords and logarithmically many T-gates is also unattainable.
We construct a convergent family of outer approximations for the problem of optimizing polynomial functions over convex bodies subject to polynomial constraints. This is achieved by generalizing the polarization hierarchy, which has previously been introduced for the study of polynomial optimization problems over state spaces of $C^*$-algebras, to convex cones in finite dimensions. If the convex bodies can be characterized by linear or semidefinite programs, then the same is true for our hierarchy. Convergence is proven by relating the problem to a certain de Finetti theorem for general probabilistic theories, which are studied as possible generalizations of quantum mechanics. We apply the method to the problem of nonnegative matrix factorization, and in particular to the nested rectangles problem. A numerical implementation of the third level of the hierarchy is shown to give rise to a very tight approximation for this problem.
The Choi-state is an indispensable tool in the study and analysis of quantum channels. Considering a channel in terms of its associated Choi-state can greatly simplify problems. It also offers an alternative approach to the characterisation of a channel, with properties of the Choi-state providing novel insight into a channel's behaviour. The rank of a Choi-state, termed the Choi-rank, has proven to be an important characterising property, and here, its significance is further elucidated through an operational interpretation. The Choi-rank is shown to provide a universal bound on how successfully two agents, Alice and Bob, can perform an entanglement-assisted exclusion task. The task can be considered an extension of super-dense coding, where Bob can only output information about Alice's encoded bit-string with certainty. Conclusive state exclusion, in place of state discrimination, is therefore considered at the culmination of the super-dense coding protocol. In order to prove this result, a necessary condition for conclusive k-state exclusion of a set of states is presented in order to achieve this result, and the notions of weak and strong exclusion are introduced.
Quantum signal processing is a framework for implementing polynomial functions on quantum computers. To implement a given polynomial $P$, one must first construct a corresponding complementary polynomial $Q$. Existing approaches to this problem employ numerical methods that are not amenable to explicit error analysis. We present a new approach to complementary polynomials using complex analysis. Our main mathematical result is a contour integral representation for a canonical complementary polynomial. The integral representation on the unit circle has a particularly simple and efficacious Fourier analytic interpretation, which we use to develop a Fast Fourier Transform-based algorithm for the efficient calculation of $Q$ in the monomial basis with explicit error guarantees. Numerical evidence that our algorithm outperforms the state-of-the-art optimization-based method for computing complementary polynomials is provided.
Ensuring data privacy in machine learning models is critical, particularly in distributed settings where model gradients are typically shared among multiple parties to allow collaborative learning. Motivated by the increasing success of recovering input data from the gradients of classical models, this study addresses a central question: How hard is it to recover the input data from the gradients of quantum machine learning models? Focusing on variational quantum circuits (VQC) as learning models, we uncover the crucial role played by the dynamical Lie algebra (DLA) of the VQC ansatz in determining privacy vulnerabilities. While the DLA has previously been linked to the classical simulatability and trainability of VQC models, this work, for the first time, establishes its connection to the privacy of VQC models. In particular, we show that properties conducive to the trainability of VQCs, such as a polynomial-sized DLA, also facilitate the extraction of detailed snapshots of the input. We term this a weak privacy breach, as the snapshots enable training VQC models for distinct learning tasks without direct access to the original input. Further, we investigate the conditions for a strong privacy breach where the original input data can be recovered from these snapshots by classical or quantum-assisted polynomial time methods. We establish conditions on the encoding map such as classical simulatability, overlap with DLA basis, and its Fourier frequency characteristics that enable such a privacy breach of VQC models. Our findings thus play a crucial role in detailing the prospects of quantum privacy advantage by guiding the requirements for designing quantum machine learning models that balance trainability with robust privacy protection.
This work investigates the oracle separation between the physically motivated complexity class of noisy quantum circuits, inspired by definitions such as those presented by Chen, Cotler, Huang, and Li (2022). We establish that with a constant error rate, separation can be achieved in terms of NP. When the error rate is $\Omega(\log n/n)$, we can extend this result to the separation of PH. Notably, our oracles, in all separations, do not necessitate error correction schemes or fault tolerance, as all quantum circuits are of constant depth. This indicates that even quantum computers with minor errors, without error correction, may surpass classical complexity classes under various scenarios and assumptions. We also explore various common noise settings and present new classical hardness results, generalizing those found in studies by Raz and Tal (2022) and Bassirian, Bouland, Fefferman, Gunn, and Tal (2021), which are of independent interest.
Efficient characterization of higher dimensional many-body physical states presents significant challenges. In this paper, we propose a new class of Project Entangled Pair State (PEPS) that incorporates two isometric conditions. This new class facilitates the efficient calculation of general local observables and certain two-point correlation functions, which have been previously shown to be intractable for general PEPS, or PEPS with only a single isometric constraint. Despite incorporating two isometric conditions, our class preserves the rich physical structure while enhancing the analytical capabilities. It features a large set of tunable parameters, with only a subleading correction compared to that of general PEPS. Furthermore, we analytically demonstrate that this class can encode universal quantum computations and can represent a transition from topological to trivial order.
The main contribution of our paper is to introduce a number of multivariate quantum fidelities and show that they satisfy several desirable properties that are natural extensions of those of the Uhlmann and Holevo fidelities. We propose three variants that reduce to the average pairwise fidelity for commuting states: average pairwise $z$-fidelities, the multivariate semi-definite programming (SDP) fidelity, and a multivariate fidelity inspired by an existing secrecy measure. The second one is obtained by extending the SDP formulation of the Uhlmann fidelity to more than two states. All three of these variants satisfy the following properties: (i) reduction to multivariate classical fidelities for commuting states, (ii) the data-processing inequality, (iii) invariance under permutations of the states, (iv) its values are in the interval $[0,1]$; they are faithful, that is, their values are equal to one if and only if all the states are equal, and they satisfy orthogonality, that is their values are equal to zero if and only if the states are mutually orthogonal to each other, (v) direct-sum property, (vi) joint concavity, and (vii) uniform continuity bounds under certain conditions. Furthermore, we establish inequalities relating these different variants, indeed clarifying that all these definitions coincide with the average pairwise fidelity for commuting states. Lastly, we introduce another multivariate fidelity called multivariate log-Euclidean fidelity, which is a quantum generalization of the Matusita multivariate fidelity. We also show that it satisfies most of the desirable properties listed above, it is a function of a multivariate log-Euclidean divergence, and has an operational interpretation in terms of quantum hypothesis testing with an arbitrarily varying null hypothesis.
A large spectrum of problems in classical physics and engineering, such as turbulence, is governed by nonlinear differential equations, which typically require high-performance computing to be solved. Over the past decade, however, the growth of classical computing power has slowed down because the miniaturisation of chips has been approaching the atomic scale. This is marking an end to Moore's law, which calls for a new computing paradigm: Quantum computing is a prime candidate. In this paper, we offer a perspective on the current challenges that need to be overcome in order to use quantum computing for the simulation of nonlinear dynamics. We review and discuss progress in the development of both quantum algorithms for nonlinear equations and quantum hardware. We propose pairings between quantum algorithms for nonlinear equations and quantum hardware concepts. These avenues open new opportunities for the simulation of nonlinear systems and turbulence.
Dynamic quantum simulation is a leading application for achieving quantum advantage. However, high circuit depths remain a limiting factor on near-term quantum hardware. We present a compilation algorithm based on Matrix Product Operators for generating compressed circuits enabling real-time simulation on digital quantum computers, that for a given depth are more accurate than all Trotterizations of the same depth. By the efficient use of environment tensors, the algorithm is scalable in depth beyond prior work, and we present circuit compilations of up to 64 layers of $SU(4)$ gates. Surpassing only 1D circuits, our approach can flexibly target a particular quasi-2D gate topology. We demonstrate this by compiling a 52-qubit 2D Transverse-Field Ising propagator onto the IBM Heavy-Hex topology. For all circuit depths and widths tested, we produce circuits with smaller errors than all equivalent depth Trotter unitaries, corresponding to reductions in error by up to 4 orders of magnitude and circuit depth compressions with a factor of over 6.
Efficient state preparation is essential for implementing efficient quantum algorithms. Whilst several techniques for low-cost state preparation exist, this work facilitates further classes of states, whose amplitudes are well approximated by piecewise polynomials. We show how such states can be efficiently prepared using a piecewise Quantum Singular Value Transformation along with a new piecewise linear diagonal block encoding. We illustrate this with the explicit examples of $\sqrt{x}|x\rangle$ and $\log x|x\rangle$. Further, our technique reduces the cost of window boosted Quantum Phase Estimation by efficiently preparing the B-spline window state. We demonstrate this window state requires 100 times fewer T-gates to prepare than the state-of-the-art Kaiser window state, and we show that the B-spline window replicates the Kaiser window's exponential reduction in tail probability for QPE.
We develop a notion of quantum channels that can make states useless for universal quantum computation by destroying their magic (non-stabilizerness) - we refer to them as magic-breaking channels. We establish the properties of these channels in arbitrary dimensions. We prove the necessary and sufficient criteria for qubit channels to be magic-breaking and present an algorithm for determining the same. Moreover, we provide compact criteria in terms of the parameters for several classes of qubit channels to be magic-breaking under various post-processing operations. Further, we investigate the necessary and sufficient conditions for the tensor product of multiple qubit channels to be magic-breaking. We establish implications of the same for the dynamical resource theory of magic preservability.
Estimating quantum fermionic properties is a computationally difficult yet crucial task for the study of electronic systems. Recent developments have begun to address this challenge by introducing classical shadows protocols relying on sampling of Fermionic Gaussian Unitaries (FGUs): a class of transformations in fermionic space which can be conveniently mapped to matchgates circuits. The different protocols proposed in the literature use different sub-ensembles of the orthogonal group $O(2n)$ to which FGUs can be associated. We propose an approach that unifies these different protocols, proving their equivalence, and deriving from it an optimal sampling scheme. We begin by demonstrating that the first three moments of the FGU ensemble associated with $SO(2n)$ and of its intersection with the Clifford group are equal, generalizing a result known for $O(2n)$ and addressing a question raised in previous works. Building on this proof, we establish the equivalence between the shadows protocols resulting from FGU ensembles analyzed in the literature. Finally, from our results, we propose a sampling scheme for a small sub-ensemble of matchgates circuits that is optimal in terms of number of gates and that inherits the performances guarantees of the previous ensembles.
Measuring the distinguishability between quantum states is a basic problem in quantum information theory. In this paper, we develop optimal quantum algorithms that estimate both the trace distance and the (square root) fidelity between pure states to within additive error $\varepsilon$ using $\Theta(1/\varepsilon)$ queries to their state-preparation circuits, quadratically improving the long-standing folklore $O(1/\varepsilon^2)$. At the heart of our construction, is an algorithmic tool for quantum square root amplitude estimation, which generalizes the well-known quantum amplitude estimation.
Distributed quantum computing allows the modular construction of large-scale quantum computers and enables new protocols for blind quantum computation. However, such applications in the large-scale, fault-tolerant regime place stringent demands on the fidelity and rate of entanglement generation which are not met by existing methods for quantum interconnects. In this work, we develop constant-rate entanglement distillation methods to address this bottleneck in the setting of noisy local operations. By using a sequence of two-way entanglement distillation protocols based on quantum error detecting codes with increasing rate, and combining with standard fault tolerance techniques, we achieve constant-rate entanglement distillation. We prove the scheme has constant-rate in expectation and further numerically optimize to achieve low practical overhead subject to memory constraints. We find our optimized schemes outperform existing computationally efficient quantum interconnect schemes by an order of magnitude in relevant regimes, leading to a direct speed-up in the execution of distributed quantum algorithms.
Feedback control of open quantum systems is of fundamental importance for practical applications in various contexts, ranging from quantum computation to quantum error correction and quantum metrology. Its use in the context of thermodynamics further enables the study of the interplay between information and energy. However, deriving optimal feedback control strategies is highly challenging, as it involves the optimal control of open quantum systems, the stochastic nature of quantum measurement, and the inclusion of policies that maximize a long-term time- and trajectory-averaged goal. In this work, we employ a reinforcement learning approach to automate and capture the role of a quantum Maxwell's demon: the agent takes the literal role of discovering optimal feedback control strategies in qubit-based systems that maximize a trade-off between measurement-powered cooling and measurement efficiency. Considering weak or projective quantum measurements, we explore different regimes based on the ordering between the thermalization, the measurement, and the unitary feedback timescales, finding different and highly non-intuitive, yet interpretable, strategies. In the thermalization-dominated regime, we find strategies with elaborate finite-time thermalization protocols conditioned on measurement outcomes. In the measurement-dominated regime, we find that optimal strategies involve adaptively measuring different qubit observables reflecting the acquired information, and repeating multiple weak measurements until the quantum state is "sufficiently pure", leading to random walks in state space. Finally, we study the case when all timescales are comparable, finding new feedback control strategies that considerably outperform more intuitive ones. We discuss a two-qubit example where we explore the role of entanglement and conclude discussing the scaling of our results to quantum many-body systems.
We provide a brief review of the fundamentals of quantum computation and quantum error correction for the participants of the first Quantum Information Knowledge (QuIK) workshop at the 2024 IEEE International Symposium on Information Theory (ISIT 2024). While this is not a comprehensive review, we provide many references for the reader to delve deeper into the concepts and research directions.
Simulating time evolution is one of the most natural applications of quantum computers and is thus one of the most promising prospects for achieving practical quantum advantage. Here we develop quantum algorithms to extract thermodynamic properties by estimating the density of states (DOS), a central object in quantum statistical mechanics. We introduce key innovations that significantly improve the practicality and extend the generality of previous techniques. First, our approach allows one to estimate the DOS for a specific subspace of the full Hilbert space. This is crucial for fermionic systems, since fermion-to-qubit mappings partition the full Hilbert space into subspaces of fixed number, on which both canonical and grand canonical ensemble properties depend. Second, in our approach, by time evolving very simple, random initial states (e.g. random computational basis states), we can exactly recover the DOS on average. Third, due to circuit-depth limitations, we only reconstruct the DOS up to a convolution with a Gaussian window - thus all imperfections that shift the energy levels by less than the width of the convolution window will not significantly affect the estimated DOS. For these reasons we find the approach is a promising candidate for early quantum advantage as even short-time, noisy dynamics yield a semi-quantitative reconstruction of the DOS (convolution with a broad Gaussian window), while early fault tolerant devices will likely enable higher resolution DOS reconstruction through longer time evolution. We demonstrate the practicality of our approach in representative Fermi-Hubbard and spin models and find that our approach is highly robust to algorithmic errors in the time evolution and to gate noise. We show that our approach is compatible with NISQ-friendly variational methods, introducing a new technique for variational time evolution in noisy DOS computations.
Estimating the eigenstate properties of quantum many-body systems is a long-standing, challenging problem for both classical and quantum computing. For the task of eigenstate preparation, quantum signal processing (QSP) has established near-optimal query complexity $O( \Delta^{-1} \log(\epsilon^{-1}) )$ by querying the block encoding of the Hamiltonian $H$ where $\Delta$ is the energy gap and $\epsilon$ is the target precision. However, QSP is challenging for both near-term noisy quantum computers and early fault-tolerant quantum computers (FTQC), which are limited by the number of logical qubits and circuit depth. To date, early FTQC algorithms have focused on querying the perfect time evolution $e^{-iHt}$. It remains uncertain whether early FTQC algorithms can maintain good asymptotic scaling at the gate level. Moreover, when considering qubit connectivity, the circuit depth of existing FTQC algorithms may scale suboptimally with system size. Here, we present a full-stack design of a random sampling algorithm for estimating the eigenenergy and the observable expectations on the eigenstates, which can achieve high precision and good system size scaling. The gate complexity has a logarithmic dependence on precision $ {O}(\log^{1+o(1)} (1/\epsilon))$ for generic Hamiltonians, which cannot achieved by methods using Trottersiation to realise $e^{-iHt}$ like in QETU. For $n$-qubit lattice Hamiltonians, our method achieves near-optimal system size dependence with the gate complexity $O(n^{1+o(1)})$. When restricting the qubit connectivity to a linear nearest-neighbour architecture, The method shows advantages in circuit depth, with $O(n^{o(1)})$ for lattice models and $O(n^{2+o(1)})$ for electronic structure problems. We compare the resource requirements (CNOT gates, T gates and qubit numbers) by phase estimation, QSP, and QETU, in lattice and molecular problems.
We consider quantum systems with energy constraints. In general, quantum channels and continuous-time dynamics need not satisfy energy conservation. Physically meaningful channels, however, can only introduce a finite amount of energy to the system, and continuous-time dynamics may only increase the energy gradually over time. We systematically study such "energy-limited" channels and dynamics. For Markovian dynamics, energy-limitedness is equivalent to a single operator inequality in the Heisenberg picture. By tracking the output energy, we observe that the energy-constrained operator and diamond norms of Shirokov and Winter satisfy submultiplicativity estimates with respect to energy-limited channels. This makes for a powerful toolkit for quantitative analyses of dynamical problems in finite and infinite-dimensional systems. As an application, we derive state-dependent bounds for quantum speed limits and related problems that outperform the usual operator/diamond norm estimates, which have to account for fluctuations in high-energy states.
We propose an extension of the classical Rényi divergences to quantum states through an optimization over probability distributions induced by restricted sets of measurements. In particular, we define the notion of locally-measured Rényi divergences, where the set of allowed measurements originates from variants of locality constraints between (distant) parties $A$ and $B$. We then derive variational bounds on the locally-measured Rényi divergences and systematically discuss when these bounds become exact characterizations. As an application, we evaluate the locally-measured Rényi divergences on variants of highly symmetric data-hiding states, showcasing the reduced distinguishing power of locality-constrained measurements. For $n$-fold tensor powers, we further employ our variational formulae to derive corresponding additivity results, which gives the locally-measured Rényi divergences operational meaning as optimal rate exponents in asymptotic locally-measured hypothesis testing.
We investigate how quantum information, encoded in a quantum field, evolves during the expansion of spacetime. Due to information loss across the horizon, a local observer experiences this evolution as a nonunitary quantum channel. We obtain this channel in the case of de Sitter spacetime by assuming the initial global state encodes a signal state via fluctuations of the Bunch-Davies vacuum. Notably, de Sitter evolution exhibits intriguing cloning properties, establishing a connection between the curvature of spacetime and the propagation of quantum information.
In this work we study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. Given $n$ points and $n$ lines in the plane, the task is to determine whether there is a point-line incidence. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n^{4/3})$ time, with matching lower bounds in some restricted settings. Our results are two different quantum algorithms with time complexity $\widetilde O(n^{5/6})$. The first algorithm is based on partition trees and the quantum backtracking algorithm. The second algorithm uses a quantum walk together with a history-independent dynamic data structure for storing line arrangement which supports efficient point location queries. In the setting where the number of points and lines differ, the quantum walk-based algorithm is asymptotically faster. The quantum speedups for the aforementioned data structures may be useful for other geometric problems.
The ZX calculus is a graphical language for representing and rewriting quantum circuits. While its graphical rewrite rules preserve semantics, they may not preserve other features. For example, applying rewrites to a circuit that implements an error-correcting code can change its distance. Here, we define the notion of distance-preserving rewrites that enables the transformation of error-correcting codes without changing their distance. Using these rewrites, we propose an algorithm that transforms a high-weight Pauli measurement into an equivalent quantum circuit with only single- and two-qubit operations. Since we only use distance-preserving rewrites, we guarantee that errors in the low-weight implementation do not propagate to create multiple data errors. Going further, we generalise the Floquetification procedure of [arXiv:2308.15489] to arbitrary stabiliser codes. Given a stabiliser code, we synthesise a new quantum error-correcting code which encodes the same number of qubits with at least the same distance. The number of additional qubits this method requires is linearly dependent on the weight or the largest Pauli measurement. This creates a tradeoff between easily implementable low-weight Pauli measurements at the cost of additional physical qubits.
We introduce a family of fidelities based on the Riemannian geometry of the Bures-Wasserstein manifold we call the generalized fidelity. We show that this family of fidelities generalizes standard quantum fidelities such as Uhlamnn-, Holevo-, and Matsumoto fidelity and demonstrate that it satisfies analogous celebrated properties. The generalized fidelity naturally arises from a generalized Bures distance, the natural distance obtained from the linearization of the Bures-Wasserstein manifold. We prove various invariance and covariance properties of generalized fidelity as the point of linearization moves along geodesic-related paths. We also provide a Block-matrix characterization and prove an Uhlmann-like theorem, as well as provide further extensions to the multivariate setting and quantum Renyi divergences, generalizing Petz-, Sandwich-, Reverse sandwich-, and Geometric Renyi divergences of order $\alpha$.
We show that there exists a unitary quantum oracle relative to which quantum commitments exist but no (efficiently verifiable) one-way state generators exist. Both have been widely considered candidates for replacing one-way functions as the minimal assumption for cryptography: the weakest cryptographic assumption implied by all of computational cryptography. Recent work has shown that commitments can be constructed from one-way state generators, but the other direction has remained open. Our results rule out any black-box construction, and thus settle this crucial open problem, suggesting that quantum commitments (as well as its equivalency class of EFI pairs, quantum oblivious transfer, and secure quantum multiparty computation) appear to be strictly weakest among all known cryptographic primitives.
Quantum error correction (QEC) is essential for operating quantum computers in the presence of noise. Here, we accurately decode arbitrary Calderbank-Shor-Steane (CSS) codes via the maximum satisfiability (MaxSAT) problem. We show how to map quantum maximum likelihood problem of CSS codes of arbitrary geometry and parity check weight into MaxSAT problems. We incorporate the syndrome measurements as hard clauses, while qubit and measurement error probabilities, including biased and non-uniform, are encoded as soft MaxSAT clauses. For the code capacity of color codes on a hexagonal lattice, our decoder has a higher threshold and superior scaling in noise suppression compared to belief propagation with ordered statistics post-processing (BP-OSD), while showing similar scaling in computational cost. Further, we decode surface codes and recently proposed bivariate quantum low-density parity check (QLDPC) codes where we find lower error rates than BP-OSD. Finally, we connect the complexity of MaxSAT decoding to a computational phase transition controlled by the clause density of the MaxSAT problem, where we show that our mapping is always in the computationally ''easy`` phase. Our MaxSAT decoder can be further parallelised or implemented on ASICs and FPGAs, promising potential further speedups of several orders of magnitude. Our work provides a flexible platform towards practical applications on quantum computers.
Random numbers are used in a wide range of sciences. In many applications, generating unpredictable private random numbers is indispensable. Device-independent quantum random number generation is a framework that makes use of the intrinsic randomness of quantum processes to generate numbers that are fundamentally unpredictable according to our current understanding of physics. While device-independent quantum random number generation is an exceptional theoretical feat, the difficulty of controlling quantum systems makes it challenging to carry out in practice. It is therefore desirable to harness the full power of the quantum degrees of freedom (the dimension) that one can control. It is known that no more than $2 \log(d)$ bits of private device-independent randomness can be extracted from a quantum system of local dimension $d$. In this paper we demonstrate that this bound can be achieved for all dimensions $d$ by providing a family of explicit protocols. In order to obtain our result, we develop new certification techniques that can be of wider interest in device-independent applications for scenarios in which complete certification ('self-testing') is impossible or impractical.
Higher-order transformations that act on a certain number of input quantum channels in an indefinite causal order - such as the quantum switch - cannot be described by standard quantum circuits that use the same number of calls of the input quantum channels. However, the question remains whether they can be simulated, i.e., whether their action on their input channels can be deterministically reproduced, for all arbitrary inputs, by a quantum circuit that uses a larger number of calls of the input channels. Here, we prove that when only one extra call of each input channel is available, the quantum switch cannot be simulated by any quantum circuit. We demonstrate that this result is robust by showing that, even when probabilistic and approximate simulations are considered, higher-order transformations that are close to the quantum switch can be at best simulated with a probability strictly less than one. This result stands in stark contrast with the known fact that, when the quantum switch acts exclusively on unitary channels, its action can be simulated.
We consider an open quantum system undergoing Markovian dynamics, the latter being modelled by a discrete-time quantum Markov semigroup $\{\Phi^n\}_{n \in {\mathbb{N}}}$, resulting from the action of sequential uses of a quantum channel $\Phi$, with $n \in {\mathbb{N}}$ being the discrete time parameter. We find upper and lower bounds on the one-shot $\epsilon$-error information transmission capacities of $\Phi^n$ for a finite time $n\in \mathbb{N}$ and $\epsilon \in [0,1)$ in terms of the structure of the peripheral space of the channel $\Phi$. We consider transmission of $(i)$ classical information (both in the unassisted and entanglement-assisted settings); $(ii)$ quantum information and $(iii)$ private classical information.
We perform a complete classification of all 56 subgroups of the two-qubit Clifford group containing the two-qubit Pauli group. We provide generators for these groups using gates familiar to the quantum information community and we reference these groups against the group libraries provided in GAP. We also list several families of groups in higher levels of the two-qubit Clifford hierarchy.
Topologically ordered quantum matter exhibits intriguing long-range patterns of entanglement, which reveal themselves in subsystem entropies. However, measuring such entropies, which can be used to certify topological order, on large partitions is challenging and becomes practically unfeasible for large systems. We propose a protocol based on local adiabatic deformations of the Hamiltonian which extracts the universal features of long-range topological entanglement from measurements on small subsystems of finite size, trading an exponential number of measurements against a polynomial-time evolution. Our protocol is general and readily applicable to various quantum simulation architectures. We apply our method to various string-net models representing both abelian and non-abelian topologically ordered phases, and illustrate its application to neutral atom tweezer arrays with numerical simulations.
We present a $\mathsf{BQSPACE}(O(\log n))$-procedure to count $st$-paths on directed graphs for which we are promised that there are at most polynomially many paths starting in $s$ and polynomially many paths ending in $t$. For comparison, the best known classical upper bound in this case just to decide $st$-connectivity is $\mathsf{DSPACE}(O(\log^2 n/ \log \log n))$. The result establishes a new relationship between $\mathsf{BQL}$ and unambiguity and fewness subclasses of $\mathsf{NL}$. Further, some preprocessing in our approach also allows us to verify whether there are at most polynomially many paths between any two nodes in $\mathsf{BQSPACE}(O(\log n))$. This yields the first natural candidate for a language problem separating $\mathsf{BQL}$ from $\mathsf{L}$ and $\mathsf{BPL}$. Until now, all candidates separating these classes were promise problems.
Chaos makes isolated systems of many interacting particles quickly thermalize and forget about their past. Here, we show that quantum mechanics hinders chaos in many-body systems: although the quantum eigenstates are thermal and strongly entangled, exponentially many of them are scarred, that is, have an enlarged weight along underlying classical unstable periodic orbits. Scarring makes the system more likely to be found on an orbit it was initialized on, retaining a memory of its past and thus weakly breaking ergodicity, even at long times and despite the system being fully thermal. We demonstrate the ubiquity of quantum scarring in many-body systems by considering a large family of spin models, including some of the most popular ones from condensed matter physics. Our findings, at hand for modern quantum simulators, prove structure in spite of chaos in many-body quantum systems.
We present a new approach for witnessing quantum resources, including entanglement and coherence, based on heat generation. Inspired by the concept of Maxwell's demon, we analyze the heat exchange between a quantum system and a thermal environment assisted by a quantum memory. By exploring the fundamental limitations of heat transfer in this scenario, we find that quantum states can reveal their non-classical signatures via energy exchange with a thermal environment. This approach offers a promising alternative to complex, system-specific measurements, as it relies solely on fixed energy measurements. To demonstrate the effectiveness of our method, we apply it to the detection of entanglement in isotropic states and coherence in a two-spin system interacting with a single-mode electromagnetic field.
We present the generalization of the CNC formalism, based on closed and noncontextual sets of Pauli observables, to the setting of odd-prime-dimensional qudits. By introducing new CNC-type phase space point operators, we construct a quasiprobability representation for quantum computation which is covariant with respect to the Clifford group and positivity preserving under Pauli measurements, and whose nonnegative sector strictly contains the subtheory of quantum theory described by nonnegative Wigner functions. This allows for a broader class of magic state quantum circuits to be efficiently classically simulated than those covered by the stabilizer formalism and Wigner function methods.
Work extraction is one of the most central processes in quantum thermodynamics. However, the prior analysis of optimal extractable work has been restricted to a limited operational scenario where complete information about the initial state is given. Here, we introduce a general framework of black box work extraction, which addresses the inaccessibility of information on the initial state. We show that the optimal extractable work in the black box setting is completely characterized by the performance of a composite hypothesis testing task, a fundamental problem in information theory.We employ this general relation to reduce the asymptotic black box work extraction to the quantum Stein's lemma in composite hypothesis testing, allowing us to provide their exact characterization in terms of the Helmholtz free energy. We also show a new quantum Stein's lemma motivated in this physical setting, where a composite hypothesis contains a certain correlation. Our work exhibits the importance of information about the initial state and gives a new interpretation of the quantities in the composite quantum hypothesis testing, encouraging the interplay between the physical settings and the information theory.
Quantum imaginary-time evolution (QITE) is a promising tool to prepare thermal or ground states of Hamiltonians, as convergence is guaranteed when the evolved state overlaps with the ground state. However, its implementation using a parameterized quantum circuit is impractical as the number of parameters $m$ increases, since each step in the evolution takes $\Theta(m^2)$ state preparations to calculate the quantum Fisher information matrix (QFIM). In this work, we accelerate QITE by rapid estimation of the QFIM, while conserving the convergence guarantees to the extent possible. To this end, we prove that if a parameterized state is rotated by a 2-design and measured in the computational basis, then the QFIM can be inferred from partial derivative cross correlations of the probability outcomes. One sample estimate costs only $\Theta(m)$ state preparations, leading to rapid QFIM estimation when a few samples suffice. The second family of estimators take greater liberties and replace QFIMs with averaged classical Fisher information matrices (CFIMs). In an extreme special case optimized for rapid (over accurate) descent, just one CFIM sample is drawn. We justify the second estimator family by proving rapid descent. Guided by these results, we propose the random-measurement imaginary-time evolution (RMITE) algorithm, which we showcase and test in several molecular systems, with the goal of preparing ground states.
Quantum access to arbitrary classical data encoded in unitary black-box oracles underlies interesting data-intensive quantum algorithms, such as machine learning or electronic structure simulation. The feasibility of these applications depends crucially on gate-efficient implementations of these oracles, which are commonly some reversible versions of the boolean circuit for a classical lookup table. We present a general parameterized architecture for quantum circuits implementing a lookup table that encompasses all prior work in realizing a continuum of optimal tradeoffs between qubits, non-Clifford gates, and error resilience, up to logarithmic factors. Our architecture assumes only local 2D connectivity, yet recovers results that previously required all-to-all connectivity, particularly, with the appropriate parameters, poly-logarithmic error scaling. We also identify novel regimes, such as simultaneous sublinear scaling in all parameters. These results enable tailoring implementations of the commonly used lookup table primitive to any given quantum device with constrained resources.
Bound entanglement is a special form of quantum entanglement that cannot be used for distillation, i.e., the local transformation of copies of arbitrarily entangled states into a smaller number of approximately maximally entangled states. Implying an inherent irreversibility of quantum resources, this phenomenon highlights the gaps in our current theory of entanglement. This review provides a comprehensive exploration of the key findings on bipartite bound entanglement. We focus on systems of finite dimensions, an area of high relevance for many quantum information processing tasks. We elucidate the properties of bound entanglement and its interconnections with various facets of quantum information theory and quantum information processing. The article illuminates areas where our understanding of bound entangled states, particularly their detection and characterization, is yet to be fully developed. By highlighting the need for further research into this phenomenon and underscoring relevant open questions, this article invites researchers to unravel its relevance for our understanding of entanglement in Nature and how this resource can most effectively be used for applications in quantum technology.
In quantum information, nonlocal games are particularly useful for differentiating classical, quantum, and non-signalling correlations. An example of differentiation is given by the principle of no-collapse of communication complexity, which is often interpreted as necessary for a feasible physical theory. It is satisfied by quantum correlations but violated by some non-signalling ones. In this work, we investigate this principle in the context of three nonlocal games related to graph theory, starting from the well-known graph isomorphism and graph coloring games, and introducing a new game, the vertex distance game, with a parameter $D\in\mathbb N$, that generalizes the former two to some extent. For these three games, we prove that perfect non-signalling strategies collapse communication complexity under favorable conditions. We also define a refinement of fractional isomorphism of graphs, namely D-fractional isomorphisms, and we show that this characterizes perfect non-signalling strategies for the vertex distance game. Surprisingly, we observe that non-signalling strategies provide a finer distinction for the new game compared to classical and quantum strategies since the parameter D is visible only in the non-signalling setting.
The optimal control problem for open quantum systems can be formulated as a time-dependent Lindbladian that is parameterized by a number of time-dependent control variables. Given an observable and an initial state, the goal is to tune the control variables so that the expected value of some observable with respect to the final state is maximized. In this paper, we present algorithms for solving this optimal control problem efficiently, i.e., having a poly-logarithmic dependency on the system dimension, which is exponentially faster than best-known classical algorithms. Our algorithms are hybrid, consisting of both quantum and classical components. The quantum procedure simulates time-dependent Lindblad evolution that drives the initial state to the final state, and it also provides access to the gradients of the objective function via quantum gradient estimation. The classical procedure uses the gradient information to update the control variables. At the technical level, we provide the first (to the best of our knowledge) simulation algorithm for time-dependent Lindbladians with an $\ell_1$-norm dependence. As an alternative, we also present a simulation algorithm in the interaction picture to improve the algorithm for the cases where the time-independent component of a Lindbladian dominates the time-dependent part. On the classical side, we heavily adapt the state-of-the-art classical optimization analysis to interface with the quantum part of our algorithms. Both the quantum simulation techniques and the classical optimization analyses might be of independent interest.
A fundamental property of quantum mechanics is that a single qubit can carry at most 1 bit of classical information. For an important class of quantum communication channels, known as entanglement-breaking, this limitation remains valid even if the sender and receiver share entangled particles before the start of the communication: for every entanglement-breaking channel, the rate at which classical messages can be reliably communicated cannot exceed 1 bit per transmitted qubit even with the assistance of quantum entanglement. But does this mean that, for the purpose of communicating classical messages, a noisy entanglement-breaking qubit channel can be replaced by a noisy bit channel? Here we answer the question in the negative. We introduce a game where a player (the sender) assists another player (the receiver) in finding a prize hidden into one of four possible boxes, while avoiding a bomb hidden in one of the three remaining boxes. In this game, the bomb cannot be avoided with certainty if the players communicate through a noisy bit channel. In contrast, the players can deterministically avoid the bomb and find the prize with a guaranteed 1/3 probability if they communicate through an entanglement-breaking qubit channel known as the universal NOT channel. We show that the features of the quantum strategy can be simulated with a noiseless bit channel, but this simulation requires the transmission to be assisted by shared randomness: without shared randomness, even the noiseless transmission of a three-level classical system cannot match the transmission of a single noisy qubit.
Trond I. Andersen, Nikita Astrakhantsev, Amir H. Karamlou, Julia Berndtsson, Johannes Motruk, Aaron Szasz, Jonathan A. Gross, Alexander Schuckert, Tom Westerhout, Yaxing Zhang, Ebrahim Forati, Dario Rossi, Bryce Kobrin, Agustin Di Paolo, Andrey R. Klots, Ilya Drozdov, Vladislav D. Kurilovich, Andre Petukhov, Lev B. Ioffe, Andreas Elben, et al (207) Understanding how interacting particles approach thermal equilibrium is a major challenge of quantum simulators. Unlocking the full potential of such systems toward this goal requires flexible initial state preparation, precise time evolution, and extensive probes for final state characterization. We present a quantum simulator comprising 69 superconducting qubits which supports both universal quantum gates and high-fidelity analog evolution, with performance beyond the reach of classical simulation in cross-entropy benchmarking experiments. Emulating a two-dimensional (2D) XY quantum magnet, we leverage a wide range of measurement techniques to study quantum states after ramps from an antiferromagnetic initial state. We observe signatures of the classical Kosterlitz-Thouless phase transition, as well as strong deviations from Kibble-Zurek scaling predictions attributed to the interplay between quantum and classical coarsening of the correlated domains. This interpretation is corroborated by injecting variable energy density into the initial state, which enables studying the effects of the eigenstate thermalization hypothesis (ETH) in targeted parts of the eigenspectrum. Finally, we digitally prepare the system in pairwise-entangled dimer states and image the transport of energy and vorticity during thermalization. These results establish the efficacy of superconducting analog-digital quantum processors for preparing states across many-body spectra and unveiling their thermalization dynamics.
We uncover emergent universality arising in the equilibration dynamics of multimode continuous-variable systems. Specifically, we study the ensemble of pure states supported on a small subsystem of a few modes, generated by Gaussian measurements on the remaining modes of a globally pure bosonic Gaussian state. We find that beginning from sufficiently complex global states, such as random Gaussian states and product squeezed states coupled via a deep array of linear optical elements, the induced ensemble attains a universal form, independent of the choice of measurement basis: it is composed of unsqueezed coherent states whose displacements are distributed normally and isotropically, with variance depending on only the particle-number density of the system. We further show that the emergence of such a universal form is consistent with a generalized maximum entropy principle, which endows the limiting ensemble, which we call the "Gaussian Scrooge distribution", with a special quantum information-theoretic property of having minimal accessible information. Our results represent a conceptual generalization of the recently introduced notion of "deep thermalization" in discrete-variable quantum many-body systems -- a novel form of equilibration going beyond thermalization of local observables -- to the realm of continuous-variable quantum systems. Moreover, it demonstrates how quantum information-theoretic perspectives can unveil new physical phenomena and principles in quantum dynamics and statistical mechanics.
Symmetry in mixed quantum states can manifest in two distinct forms: \textitstrong symmetry, where each individual pure state in the quantum ensemble is symmetric with the same charge, and \textitweak symmetry, which applies only to the entire ensemble. This paper explores a novel type of spontaneous symmetry breaking (SSB) where a strong symmetry is broken to a weak one. While the SSB of a weak symmetry is measured by the long-ranged two-point correlation function $\mathrm{Tr}(O_xO^{\dagger}_y\rho)$, the strong-to-weak SSB (SW-SSB) is measured by the fidelity $F(\rho, O_xO^{\dagger}_y\rho O_yO^{\dagger}_x)$, dubbed the \textitfidelity correlator. We prove that SW-SSB is a universal property of mixed-state quantum phases, in the sense that the phenomenon of SW-SSB is robust against symmetric low-depth local quantum channels. We also show that the symmetry breaking is "spontaneous " in the sense that the effect of a local symmetry-breaking measurement cannot be recovered locally. We argue that a thermal state at a nonzero temperature in the canonical ensemble (with fixed symmetry charge) should have spontaneously broken strong symmetry. Additionally, we study non-thermal scenarios where decoherence induces SW-SSB, leading to phase transitions described by classical statistical models with bond randomness. In particular, the SW-SSB transition of a decohered Ising model can be viewed as the "ungauged" version of the celebrated toric code decodability transition. We confirm that, in the decohered Ising model, the SW-SSB transition defined by the fidelity correlator is the only physical transition in terms of channel recoverability. We also comment on other (inequivalent) definitions of SW-SSB, through correlation functions with higher Rényi indices.
Learning an unknown quantum process is a central task for validation of the functioning of near-term devices. The task is generally hard, requiring exponentially many measurements if no prior assumptions are made on the process. However, an interesting feature of the classically-simulable Clifford group is that unknown Clifford operations may be efficiently determined from a black-box implementation. We extend this result to the important class of fermionic Gaussian operations. These operations have received much attention due to their close links to fermionic linear optics. We then introduce an infinite family of unitary gates, called the Matchgate Hierarchy, with a similar structure to the Clifford Hierarchy. We show that the Clifford Hierarchy is contained within the Matchgate Hierarchy and how operations at any level of the hierarchy can be efficiently learned.
In this short note we show that the ensemble $\{O \vert 0\rangle \langle 0 \vert O^\top \ \vert \ O \in \mathbb{O(d)}\}$, where $O$ is drawn from the Haar measure on $\mathbb{O}(d)$ cannot be distinguished from $t$ copies of a Haar random state unless $t = \Omega(\sqrt{d})$. Our proof has the benefit of exactly computing the trace distance, which scales as $\Theta(t^2/d)$ for $t = O(\sqrt{d})$, between the moments as well as being surprisingly short. Lastly, we show that twirling certain states with orthogonal matrices yields exact $t=3$ designs, yet the same cannot be true for $t>3$.
We construct a quantum oracle relative to which BQP = QCMA but quantum-computation-classical-communication (QCCC) key exchange, QCCC commitments, and two-round quantum key distribution exist. We also construct an oracle relative to which BQP = QMA, but quantum lightning (a stronger variant of quantum money) exists. This extends previous work by Kretschmer [Kretschmer, TQC22], which showed that there is a quantum oracle relative to which BQP = QMA but pseudorandom state generators (a quantum variant of pseudorandom generators) exist. We also show that QCCC key exchange, QCCC commitments, and two-round quantum key distribution can all be used to build one-way puzzles. One-way puzzles are a version of "quantum samplable" one-wayness and are an intermediate primitive between pseudorandom state generators and EFI pairs, the minimal quantum primitive. In particular, one-way puzzles cannot exist if BQP = PP. Our results together imply that aside from pseudorandom state generators, there is a large class of quantum cryptographic primitives which can exist even if BQP = QCMA, but are broken if BQP = PP. Furthermore, one-way puzzles are a minimal primitive for this class. We denote this class "CountCrypt".
Recent experimental progress in controlling open quantum systems enables the pursuit of mixed-state nonequilibrium quantum phases. We investigate whether open quantum systems hosting mixed-state symmetry-protected topological states as steady states retain this property under symmetric perturbations. Focusing on the decohered cluster state -- a mixed-state symmetry-protected topological state protected by a combined strong and weak symmetry -- we construct a parent Lindbladian that hosts it as a steady state. This Lindbladian can be mapped onto exactly solvable reaction-diffusion dynamics, even in the presence of certain perturbations, allowing us to solve the parent Lindbladian in detail and reveal previously-unknown steady states. Using both analytical and numerical methods, we find that typical symmetric perturbations cause strong-to-weak spontaneous symmetry breaking at arbitrarily small perturbations, destabilize the steady-state mixed-state symmetry-protected topological order. However, when perturbations introduce only weak symmetry defects, the steady-state mixed-state symmetry-protected topological order remains stable. Additionally, we construct a quantum channel which replicates the essential physics of the Lindbladian and can be efficiently simulated using only Clifford gates, Pauli measurements, and feedback.
Braneshop, and
the US National Science Foundation.
SciRate