Papers 2021

• A Rate-Distortion Perspective on Quantum State Redistribution

  Zahra Baghali Khanian, Andreas Winter

  arXiv:2112.11952 · December 22, 2021 · quant-ph · doi

  Abstract

  We consider a rate-distortion version of the quantum state redistribution task, where the error of the decoded state is judged via an additive distortion measure; it thus constitutes a quantum generalisation of the classical Wyner-Ziv problem. The quantum source is described by a tripartite pure state shared between Alice ($A$, encoder), Bob ($B$, decoder) and a reference ($R$). Both Alice and Bob are required to output a system ($\widetilde{A}$ and $\widetilde{B}$, respectively), and the distortion measure is encoded in an observable on $\widetilde{A}\widetilde{B}R$. It includes as special cases most quantum rate-distortion problems considered in the past, and in particular quantum data compression with the fidelity measured per copy; furthermore, it generalises the well-known state merging and quantum state redistribution tasks for a pure state source, with per-copy fidelity, and a variant recently considered by us, where the source is an ensemble of pure states [ZBK & AW, Proc. ISIT 2020, pp. 1858-1863 and ZBK, PhD thesis, UAB 2020, arXiv:2012.14143]. We derive a single-letter formula for the rate-distortion function of compression schemes assisted by free entanglement. A peculiarity of the formula is that in general it requires optimisation over an unbounded auxiliary register, so the rate-distortion function is not readily computable from our result, and there is a continuity issue at zero distortion. However, we show how to overcome these difficulties in certain situations.

• How to simulate quantum measurement without computing marginals

  Sergey Bravyi, David Gosset, Yinchen Liu

  arXiv:2112.08499 · December 15, 2021 · quant-ph · doi

  Abstract

  We describe and analyze algorithms for classically simulating measurement of an $n$-qubit quantum state $ψ$ in the standard basis, that is, sampling a bit string $x$ from the probability distribution $|\langle x|ψ\rangle|^2$. Our algorithms reduce the sampling task to computing poly$(n)$ amplitudes of $n$-qubit states; unlike previously known techniques they do not require computation of marginal probabilities. First we consider the case where $|ψ\rangle=U|0^n\rangle$ is the output state of an $m$-gate quantum circuit $U$. We propose an exact sampling algorithm which involves computing $O(m)$ amplitudes of $n$-qubit states generated by subcircuits of $U$ spanned by the first $t=1,2,\ldots,m$ gates. We show that our algorithm can significantly accelerate quantum circuit simulations based on tensor network contraction methods or low-rank stabilizer decompositions. As another striking consequence we obtain an efficient classical simulation algorithm for measurement-based quantum computation with the surface code resource state on any planar graph, generalizing a previous algorithm which was known to be efficient only under restrictive topological constraints on the ordering of single-qubit measurements. Second, we consider the case in which $ψ$ is the unique ground state of a local Hamiltonian with a spectral gap that is lower bounded by an inverse polynomial function of $n$. We prove that a simple Metropolis-Hastings Markov Chain mixes rapidly to the desired probability distribution provided that $ψ$ obeys a certain technical condition, which we show is satisfied for all sign-problem free Hamiltonians. This gives a sampling algorithm which involves computing $\mathrm{poly}(n)$ amplitudes of $ψ$.

• Linear-time generalized Hartree-Fock algorithm for quasi-one-dimensional systems

  Alex Meiburg, Bela Bauer

  arXiv:2112.02088 · December 3, 2021 · cond-mat.str-el

  Abstract

  In many approximate approaches to fermionic quantum many-body systems, such as Hartree-Fock and density functional theory, solving a system of non-interacting fermions coupled to some effective potential is the computational bottleneck. In this paper, we demonstrate that this crucial computational step can be accelerated using recently developed methods for Gaussian fermionic matrix product states (GFMPS). As an example, we study the generalized Hartree-Fock method, which unifies Hartree-Fock and self-consistent BCS theory, applied to Hubbard models with an inhomogeneous potential. We demonstrate that for quasi-one-dimensional systems with local interactions, our approach scales approximately linearly in the length of the system while yielding a similar accuracy to standard approaches that scale cubically in the system size.

• Measurement-driven navigation in many-body Hilbert space: Active-decision steering

  Yaroslav Herasymenko, Igor Gornyi, Yuval Gefen

  arXiv:2111.09306 · November 17, 2021 · quant-ph · PRX Quantum 4, 020347 (2023) · doi

  Abstract

  The challenge of preparing a system in a designated state spans diverse facets of quantum mechanics. To complete this task of steering quantum states, one can employ quantum control through a sequence of generalized measurements which direct the system towards the target state. In an active version of this protocol, the obtained measurement readouts are used to adjust the protocol on-the-go. This enables a sped-up performance relative to the passive version of the protocol, where no active adjustments are included. In this work, we consider such active measurement-driven steering as applied to the challenging case of many-body quantum systems. For helpful decision-making strategies, we offer Hilbert-space-orientation techniques, comparable to those used in navigation. The first one is to tie the active-decision protocol to the greedy accumulation of the cost function, such as the target state fidelity. We show the potential of a significant speedup, employing this greedy approach to a broad family of Matrix Product State targets. For system sizes considered here, an average value of the speedup factor $f$ across this family settles about $20$, for some targets even reaching a few thousands. We also identify a subclass of Matrix Product State targets, for which the value of $f$ increases with system size. In addition to the greedy approach, the second wayfinding technique is to map out the available measurement actions onto a Quantum State Machine. A decision-making protocol can be based on such a representation, using semiclassical heuristics. This State Machine-based approach can be applied to a more restricted set of targets, sometimes offering advantages over the cost function-based method. We give an example of a W-state preparation which is accelerated with this method by $f\simeq3.5$, outperforming the greedy protocol for this target.

