Search

Quantum computers are expected to break modern public key cryptography owing to Shor's algorithm. As a result, these cryptosystems need to be replaced by quantum-resistant algorithms, also known as post-quantum cryptography (PQC) algorithms. The PQC research field has flourished over the past two decades, leading to the creation of a large variety of algorithms that are expected to be resistant to quantum attacks. These PQC algorithms are being selected and standardized by several standardization bodies. However, even with the guidance from these important efforts, the danger is not gone: there are billions of old and new devices that need to transition to the PQC suite of algorithms, leading to a multidecade transition process that has to account for aspects such as security, algorithm performance, ease of secure implementation, compliance and more. Here we present an organizational perspective of the PQC transition. We discuss transition timelines, leading strategies to protect systems against quantum attacks, and approaches for combining pre-quantum cryptography with PQC to minimize transition risks. We suggest standards to start experimenting with now and provide a series of other recommendations to allow organizations to achieve a smooth and timely PQC transition.

We present a quantum kernel method for high-dimensional data analysis using Google's universal quantum processor, Sycamore. This method is successfully applied to the cosmological benchmark of supernova classification using real spectral features with no dimensionality reduction and without vanishing kernel elements. Instead of using a synthetic dataset of low dimension or pre-processing the data with a classical machine learning algorithm to reduce the data dimension, this experiment demonstrates that machine learning with real, high dimensional data is possible using a quantum processor; but it requires careful attention to shot statistics and mean kernel element size when constructing a circuit ansatz. Our experiment utilizes 17 qubits to classify 67 dimensional data - significantly higher dimensionality than the largest prior quantum kernel experiments - resulting in classification accuracy that is competitive with noiseless simulation and comparable classical techniques., 20 pages, 12 figures

The quantum approximate optimization algorithm (QAOA) is widely seen as a possible usage of noisy intermediate-scale quantum (NISQ) devices. We analyze the algorithm as a bang-bang protocol with fixed total time and a randomized greedy optimization scheme. We investigate the performance of bang-bang QAOA on MAX-2-SAT, finding the appearance of phase transitions with respect to the total time. As the total time increases, the optimal bang-bang protocol experiences a number of jumps and plateaus in performance, which match up with an increasing number of switches in the standard QAOA formulation. At large times, it becomes more difficult to find a globally optimal bang-bang protocol and performances suffer. We also investigate the effects of changing the initial conditions of the randomized optimization algorithm and see that better local optima can be found by using an adiabatic initialization., Open source code of this paper is available: github.com/google-research/google-research/tree/master/bangbang_qaoa

The Quantum Approximate Optimization Algorithm (QAOA) is a standard method for combinatorial optimization with a gate-based quantum computer. The QAOA consists of a particular ansatz for the quantum circuit architecture, together with a prescription for choosing the variational parameters of the circuit. We propose modifications to both. First, we define the Gibbs objective function and show that it is superior to the energy expectation value for use as an objective function in tuning the variational parameters. Second, we describe an Ansatz Architecture Search (AAS) algorithm for searching the discrete space of quantum circuit architectures near the QAOA to find a better ansatz. Applying these modifications for a complete graph Ising model results in a $244.7\%$ median relative improvement in the probability of finding a low-energy state while using $33.3\%$ fewer two-qubit gates. For Ising models on a 2d grid we similarly find $44.4\%$ median improvement in the probability with a $20.8\%$ reduction in the number of two-qubit gates. This opens a new research field of quantum circuit architecture design for quantum optimization algorithms.

We study the consequences of Entanglement Wedge Nesting for CFTs with holographic duals. The CFT is formulated on an arbitrary curved background, and we include the effects of curvature-squared couplings in the bulk. In this setup we find necessary and sufficient conditions for Entanglement Wedge Nesting to imply the Quantum Null Energy Condition in $d\leq 5$, extending its earlier holographic proofs. We also show that the Quantum Focusing Conjecture yields the Quantum Null Energy Condition as its nongravitational limit under these same conditions., 20+12 pages, 1 figure

We show that the bulk region reconstructable from a given boundary subregion --- which we term the reconstruction wedge --- can be much smaller than the entanglement wedge even when backreaction is small. We find arbitrarily large separations between the reconstruction and entanglement wedges in near-vacuum states for regions close to an entanglement phase transition, and for more general regions in states with large energy (but very low energy density). Our examples also illustrate situations for which the quantum extremal surface is macroscopically different from the Ryu-Takayanagi surface., Comment: 7 pages, 4 figures

We compute the local second variation of the von Neumann entropy of a region in theories with a gravity dual. For null variations our formula says that the diagonal part of the quantum null energy condition (QNEC) is saturated in every state, thus providing an equivalence between energy and entropy. We prove that the formula holds at leading order in 1/N and further argue that it will not be affected at higher orders. We conjecture that the QNEC is saturated in all interacting theories. We also discuss the special case of free theories, and the implications of our formula for the averaged null energy condition, quantum focusing conjecture (QFC), and gravitational equations of motion. We show that the leading-order gravitational equations of motion, Einstein’s equations, are equivalent to the leading-order saturation of the QFC for Planck-width deformations.

The vacuum modular Hamiltonian $K$ of the Rindler wedge in any relativistic quantum field theory is given by the boost generator. Here we investigate the modular Hamiltoninan for more general half-spaces which are bounded by an arbitrary smooth cut of a null plane. We derive a formula for the second derivative of the modular Hamiltonian with respect to the coordinates of the cut which schematically reads $K" = T_{vv}$. This formula can be integrated twice to obtain a simple expression for the modular Hamiltonian. The result naturally generalizes the standard expression for the Rindler modular Hamiltonian to this larger class of regions. Our primary assumptions are the quantum null energy condition --- an inequality between the second derivative of the von Neumann entropy of a region and the stress tensor --- and its saturation in the vacuum for these regions. We discuss the validity of these assumptions in free theories and holographic theories to all orders in $1/N$., Comment: 6 pages, 1 figure

We study the evolution of the universal area law of entanglement entropy when the Hamiltonian of the system undergoes a time dependent perturbation. In particular, we derive a general formula for the time dependent first order correction to the area law under the assumption that the field theory resides in a vacuum state when a small time-dependent perturbation of a relevant coupling constant is turned on. Using this formula, we carry out explicit calculations in free field theories deformed by a time dependent mass, whereas for a generic QFT we show that the time dependent first order correction is governed by the spectral function defining the two-point correlation function of the trace of the energy-momentum tensor. We also carry out holographic calculations based on the HRT proposal and find qualitative and, in certain cases, quantitative agreement with the field theory calculations., Comment: 26 pages, one figure. v2: published version

We propose a universal inequality that unifies the Bousso bound with the classical focussing theorem. Given a surface $\sigma$ that need not lie on a horizon, we define a finite generalized entropy $S_\text{gen}$ as the area of $\sigma$ in Planck units, plus the von Neumann entropy of its exterior. Given a null congruence $N$ orthogonal to $\sigma$, the rate of change of $S_\text{gen}$ per unit area defines a quantum expansion. We conjecture that the quantum expansion cannot increase along $N$. This extends the notion of universal focussing to cases where quantum matter may violate the null energy condition. Integrating the conjecture yields a precise version of the Strominger-Thompson Quantum Bousso Bound. Applied to locally parallel light-rays, the conjecture implies a Quantum Null Energy Condition: a lower bound on the stress tensor in terms of the second derivative of the von Neumann entropy. We sketch a proof of this novel relation in quantum field theory., Comment: 45 pages, 6 figures

We prove the Quantum Null Energy Condition (QNEC), a lower bound on the stress tensor in terms of the second variation in a null direction of the entropy of a region. The QNEC arose previously as a consequence of the Quantum Focussing Conjecture, a proposal about quantum gravity. The QNEC itself does not involve gravity, so a proof within quantum field theory is possible. Our proof is somewhat nontrivial, suggesting that there may be alternative formulations of quantum field theory that make the QNEC more manifest. Our proof applies to free and superrenormalizable bosonic field theories, and to any points that lie on stationary null surfaces. An example is Minkowski space, where any point $p$ and null vector $k^a$ define a null plane $N$ (a Rindler horizon). Given any codimension-2 surface $\Sigma$ that contains $p$ and lies on $N$, one can consider the von Neumann entropy $S_\text{out}$ of the quantum state restricted to one side of $\Sigma$. A second variation $S_\text{out}^{\prime\prime}$ can be defined by deforming $\Sigma$ along $N$, in a small neighborhood of $p$ with area $\cal A$. The QNEC states that $\langle T_{kk}(p) \rangle \ge \frac{\hbar}{2\pi} \lim_{{\cal A}\to 0}S_\text{out}^{ \prime\prime}/{\cal A}$., Comment: 32 pages, 3 figures. v2: references and minor typos