• Approximate symmetries and quantum error correction

  Zi-Wen Liu, Sisi Zhou

  arXiv:2111.06355 · November 11, 2021 · quant-ph · npj Quantum Information (2023) 9:119 · doi

  Abstract

  Quantum error correction (QEC) is a key concept in quantum computation as well as many areas of physics. There are fundamental tensions between continuous symmetries and QEC. One vital situation is unfolded by the Eastin--Knill theorem, which forbids the existence of QEC codes that admit transversal continuous symmetry actions (transformations). Here, we systematically study the competition between continuous symmetries and QEC in a quantitative manner. We first define a series of meaningful measures of approximate symmetries motivated from different perspectives, and then establish a series of trade-off bounds between them and QEC accuracy utilizing multiple different methods. Remarkably, the results allow us to derive general quantitative limitations of transversally implementable logical gates, an important topic in fault-tolerant quantum computation. As concrete examples, we showcase two explicit types of quantum codes, obtained from quantum Reed--Muller codes and thermodynamic codes, respectively, that nearly saturate our bounds. Finally, we discuss several potential applications of our results in physics.

• Quantum error correction meets continuous symmetries: fundamental trade-offs and case studies

  Zi-Wen Liu, Sisi Zhou

  arXiv:2111.06360 · November 11, 2021 · quant-ph

  Abstract

  We systematically study the fundamental competition between quantum error correction (QEC) and continuous symmetries, two key notions in quantum information and physics, in a quantitative manner. Three meaningful measures of approximate symmetries in quantum channels and in particular QEC codes, respectively based on the violation of covariance conditions over the entire symmetry group or at a local point, and the violation of charge conservation, are introduced and studied. Each measure induces a corresponding characterization of approximately covariant codes. We explicate a host of different ideas and techniques that enable us to derive various forms of trade-off relations between the QEC inaccuracy and all symmetry violation measures. More specifically, we introduce two frameworks for understanding and establishing the trade-offs respectively based on the notions of charge fluctuation and gate implementation error, and employ methods including the Knill--Laflamme conditions as well as quantum metrology and quantum resource theory for the derivation. From the perspective of fault-tolerant quantum computing, our bounds on symmetry violation indicate limitations on the precision or density of transversally implementable logical gates for general QEC codes, refining the Eastin--Knill theorem. To exemplify nontrivial approximately covariant codes and understand the achievability of the above fundamental limits, we analyze the behaviors of two explicit types of codes: a parametrized extension of the thermodynamic code (which gives a construction of a code family that continuously interpolates between exact QEC and exact symmetry), and the quantum Reed--Muller codes. We show that both codes can saturate the scaling of the bounds for group-global covariance and charge conservation asymptotically, indicating the near-optimality of these bounds and codes.

• Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography

  Alex Meiburg

  arXiv:2111.03142 · November 4, 2021 · quant-ph

  Abstract

  Matrix permanents are hard to compute or even estimate in general. It had been previously suggested that the permanents of Positive Semidefinite (PSD) matrices may have efficient approximations. By relating PSD permanents to a task in quantum state tomography, we show that PSD permanents are NP-hard to approximate within a constant factor, and so admit no FPTAS (unless P=NP). We also establish that several natural tasks in quantum state tomography, even approximately, are NP-hard in the dimension of the Hilbert space. These state tomography tasks therefore remain hard even with only logarithmically few qubits.

• On the complexity of quantum partition functions

  Sergey Bravyi, Anirban Chowdhury, David Gosset, Pawel Wocjan

  arXiv:2110.15466 · October 29, 2021 · quant-ph · Nature Physics, 18 (11) 1367-1370 (2022) · doi

  Abstract

  The partition function and free energy of a quantum many-body system determine its physical properties in thermal equilibrium. Here we study the computational complexity of approximating these quantities for $n$-qubit local Hamiltonians. First, we report a classical algorithm with $\mathrm{poly}(n)$ runtime which approximates the free energy of a given $2$-local Hamiltonian provided that it satisfies a certain denseness condition. Our algorithm combines the variational characterization of the free energy and convex relaxation methods. It contributes to a body of work on efficient approximation algorithms for dense instances of optimization problems which are hard in the general case, and can be viewed as simultaneously extending existing algorithms for (a) the ground energy of dense $2$-local Hamiltonians, and (b) the free energy of dense classical Ising models. Secondly, we establish polynomial-time equivalence between the problem of approximating the free energy of local Hamiltonians and three other natural quantum approximate counting problems, including the problem of approximating the number of witness states accepted by a QMA verifier. These results suggest that simulation of quantum many-body systems in thermal equilibrium may precisely capture the complexity of a broad family of computational problems that has yet to be defined or characterized in terms of known complexity classes. Finally, we summarize state-of-the-art classical and quantum algorithms for approximating the free energy and show how to improve their runtime and memory footprint.