We use holography to prove the Quantum Null Energy Condition (QNEC) at leading order in large-$N$ for CFTs and relevant deformations of CFTs in Minkowski space which have Einstein gravity duals. Given any codimension-2 surface $\Sigma$ which is locally stationary under a null deformation in the direction $k$ at the point $p$, the QNEC is a lower bound on the energy-momentum tensor at $p$ in terms of the second variation of the entropy to one side of $\Sigma$: $\langle T_{kk}\rangle \geq S"/2\pi \sqrt{h}$. In a CFT, conformal transformations of this inequality give results which apply when $\Sigma$ is not locally stationary. The QNEC was proven previously for free theories, and taken together with our result this provides strong evidence that the QNEC is a true statement about quantum field theory in general., Comment: 25 pages, 2 figures. v2: references added, minor notation corrections, minor clarifications

We use holographic techniques to calculate the first thermal correction to the entanglement entropy of a cap-like region of a CFT defined on a sphere, successfully reproducing the field theory result. Since this is an order-one correction to the entropy in the large-$N$ expansion, quantum corrections to the holographic entanglement entropy formula are essential. The bulk calculation is made tractable using the same technical machinery recently used to derive the linearized Einstein equations in the bulk from the first law of entanglement entropy in the CFT., 12 pages, 1 figure

We derive a generalization of the Second Law of Thermodynamics that uses Bayesian updates to explicitly incorporate the effects of a measurement of a system at some point in its evolution. By allowing an experimenter's knowledge to be updated by the measurement process, this formulation resolves a tension between the fact that the entropy of a statistical system can sometimes fluctuate downward and the information-theoretic idea that knowledge of a stochastically-evolving system degrades over time. The Bayesian Second Law can be written as $\Delta H(\rho_m, \rho) + \langle \mathcal{Q}\rangle_{F|m}\geq 0$, where $\Delta H(\rho_m, \rho)$ is the change in the cross entropy between the original phase-space probability distribution $\rho$ and the measurement-updated distribution $\rho_m$, and $\langle \mathcal{Q}\rangle_{F|m}$ is the expectation value of a generalized heat flow out of the system. We also derive refined versions of the Second Law that bound the entropy increase from below by a non-negative number, as well as Bayesian versions of the Jarzynski equality. We demonstrate the formalism using simple analytical and numerical examples., Comment: 40 pages. Additional information and animations at http://preposterousuniverse.com/research/bsl/

We study the time dependence of the entanglement entropy of disjoint intervals following a global quantum quench in (1+1)-dimensional CFTs at large-$c$ with a sparse spectrum. The result agrees with a holographic calculation but differs from the free field theory answer. In particular, a simple model of free quasiparticle propagation is not adequate for CFTs with a holographic dual. We elaborate on the entanglement tsunami proposal of Liu and Suh and show how it can be used to reproduce the holographic answer., 20 pages and 6 figures. v3: added references

The question is raised whether the sum of the k × k principal minors of the titled matrix is a polynomial (in t ) with positive coefficients, when A and B are positive definite. This would generalize a conjecture made by Bessis–Moussa–Villani, as stated by E.H. Lieb and R. Seiringer [Equivalent forms of the Bessis–Moussa–Villani conjecture, J. Stat. Phys. 115 (2004) 185–190]. We give a variety of evidence for this further question, some of which is new.

Effective field theory provides a perturbative framework to study the evolution of cosmological large-scale structure. We investigate the underpinnings of this approach, and suggest new ways to compute correlation functions of cosmological observables. We find that, in contrast with quantum field theory, the appropriate effective theory of classical cosmological perturbations involves interactions that are nonlocal in time. We describe an alternative to the usual approach of smoothing the perturbations, based on a path-integral formulation of the renormalization group equations. This technique allows for improved handling of short-distance modes that are perturbatively generated by long-distance interactions., submitted to Phys. Rev. D; corrected typo

Black holes emit high energy particles which induce a finite density potential for any scalar field $\phi$ coupling to the emitted quanta. Due to energetic considerations, $\phi$ evolves locally to minimize the effective masses of the outgoing states. In theories where $\phi$ resides at a metastable minimum, this effect can drive $\phi$ over its potential barrier and classically catalyze the decay of the vacuum. Because this is not a tunneling process, the decay rate is not exponentially suppressed and a single black hole in our past light cone may be sufficient to activate the decay. Moreover, decaying black holes radiate at ever higher temperatures, so they eventually probe the full spectrum of particles coupling to $\phi$. We present a detailed analysis of vacuum decay catalyzed by a single particle, as well as by a black hole. The former is possible provided large couplings or a weak potential barrier. In contrast, the latter occurs much more easily and places new stringent limits on theories with hierarchical spectra. Finally, we comment on how these constraints apply to the standard model and its extensions, e.g. metastable supersymmetry breaking., Comment: 24 pages, 4 figures; v2: minor revisions for publication