• T-count and T-depth of any multi-qubit unitary

  Vlad Gheorghiu, Michele Mosca, Priyanka Mukhopadhyay

  arXiv:2110.10292 · October 19, 2021 · quant-ph · doi

  Abstract

  While implementing a quantum algorithm it is crucial to reduce the quantum resources, in order to obtain the desired computational advantage. For most fault-tolerant quantum error-correcting codes the cost of implementing the non-Clifford gate is the highest among all the gates in a universal fault-tolerant gate set. In this paper we design provable algorithm to determine T-count of any $n$-qubit ($n\geq 1$) unitary $W$ of size $2^n\times 2^n$, over the Clifford+T gate set. The space and time complexity of our algorithm are $O\left(2^{2n}\right)$ and $O\left(2^{2n\mathcal{T}_ε(W)+4n}\right)$ respectively. $\mathcal{T}_ε(W)$ ($ε$-T-count) is the (minimum possible) T-count of an exactly implementable unitary $U$ i.e. $\mathcal{T}(U)$, such that $d(U,W)\leqε$ and $\mathcal{T}(U)\leq\mathcal{T}(U')$ where $U'$ is any exactly implementable unitary with $d(U',W)\leqε$. $d(.,.)$ is the global phase invariant distance. Our algorithm can also be used to determine the (minimum possible) T-depth of any multi-qubit unitary and the complexity has exponential dependence on $n$ and $ε$-T-depth. This is the first algorithm that gives T-count or T-depth of any multi-qubit ($n\geq 1$) unitary. For small enough $ε$, we can synthesize the T-count and T-depth-optimal circuits. Our results can be used to determine the minimum count (or depth) of non-Clifford gates required to implement any multi-qubit unitary with a universal gate set consisting of Clifford and non-Clifford gates like Clifford+CS, Clifford+V, etc. To the best of our knowledge, there were no such optimal-synthesis algorithm for arbitrary multi-qubit unitaries in any universal gate set.

• A degree preserving delta wye transformation with applications to 6-regular graphs and Feynman periods

  Shannon Jeffries, Karen Yeats

  arXiv:2110.07764 · October 14, 2021 · math.CO

  Abstract

  We investigate a degree preserving variant of the $Δ$-Y transformation which replaces a triangle with a new 6-valent vertex which has double edges to the vertices that had been in the triangle. This operation is relevant for understanding scalar Feynman integrals in 6 dimensions. We study the structure of equivalence classes under this operation and its inverse, with particular attention to when the equivalence classes are finite, when they contain simple 6-regular graphs, and when they contain doubled 3-regular graphs. The last of these, in particular, is relevant for the Feynman integral calculations and we make some observations linking the structure of these classes to the Feynman periods. Furthermore, we investigate properties of minimal graphs in these equivalence classes.

• Decoding the Entanglement Structure of Monitored Quantum Circuits

  Beni Yoshida

  arXiv:2109.08691 · September 17, 2021 · quant-ph

  Abstract

  Given an output wavefunction of a monitored quantum circuit consisting of both unitary gates and projective measurements, we ask whether two complementary subsystems are entangled or not. For Clifford circuits, we find that this question can be mapped to a certain classical error-correction problem where various entanglement measures can be explicitly computed from the recoverability. The dual classical code is constructed from spacetime patterns of out-of-time ordered correlation functions among local operators and measured Pauli operators in the past, suggesting that the volume-law entanglement in a monitored circuit emerges from quantum information scrambling, namely the growth of local operators. We also present a method of verifying quantum entanglement by providing a simple deterministic entanglement distillation algorithm, which can be interpreted as decoding of the dual classical code. Discussions on coding properties of a monitored Clifford circuit, including explicit constructions of logical and stabilizer operators, are also presented. Applications of our framework to various physical questions, including non-Clifford systems, are discussed as well. Namely, we argue that the entanglement structure of a monitored quantum circuit in the volume-law phase is largely independent of the initial states and past measurement outcomes except recent ones, due to the decoupling phenomena from scrambling dynamics, up to a certain polynomial length scale which can be identified as the code distance of the circuit. We also derive a general relation between the code distance and the sub-leading contribution to the volume-law entanglement entropy. Applications of these results to black hole physics are discussed as well.

• Finding $AdS^{5} \times S^{5}$ in 2+1 dimensional SCFT physics

  Mark Van Raamsdonk, Chris Waddell

  arXiv:2109.04479 · September 9, 2021 · hep-th · doi

  Abstract

  We study solutions of type IIB string theory dual to ${\cal N}=4$ supersymmetric Yang-Mills theory on half of $\mathbb{R}^{3,1}$ coupled to holographic three-dimensional superconformal field theories (SCFTs) at the edge of this half-space. The dual geometries are asymptotically $AdS^5 \times S^5$ with boundary geometry $\mathbb{R}^{2,1} \times \mathbb{R}^+$, with a geometrical end-of-the-world (ETW) brane cutting off the other half of the asymptotic region of the would-be Poincaré $AdS^5 \times S^5$. We show that by choosing the 3D SCFT appropriately, this ETW brane can be pushed arbitrarily far towards the missing asymptotic region, recovering the "missing" half of Poincaré $AdS^5 \times S^5$. We also show that there are 3D SCFTs whose dual includes a wedge of Poincaré $AdS^5 \times S^5$ with an angle arbitrarily close to $π$, with geometrical ETW branes on either side.

• Looking for (and not finding) a bulk brane

  Wyatt Reeves, Moshe Rozali, Petar Simidzija, James Sully, Christopher Waddell, David Wakeham

  arXiv:2108.10345 · August 23, 2021 · hep-th · doi

  Abstract

  When does a holographic CFT with a boundary added to it (a BCFT) also have a `good' holographic dual with a localized gravitating end-of-the-world brane? We argue that the answer to this question is almost never. By studying Lorentzian BCFT correlators, we characterize constraints imposed on a BCFT by the existence of a bulk causal structure. We argue that approximate `bulk brane' singularities place restrictive constraints on the spectrum of a BCFT that are not expected to be true generically. We discuss how similar constraints implied by bulk causality might apply in higher-dimensional holographic descriptions of BCFTs involving a degenerating internal space. We suggest (although do not prove) that even these higher-dimensional holographic duals are not generic.

• Quantum advantages for Pauli channel estimation

  Senrui Chen, Sisi Zhou, Alireza Seif, Liang Jiang

  arXiv:2108.08488 · August 19, 2021 · quant-ph · Phys. Rev. A 105, 032435 (2022) · doi

  Abstract

  We show that entangled measurements provide an exponential advantage in sample complexity for Pauli channel estimation, which is both a fundamental problem and a practically important subroutine for benchmarking near-term quantum devices. The specific task we consider is to simultaneously learn all the eigenvalues of an $n$-qubit Pauli channel to $\pm\varepsilon$ precision. We give an estimation protocol with an $n$-qubit ancilla that succeeds with high probability using only $O(n/\varepsilon^{2})$ copies of the Pauli channel, while prove that any ancilla-free protocol (possibly with adaptive control and channel concatenation) would need at least $Ω(2^{n/3})$ rounds of measurement. We further study the advantages provided by a small number of ancillas. For the case that a $k$-qubit ancilla ($k\le n$) is available, we obtain a sample complexity lower bound of $Ω(2^{(n-k)/3})$ for any non-concatenating protocol, and a stronger lower bound of $Ω(n2^{n-k})$ for any non-adaptive, non-concatenating protocol, which is shown to be tight. We also show how to apply the ancilla-assisted estimation protocol to a practical quantum benchmarking task in a noise-resilient and sample-efficient manner, given reasonable noise assumptions. Our results provide a practically-interesting example for quantum advantages in learning and also bring new insight for quantum benchmarking.

• Simulating gauge theories with variational quantum eigensolvers in superconducting microwave cavities

  Jinglei Zhang, Ryan Ferguson, Stefan Kühn, Jan F. Haase, C. M. Wilson, Karl Jansen, Christine A. Muschik

  arXiv:2108.08248 · August 18, 2021 · quant-ph · Quantum 7, 1148 (2023) · doi

  Abstract

  Quantum-enhanced computing methods are promising candidates to solve currently intractable problems. We consider here a variational quantum eigensolver (VQE), that delegates costly state preparations and measurements to quantum hardware, while classical optimization techniques guide the quantum hardware to create a desired target state. In this work, we propose a bosonic VQE using superconducting microwave cavities, overcoming the typical restriction of a small Hilbert space when the VQE is qubit based. The considered platform allows for strong nonlinearities between photon modes, which are highly customisable and can be tuned in situ, i.e. during running experiments. Our proposal hence allows for the realization of a wide range of bosonic ansatz states, and is therefore especially useful when simulating models involving degrees of freedom that cannot be simply mapped to qubits, such as gauge theories, that include components which require infinite-dimensional Hilbert spaces. We thus propose to experimentally apply this bosonic VQE to the U(1) Higgs model including a topological term, which in general introduces a sign problem in the model, making it intractable with conventional Monte Carlo methods.

• Recovery algorithms for Clifford Hayden-Preskill problem

  Beni Yoshida

  arXiv:2106.15628 · June 29, 2021 · quant-ph

  Abstract

  The Hayden-Preskill recovery problem has provided useful insights on physics of quantum black holes as well as dynamics in quantum many-body systems from the viewpoint of quantum error-correcting codes. While finding an efficient universal information recovery procedure seems challenging, some interesting classes of dynamical systems may admit efficient recovery algorithms. Here we present simple deterministic recovery algorithms for the Hayden-Preskill problem when its unitary dynamics is given by a Clifford operator. The algorithms utilize generalized Bell measurements and apply feedback operations based on the measurement result. The recovery fidelity and the necessary feedback operation can be found by analyzing the operator growth. These algorithms can also serve as a decoding strategy for entanglement-assisted quantum error-correcting codes (EAQECCs). We also present a version of recovery algorithms with local Pauli basis measurements, which can be viewed as a many-body generalization of quantum teleportation with fault-tolerance. A certain relation between out-of-time order correlation functions and discrete Wigner functions is also discussed, which may be of independent interest.

• Role of symmetry in quantum search via continuous-time quantum walk

  Yunkai Wang, Shengjun Wu

  arXiv:2106.08398 · June 15, 2021 · quant-ph · SPIN 11, 2140002 (2021) · doi

  Abstract

  For quantum search via the continuous-time quantum walk, the evolution of the whole system is usually limited in a small subspace. In this paper, we discuss how the symmetries of the graphs are related to the existence of such an invariant subspace, which also suggests a dimensionality reduction method based on group representation theory. We observe that in the one-dimensional subspace spanned by each desired basis state which assembles the identically evolving original basis states, we always get a trivial representation of the symmetry group. So we could find the desired basis by exploiting the projection operator of the trivial representation. Besides being technical guidance in this type of problem, this discussion also suggests that all the symmetries are used up in the invariant subspace and the asymmetric part of the Hamiltonian is very important for the purpose of quantum search.

• Improved upper bounds on the stabilizer rank of magic states

  Hammam Qassim, Hakop Pashayan, David Gosset

  arXiv:2106.07740 · June 14, 2021 · quant-ph · Quantum 5, 606 (2021) · doi

  Abstract

  In this work we improve the runtime of recent classical algorithms for strong simulation of quantum circuits composed of Clifford and T gates. The improvement is obtained by establishing a new upper bound on the stabilizer rank of $m$ copies of the magic state $|T\rangle=\sqrt{2}^{-1}(|0\rangle+e^{iπ/4}|1\rangle)$ in the limit of large $m$. In particular, we show that $|T\rangle^{\otimes m}$ can be exactly expressed as a superposition of at most $O(2^{αm})$ stabilizer states, where $α\leq 0.3963$, improving on the best previously known bound $α\leq 0.463$. This furnishes, via known techniques, a classical algorithm which approximates output probabilities of an $n$-qubit Clifford + T circuit $U$ with $m$ uses of the T gate to within a given inverse polynomial relative error using a runtime $\mathrm{poly}(n,m)2^{αm}$. We also provide improved upper bounds on the stabilizer rank of symmetric product states $|ψ\rangle^{\otimes m}$ more generally; as a consequence we obtain a strong simulation algorithm for circuits consisting of Clifford gates and $m$ instances of any (fixed) single-qubit $Z$-rotation gate with runtime $\text{poly}(n,m) 2^{m/2}$. We suggest a method to further improve the upper bounds by constructing linear codes with certain properties.

• Achieving fault tolerance on capped color codes with few ancillas

  Theerapat Tansuwannont, Debbie Leung

  arXiv:2106.02649 · June 4, 2021 · quant-ph · PRX Quantum 3, 030322 (2022) · doi

  Abstract

  Attaining fault tolerance while maintaining low overhead is one of the main challenges in a practical implementation of quantum circuits. One major technique that can overcome this problem is the flag technique, in which high-weight errors arising from a few faults can be detected by a few ancillas and distinguished using subsequent syndrome measurements. The technique can be further improved using the fact that for some families of codes, errors of any weight are logically equivalent if they have the same syndrome and weight parity, as previously shown in [Phys. Rev. A 104, 042410 (2021)]. In this work, we develop a notion of distinguishable fault set which captures both concepts of flags and weight parities, and extend the use of weight parities in error correction from [Phys. Rev. A 104, 042410 (2021)] to families of capped and recursive capped color codes. We also develop fault-tolerant protocols for error correction, measurement, state preparation, and logical T gate implementation via code switching, which are sufficient for performing fault-tolerant Clifford computation on a capped color code, and performing fault-tolerant universal quantum computation on a recursive capped color code. Our protocols for a capped or a recursive capped color code of any distance require only 2 ancillas, assuming that the ancillas can be reused. The concept of distinguishable fault set also leads to a generalization of the definitions of fault-tolerant gadgets proposed by Aliferis, Gottesman, and Preskill.

• Bulk private curves require large conditional mutual information

  Alex May

  arXiv:2105.08094 · May 17, 2021 · hep-th · doi

  Abstract

  We prove a theorem showing that the existence of "private" curves in the bulk of AdS implies two regions of the dual CFT share strong correlations. A private curve is a causal curve which avoids the entanglement wedge of a specified boundary region $\mathcal{U}$. The implied correlation is measured by the conditional mutual information $I(\mathcal{V}_1:\mathcal{V}_2\,|\,\mathcal{U})$, which is $O(1/G_N)$ when a private causal curve exists. The regions $\mathcal{V}_1$ and $\mathcal{V}_2$ are specified by the endpoints of the causal curve and the placement of the region $\mathcal{U}$. This gives a causal perspective on the conditional mutual information in AdS/CFT, analogous to the causal perspective on the mutual information given by earlier work on the connected wedge theorem. We give an information theoretic argument for our theorem, along with a bulk geometric proof. In the geometric perspective, the theorem follows from the maximin formula and entanglement wedge nesting. In the information theoretic approach, the theorem follows from resource requirements for sending private messages over a public quantum channel.

• Investigating a (3+1)D Topological $θ$-Term in the Hamiltonian Formulation of Lattice Gauge Theories for Quantum and Classical Simulations

  Angus Kan, Lena Funcke, Stefan Kühn, Luca Dellantonio, Jinglei Zhang, Jan F. Haase, Christine A. Muschik, Karl Jansen

  arXiv:2105.06019 · May 13, 2021 · hep-lat · Phys. Rev. D 104, 034504 (2021) · doi

  Abstract

  Quantum technologies offer the prospect to efficiently simulate sign-problem afflicted regimes in lattice field theory, such as the presence of topological terms, chemical potentials, and out-of-equilibrium dynamics. In this work, we derive the (3+1)D topological $θ$-term for Abelian and non-Abelian lattice gauge theories in the Hamiltonian formulation, paving the way towards Hamiltonian-based simulations of such terms on quantum and classical computers. We further study numerically the zero-temperature phase structure of a (3+1)D U(1) lattice gauge theory with the $θ$-term via exact diagonalization for a single periodic cube. In the strong coupling regime, our results suggest the occurrence of a phase transition at constant values of $θ$, as indicated by an avoided level-crossing and abrupt changes in the plaquette expectation value, the electric energy density, and the topological charge density. These results could in principle be cross-checked by the recently developed (3+1)D tensor network methods and quantum simulations, once sufficient resources become available.

• Improved approximation algorithms for bounded-degree local Hamiltonians

  Anurag Anshu, David Gosset, Karen J. Morenz Korol, Mehdi Soleimanifar

  arXiv:2105.01193 · May 3, 2021 · quant-ph · doi

  Abstract

  We consider the task of approximating the ground state energy of two-local quantum Hamiltonians on bounded-degree graphs. Most existing algorithms optimize the energy over the set of product states. Here we describe a family of shallow quantum circuits that can be used to improve the approximation ratio achieved by a given product state. The algorithm takes as input an $n$-qubit product state $|v\rangle$ with mean energy $e_0=\langle v|H|v\rangle$ and variance $\mathrm{Var}=\langle v|(H-e_0)^2|v\rangle$, and outputs a state with an energy that is lower than $e_0$ by an amount proportional to $\mathrm{Var}^2/n$. In a typical case, we have $\mathrm{Var}=Ω(n)$ and the energy improvement is proportional to the number of edges in the graph. When applied to an initial random product state, we recover and generalize the performance guarantees of known algorithms for bounded-occurrence classical constraint satisfaction problems. We extend our results to $k$-local Hamiltonians and entangled initial states.

• Soft thermodynamics of gravitational shock wave

  Shuwei Liu, Beni Yoshida

  arXiv:2104.13377 · April 27, 2021 · hep-th · doi

  Abstract

  The gravitational shock waves have provided crucial insights into entanglement structures of black holes in the AdS/CFT correspondence. Recent progress on the soft hair physics suggests that these developments from holography may also be applicable to geometries beyond negatively curved spacetime. In this work, we derive a remarkably simple thermodynamic relation which relates the gravitational shock wave to a microscopic area deformation. Our treatment is based on the covariant phase space formalism and is applicable to any Killing horizon in generic static spacetime which is governed by arbitrary covariant theory of gravity. The central idea is to probe the gravitational shock wave, which shifts the horizon in the $u$ direction, by the Noether charge constructed from a vector field which shifts the horizon in the $v$ direction. As an application, we illustrate its use for the Gauss-Bonnet gravity. We also derive a simplified form of the gravitational scattering unitary matrix and show that its leading-order contribution is nothing but the exponential of the horizon area: $\mathcal{U}=\exp(i \text{Area})$.

• Negative energy enhancement in layered holographic conformal field theories

  Alex May, Petar Simidzija, Mark Van Raamsdonk

  arXiv:2103.14046 · March 25, 2021 · hep-th · doi

  Abstract

  Using a holographic model, we study quantum field theories with a layer of one CFT surrounded by another CFT, on either a periodic or an infinite direction. We study the vacuum energy density in each CFT as a function of the central charges, the thickness of the layer(s), and the properties of the interfaces between the CFTs. The dual spacetimes in the holographic model include two regions separated by a dynamical interface with some tension. For two or more spatial dimensions, we find that a layer of CFT with more degrees of freedom than the surrounding one can have an anomalously large negative vacuum energy density for certain types of interfaces. The negative energy density (or null-energy density in the direction perpendicular to the interface) becomes arbitrarily large for fixed layer width when the tension of the bulk interface approaches a lower critical value. We argue that in cases where we have large negative energy density, we also have an anomalously high transition temperature to the high-temperature thermal state.

• Asymptotically Consistent Measures of General Quantum Resources: Discord, Non-Markovianity, and Non-Gaussianity

  Kohdai Kuroiwa, Hayata Yamasaki

  arXiv:2103.05665 · March 9, 2021 · quant-ph · Phys. Rev. A 104, L020401 (2021) · doi

  Abstract

  Quantum resource theories provide a unified framework to quantitatively analyze inherent quantum properties as resources for quantum information processing. So as to investigate the best way for quantifying resources, desirable axioms for resource quantification have been extensively studied through axiomatic approaches. However, a conventional way of resource quantification by resource measures with such desired axioms may contradict rates of asymptotic transformation between resourceful quantum states due to an approximation in the transformation. In this paper, we establish an alternative axiom, asymptotic consistency of resource measures, and we investigate asymptotically consistent resource measures, which quantify resources without contradicting the rates of the asymptotic resource transformation. We prove that relative entropic measures are consistent with the rates for a broad class of resources, i.e., all convex finite-dimensional resources, e.g., entanglement, coherence, and magic, and even some nonconvex or infinite-dimensional resources such as quantum discord, non-Markovianity, and non-Gaussianity. These results show that consistent resource measures are widely applicable to the quantitative analysis of various inherent quantum-mechanical properties.

• An area law for 2D frustration-free spin systems

  Anurag Anshu, Itai Arad, David Gosset

  arXiv:2103.02492 · March 3, 2021 · quant-ph · Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022) · doi

  Abstract

  We prove that the entanglement entropy of the ground state of a locally gapped frustration-free 2D lattice spin system satisfies an area law with respect to a vertical bipartition of the lattice into left and right regions. We first establish that the ground state projector of any locally gapped frustration-free 1D spin system can be approximated to within error $ε$ by a degree $O(\sqrt{n\log(ε^{-1})})$ multivariate polynomial in the interaction terms of the Hamiltonian. This generalizes the optimal bound on the approximate degree of the boolean AND function, which corresponds to the special case of commuting Hamiltonian terms. For 2D spin systems we then construct an approximate ground state projector (AGSP) that employs the optimal 1D approximation in the vicinity of the boundary of the bipartition of interest. This AGSP has sufficiently low entanglement and error to establish the area law using a known technique.

• SU(2) hadrons on a quantum computer

  Yasar Atas, Jinglei Zhang, Randy Lewis, Amin Jahanpour, Jan F. Haase, Christine A. Muschik

  arXiv:2102.08920 · February 17, 2021 · quant-ph · Nature Communications 12, 6499 (2021) · doi

  Abstract

  We realize, for the first time, a non-Abelian gauge theory with both gauge and matter fields on a quantum computer. This enables the observation of hadrons and the calculation of their associated masses. The SU(2) gauge group considered here represents an important first step towards ultimately studying quantum chromodynamics, the theory that describes the properties of protons, neutrons and other hadrons. Quantum computers are able to create important new opportunities for ongoing essential research on gauge theories by providing simulations that are unattainable on classical computers. Our calculations on an IBM superconducting platform utilize a variational quantum eigensolver to study both meson and baryon states, hadrons which have never been seen in a non-Abelian simulation on a quantum computer. We develop a resource-efficient approach that not only allows the implementation of a full SU(2) gauge theory on present-day quantum hardware, but further lays out the premises for future quantum simulations that will address currently unanswered questions in particle and nuclear physics.

• Classical algorithms for Forrelation

  Sergey Bravyi, David Gosset, Daniel Grier, Luke Schaeffer

  arXiv:2102.06963 · February 13, 2021 · quant-ph

  Abstract

  We study the forrelation problem: given a pair of $n$-bit Boolean functions $f$ and $g$, estimate the correlation between $f$ and the Fourier transform of $g$. This problem is known to provide the largest possible quantum speedup in terms of its query complexity and achieves the landmark oracle separation between the complexity class BQP and the Polynomial Hierarchy. Our first result is a classical algorithm for the forrelation problem which has runtime $O(n2^{n/2})$. This is a nearly quadratic improvement over the best previously known algorithm. Secondly, we show that quantum query algorithm that makes $t$ queries to an $n$-bit oracle can be simulated by classical query algorithm making only $O(2^{n(1-1/2t)})$ queries. This fixes a gap in the literature arising from a recently discovered critical error in a previous proof; it matches recently established lower bounds (up to $poly(n,t))$ factors) and thus characterizes the maximal separation in query complexity between quantum and classical algorithms. Finally, we introduce a graph-based forrelation problem where $n$ binary variables live at vertices of some fixed graph and the functions $f,g$ are products of terms describing interactions between nearest-neighbor variables. We show that the graph-based forrelation problem can be solved on a classical computer in time $O(n)$ for any bipartite graph, any planar graph, or, more generally, any graph which can be partitioned into two subgraphs of constant treewidth. The graph-based forrelation is simply related to the variational energy achieved by the Quantum Approximate Optimization Algorithm (QAOA) with two entangling layers and Ising-type cost functions. By exploiting the connection between QAOA and the graph-based forrelation we were able to simulate the recently proposed Recursive QAOA with two entangling layers and $225$ qubits on a laptop computer.

• Quantum tasks require islands on the brane

  Alex May, David Wakeham

  arXiv:2102.01810 · February 3, 2021 · hep-th · doi

  Abstract

  In recent work, it was argued that quantum computations with inputs and outputs distributed in spacetime, or quantum tasks, impose constraints on entanglement in holographic theories. The resulting constraint was named the connected wedge theorem and can verified by a direct bulk proof using focusing arguments in general relativity. In this article we extend this work to the context of AdS/BCFT, where an end-of-the-world brane is present in the bulk. By considering quantum tasks which exploit information localized to the brane, we find a new connected wedge theorem. We apply this theorem to brane models of black holes, where it relates the formation of islands in the Ryu-Takayanagi formula to causal features of the ambient spacetime. In particular, we find that if the black hole interior is causally connected to the radiation system through the ambient spacetime, then an island forms. For constant tension branes in pure AdS the converse also holds.

• Many-body quantum teleportation via operator spreading in the traversable wormhole protocol

  Thomas Schuster, Bryce Kobrin, Ping Gao, Iris Cong, Emil T. Khabiboulline, Norbert M. Linke, Mikhail D. Lukin, Christopher Monroe, Beni Yoshida, Norman Y. Yao

  arXiv:2102.00010 · January 29, 2021 · quant-ph · Physical Review X 12, 031013 (2022) · doi

  Abstract

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