We study entanglement in thermofield double states of strongly coupled CFTs by analyzing two-sided Reissner-Nordstrom solutions in AdS. The central object of study is the mutual information between a pair of regions, one on each asymptotic boundary of the black hole. For large regions the mutual information is positive and for small ones it vanishes; we compute the critical length scale, which goes to infinity for extremal black holes, of the transition. We also generalize the butterfly effect of Shenker and Stanford to a wide class of charged black holes, showing that mutual information is disrupted upon perturbing the system and waiting for a time of order $\log E/\delta E$ in units of the temperature. We conjecture that the parametric form of this timescale is universal., Comment: 20 pages, 3 figures; v2: references added

In Lorentzian AdS/CFT there exists a mapping between local bulk operators and nonlocal CFT operators. In global AdS this mapping can be found through use of bulk equations of motion and allows the nonlocal CFT operator to be expressed as a local operator smeared over a range of positions and times. We argue that such a construction is not possible if there are bulk normal modes with exponentially small near boundary imprint. We show that the AdS-Schwarzschild background is such a case, with the horizon introducing modes with angular momentum much larger than frequency, causing them to be trapped by the centrifugal barrier. More generally, we argue that any barrier in the radial effective potential which prevents null geodesics from reaching the boundary will lead to modes with vanishingly small near boundary imprint, thereby obstructing the existence of a smearing function. While one may have thought the bulk-boundary dictionary for low curvature regions, such as the exterior of a black hole, should be as in empty AdS, our results demonstrate otherwise., Comment: 25 pages, published version

One may ask whether the CFT restricted to a subset b of the AdS boundary has a well-defined dual restricted to a subset H(b) of the bulk geometry. The Poincare patch is an example, but more general choices of b can be considered. We propose a geometric construction of H. We argue that H should contain the set C of causal curves with both endpoints on b. Yet H should not reach so far from the boundary that the CFT has insufficient degrees of freedom to describe it. This can be guaranteed by constructing a superset of H from light-sheets off boundary slices and invoking the covariant entropy bound in the bulk. The simplest covariant choice is L, the intersection of L^+ and L^-, where L^+ (L^-) is the union of all future-directed (past-directed) light-sheets. We prove that C=L, so the holographic domain is completely determined by our assumptions: H=C=L. In situations where local bulk operators can be constructed on b, H is closely related to the set of bulk points where this construction remains unambiguous under modifications of the CFT Hamiltonian outside of b. Our construction leads to a covariant geometric RG flow. We comment on the description of black hole interiors and cosmological regions via AdS/CFT., Comment: 29 pages, 12 figures. published version

We investigate the nature of the AdS/CFT duality between a subregion of the bulk and its boundary. In global AdS/CFT in the classical G_N=0 limit, the duality reduces to a boundary value problem that can be solved by restricting to one-point functions of local operators in the CFT. We show that the solution of this boundary value problem depends continuously on the CFT data. In contrast, the AdS-Rindler subregion cannot be continuously reconstructed from local CFT data restricted to the associated boundary region. Motivated by related results in the mathematics literature, we posit that a continuous bulk reconstruction is only possible when every null geodesic in a given bulk subregion has an endpoint on the associated boundary subregion. This suggests that a subregion duality for AdS-Rindler, if it exists, must involve nonlocal CFT operators in an essential way., Comment: 28 pages, 6 figures; v2: final version for PRD, minor edits and reference added

We show that the geometry of cutoffs on eternal inflation strongly constrains predictions for the timescales of vacuum domination, curvature domination, and observation. We consider three measure proposals: the causal patch, the fat geodesic, and the apparent horizon cutoff, which is introduced here for the first time. We impose neither anthropic requirements nor restrictions on landscape vacua. For vacua with positive cosmological constant, all three measures predict the double coincidence that most observers live at the onset of vacuum domination and just before the onset of curvature domination. The hierarchy between the Planck scale and the cosmological constant is related to the number of vacua in the landscape. These results require only mild assumptions about the distribution of vacua (somewhat stronger assumptions are required by the fat geodesic measure). At this level of generality, none of the three measures are successful for vacua with negative cosmological constant. Their applicability in this regime is ruled out unless much stronger anthropic requirements are imposed., 34 pages, 5 figures