• Holographic quantum tasks with input and output regions

  Alex May

  arXiv:2101.08855 · January 21, 2021 · hep-th · doi

  Abstract

  Quantum tasks are quantum computations with inputs and outputs occurring at specified spacetime locations. Considering such tasks in the context of AdS/CFT has led to novel constraints relating bulk geometry and boundary entanglement. In this article we consider tasks where inputs and outputs are encoded into extended spacetime regions, rather than the points previously considered. We show that this leads to stronger constraints than have been derived in the point based setting. In particular we improve the connected wedge theorem, appearing earlier in 1912.05649, by finding a larger bulk region whose existence implies large boundary correlation. As well, we show how considering extended input and output regions leads to non-trivial statements in Poincaré-AdS$_{2+1}$, a setting where the point-based connected wedge theorem is always trivial.

• Quantum Constraint Problems can be complete for $\mathsf{BQP}$, $\mathsf{QCMA}$, and more

  Alex Meiburg

  arXiv:2101.08381 · January 21, 2021 · quant-ph

  Abstract

  A quantum constraint problem is a frustration-free Hamiltonian problem: given a collection of local operators, is there a state that is in the ground state of each operator simultaneously? It has previously been shown that these problems can be in P, NP-complete, MA-complete, or QMA_1-complete, but this list has not been shown to be exhaustive. We present three quantum constraint problems, that are (1) BQP_1-complete (also known as coRQP), (2) QCMA_1-complete and (3) coRP-complete. This provides the first natural complete problem for BQP_1. We also show that all quantum constraint problems can be realized on qubits, a trait not shared with classical constraint problems. These results suggest a significant diversity of complexity classes present in quantum constraint problems.

• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits

  Vlad Gheorghiu, Michele Mosca, Priyanka Mukhopadhyay

  arXiv:2101.03142 · January 8, 2021 · quant-ph · doi

  Abstract

  We investigate the problem of synthesizing T-depth optimal quantum circuits over the Clifford+T gate set. First we construct a special subset of T-depth 1 unitaries, such that it is possible to express the T-depth-optimal decomposition of any unitary as product of unitaries from this subset and a Clifford (up to global phase). The cardinality of this subset is at most $n\cdot 2^{5.6n}$. We use nested meet-in-the-middle (MITM) technique to develop algorithms for synthesizing provably \emph{depth-optimal} and \emph{T-depth-optimal} circuits for exactly implementable unitaries. Specifically, for synthesizing T-depth-optimal circuits, we get an algorithm with space and time complexity $O\left(\left(4^{n^2}\right)^{\lceil d/c\rceil}\right)$ and $O\left(\left(4^{n^2}\right)^{(c-1)\lceil d/c\rceil}\right)$ respectively, where $d$ is the minimum T-depth and $c\geq 2$ is a constant. This is much better than the complexity of the algorithm by Amy et al.(2013), the previous best with a complexity $O\left(\left(3^n\cdot 2^{kn^2}\right)^{\lceil \frac{d}{2}\rceil}\cdot 2^{kn^2}\right)$, where $k>2.5$ is a constant. We design an even more efficient algorithm for synthesizing T-depth-optimal circuits. The claimed efficiency and optimality depends on some conjectures, which have been inspired from the work of Mosca and Mukhopadhyay (2020). To the best of our knowledge, the conjectures are not related to the previous work. Our algorithm has space and time complexity $poly(n,2^{5.6n},d)$ (or $poly(n^{\log n},2^{5.6n},d)$ under some weaker assumptions).