Without assuming necessary conditions for observers such as galaxies or entropy production, we show that the causal patch measure predicts the coincidence of vacuum energy and present matter density. Their common scale, and thus the enormous size of the visible universe, has its origin in the number of metastable vacua in the landscape., Comment: 5 pages, 2 figures. v2: minor editing

We compute trivariate probability distributions in the landscape, scanning simultaneously over the cosmological constant, the primordial density contrast, and spatial curvature. We consider two different measures for regulating the divergences of eternal inflation, and three different models for observers. In one model, observers are assumed to arise in proportion to the entropy produced by stars; in the others, they arise at a fixed time (5 or 10 billion years) after star formation. The star formation rate, which underlies all our observer models, depends sensitively on the three scanning parameters. We employ a recently developed model of star formation in the multiverse, a considerable refinement over previous treatments of the astrophysical and cosmological properties of different pocket universes. For each combination of observer model and measure, we display all single and bivariate probability distributions, both with the remaining parameter(s) held fixed, and marginalized. Our results depend only weakly on the observer model but more strongly on the measure. Using the causal diamond measure, the observed parameter values (or bounds) lie within the central $2\sigma$ of nearly all probability distributions we compute, and always within $3\sigma$. This success is encouraging and rather nontrivial, considering the large size and dimension of the parameter space. The causal patch measure gives similar results as long as curvature is negligible. If curvature dominates, the causal patch leads to a novel runaway: it prefers a negative value of the cosmological constant, with the smallest magnitude available in the landscape., Comment: 68 pages, 19 figures

The covariant entropy bound states that the entropy, S, of matter on a light-sheet cannot exceed a quarter of its initial area, A, in Planck units. The gravitational entropy of black holes saturates this inequality. The entropy of matter systems, however, falls short of saturating the bound in known examples. This puzzling gap has led to speculation that a much stronger bound, S< A^{3/4}, may hold true. In this note, we exhibit light-sheets whose entropy exceeds A^{3/4} by arbitrarily large factors. In open FRW universes, such light-sheets contain the entropy visible in the sky; in the limit of early curvature domination, the covariant bound can be saturated but not violated. As a corollary, we find that the maximum observable matter and radiation entropy in universes with positive (negative) cosmological constant is of order Lambda^{-1} (Lambda^{-2}), and not |Lambda|^{-3/4} as had hitherto been believed. Our results strengthen the evidence for the covariant entropy bound, while showing that the stronger bound S< A^{3/4} is not universally valid. We conjecture that the stronger bound does hold for static, weakly gravitating systems., 36 pages, 10 figures

Present treatments of eternal inflation regulate infinities by imposing a geometric cutoff. We point out that some matter systems reach the cutoff in finite time. This implies a nonzero probability for a novel type of catastrophe. According to the most successful measure proposals, our galaxy is likely to encounter the cutoff within the next 5 billion years., Comment: 22 pages, 1 figure

We propose to regulate the infinities of eternal inflation by relating a late time cut-off in the bulk to a short distance cut-off on the future boundary. The light-cone time of an event is defined in terms of the volume of its future light-cone on the boundary. We seek an intrinsic definition of boundary volumes that makes no reference to bulk structures. This requires taming the fractal geometry of the future boundary, and lifting the ambiguity of the conformal factor. We propose to work in the conformal frame in which the boundary Ricci scalar is constant. We explore this proposal in the FRW approximation for bubble universes. Remarkably, we find that the future boundary becomes a round three-sphere, with smooth metric on all scales. Our cut-off yields the same relative probabilities as a previous proposal that defined boundary volumes by projection into the bulk along timelike geodesics. Moreover, it is equivalent to an ensemble of causal patches defined without reference to bulk geodesics. It thus yields a holographically motivated and phenomenologically successful measure for eternal inflation., Comment: 39 pages, 4 figures; v2: minor corrections

We develop a simple semi-analytic model of the star formation rate (SFR) as a function of time. We estimate the SFR for a wide range of values of the cosmological constant, spatial curvature, and primordial density contrast. Our model can predict such parameters in the multiverse, if the underlying theory landscape and the cosmological measure are known., Comment: 26 pages, 11 figures. For Mathematica notebook, go to http://panic.berkeley.edu/~sleichen/ComputeSFR.nb