Quantum Information and String Theory 2019

Program

• 1st, 2nd week
• 3rd week (QI workshop)
• 4th, 5th weeks (IFQ school/workshop)

3rd week (QI workshop)

Detailed Program (PDF) (updated on May 28).

Timetable of the 3rd week (June 10 - 14)

[Current List of Invited Speakers in Quantum Information Workshop, June 10-June 14, 2019]

• Fernando Brandao (Caltech) on June 11
    "Localizable Mutual Information: Tensor Networks meet Dynamical Systems"

We will study the problem of defining a parent Hamiltonian for matrix product density operators and connect it to the theory of linear cocycles on ergodic dynamical systems.

• Fernando Brandao (Caltech) on June 13
    "Quantum Computing in the Near Term"

Small quantum computers are around the corner, with fifty to few hundred qubits and small enough error rates which make them hard to simulate on standard computers. The era of Noisy Intermediate-Scale Quantum (NISQ) devices is exciting, as for the first time there is an opportunity for quantum hardware to outperform standard computing, but it is also challenging, as there is no currently known applications with guaranteed speed-up for NISQ devices. In this talk I will review progress in this direction and discuss how development on small quantum computers pave the way for the longer term vision of scalable quantum computers, capable e.g. of breaking RSA.

• Michele Dall'Arno (National University of Singapore)
    "Data-Driven Inference, Reconstruction, and Observational Completeness of Quantum Devices"

The range of a quantum measurement is the set of output probability distributions that can be produced by varying the input state. We introduce data-driven inference as a protocol that, given a set of experimental data as a collection of output distributions, infers the quantum measurement which is, i) consistent with the data, in the sense that its range contains all the distributions observed, and, ii) maximally noncommittal, in the sense that its range is of minimum volume in the space of output distributions. We show that data-driven inference is able to return a measurement up to symmetries of the state space (as it is solely based on observed distributions) and that such limit accuracy is achieved for any data set if and only if the inference adopts a (hyper)-spherical state space (for example, the classical or the quantum bit). When using data-driven inference as a protocol to reconstruct an unknown quantum measurement, we show that a crucial property to consider is that of observational completeness, which is defined, in analogy to the property of informational completeness in quantum tomography, as the property of any set of states that, when fed into any given measurement, produces a set of output distributions allowing for the correct reconstruction of the measurement via data-driven inference. We show that observational completeness is strictly stronger than informational completeness, in the sense that not all informationally complete sets are also observationally complete. Moreover, we show that for systems with a (hyper)-spherical state space, the only observationally complete simplex is the regular one, namely, the symmetric informationally complete set.

• Alexandru Cojocaru (The University of Edinburgh)
    "How classical parties can obtain a secure access in the quantum internet: QFactory from the Learning-With-Errors problem"

In this talk I will focus on our recent work on how to enable a fully classical party to participate in quantum protocols (including delegated blind quantum computation) and why this is important. The primitive of delegated pseudo-secret random qubit generator (PSRQG) will be introduced, and a protocol achieving this based on trapdoor one-way functions with extra properties will be given. Following, I will delve further in the primitive PSRQG. I will first give a concrete construction of the function required for the simplest construction (secure only against honest-but-curious adversaries), based on the Learning-With-Errors problem and the trapdoor function of Micciancio and Peikert. Then, I will give the second protocol that is secure against malicious adversaries, giving also the intuition of the proof and the new, modified functions used.

• Animesh Datta (University of Warwick)
    "Nonadaptive fault-tolerant verification of quantum supremacy with noise"

Quantum samplers are believed capable of sampling efficiently from distributions that are clas- sically hard to sample from. We consider a sampler inspired by the Ising model. It is nonadaptive and therefore experimentally amenable. Under a plausible average-case hardness conjecture, classical sampling upto additive errors from this model is known to be hard. We present a trap-based verification scheme for quantum supremacy that only requires the verifier to prepare single-qubit states. The verification is done on the same model as the original sampler, a square lattice, with only a constant factor overhead. We next revamp our verification scheme in two distinct ways using fault-tolerance that preserves the nonadaptivity. The first has a lower constant overhead based on error correction with the same threshold (0.75%) as universal quantum computation. The second has a higher constant overhead but an improved threshold (1.97%) based on error detection. We show that classically sampling upto additive errors is likely hard in both these schemes. Our results are applicable to more general sampling problems such as the Instantaneous Quantum Polynomial-time (IQP) computation model. It should also assist near-term attempts at experimentally demonstrating quantum supremacy and guide long-term ones.

• Keisuke Fujii (Osaka)
• Masahito Hayashi (Nagoya)
    "Verification of commuting quantum computations via fidelity estimation of weighted graph states"

First, we review the result of verification of graph states. After this review, we proceed to verification of weighted graph states. This topic is related to the instantaneous quantum polynomial time model (or the IQP model), which is one of promising models to demonstrate a quantum computational advantage over classical computers. If the IQP model can be efficiently simulated by a classical computer, an unlikely consequence in computer science can be obtained (under some unproven conjectures). In order to experimentally demonstrate the advantage using medium or large-scale IQP circuits, it is inevitable to efficiently verify whether the constructed IQP circuits faithfully work. There exists two types of IQP models, each of which is the sampling on hypergraph states or weighted graph states. For the first-type IQP model, polynomial-time verification protocols have already been proposed. In this paper, we propose verification protocols for the second-type IQP model. To this e! nd, we pr opose polynomial-time fidelity estimation protocols of weighted graph states for each of the following four situations where a verifier can (i) choose any measuremen t basis and perform adaptive measurements, (ii) only choose restricted measurement bases and perform adaptive measurements, (iii) choose any measurement basis and only perform non-adaptive measurements, and (iv) only choose restricted measurement bases and only perform non-adaptive measurements. In all of our verification protocols, the verifier's quantum operations are only single-qubit measurements. Since we assume no i.i.d. property on quantum states, our protocols work in any situation. A part of the contents is available as arXiv:1902.03369. This talk includes a joint work with Yuki Takeuchi.

• Francois Le Gall (Kyoto University)
    "Average-Case Quantum Advantage with Shallow Circuits"

Recently Bravyi, Gosset and König (Science 2018) proved an unconditional separation between the computational powers of small-depth quantum and classical circuits for a relation. In this talk I will present a similar separation in the average-case setting that gives a stronger evidence of the superiority of small-depth quantum computation: we construct a computational task that can be solved on all inputs by a quantum circuit of constant depth with bounded-fanin gates (a "shallow" quantum circuit) and show that any classical circuit with bounded-fanin gates solving this problem on a non-negligible fraction of the inputs must have logarithmic depth. Our results are obtained by introducing a technique to create quantum states exhibiting global quantum correlations from any graph, via a construction that we call the extended graph.

• Akimasa Miyake (New Mexico)
    "Symmetry, geometry, and topology in measurement-based quantum computation"

Measurement-based quantum computation (MBQC) is a scheme to simulate space-time dynamics on the network of certain initial entanglement, like the cluster state, using local measurements and classical communication (LOCC). First I present a pedagogical review of basic principles of MBQC, highlighting how the causal relations of space-time emerge. The pursuit of a broad class of useful (or computationally universal) entanglement encountered a concept of symmetry-protected topologically ordered (SPTO) phases in condensed matter physics. We analyze SPTO cluster phases on all vertex-translative 2D Archimedean lattices as examples, and characterize their computational capacity in terms of symmetry, geometry, and topology.

• Yoshifumi Nakata (YITP, Kyoto)
    "Black hole information paradox when black holes have symmetry"

Quantum information theory has shed new light on the black hole information paradox. It has been shown that the scrambling dynamics of black holes induces a good quantum error correcting code (QECC), and the quantum information of black holes can be carried away by the radiation far more quickly than expected. It is however not clear whether the scrambling dynamics is achievable in realistic black holes due to their symmetries, such as rotational, charge, and other symmetries. Although global symmetries are believed to be weakly violated in quantum gravity, an approximate symmetry prevents the early-time dynamics of black holes from being fully random, which implies that a part of quantum information remains unencoded in early time. Here, we study the information paradox when black holes have symmetry and prove that symmetry-preserving dynamics of black holes induces a novel information theoretic mechanism, which we call observable imprinting, and leads to quick evaporation of even unencoded information. We especially focus on rotating uncharged quantum black holes and show that 1. for small black holes, the information leakage occurs in a step-wise manner, and 2. for sufficiently large black holes, the information is fully evaporated extremely quickly. The second result is to some extent surprising from the QECC perspective since some information is not encoded but evaporates quickly, which becomes possible with the help of the observable imprinting. We think that our results contribute both to quantum information theory and the quantum black hole science and hence, are suitable for Quantum Information and String Theory 2019.

• Jonathan Oppenheim (University College London)
     "Entanglement fluctuation relations and the three laws of quantum resource theories"
• Mark Van Raamsdonk (UBC)
    "Spacetime from bits"

In the AdS/CFT correspondence, states of a continuum quantum field theory encode dual gravitational spacetimes. It has been argued that entanglement between degrees of freedom in the field theory system plays a crucial role in the emergence of the dual spacetime. In this talk, we describe a way to replace the continuum field theory state with an entangled state of a large collection of non-interacting systems in such a way that the entangled state still holographically encodes a single connected spacetime. In the new description, the importance of entanglement is manifest, upon removing it, the dual spacetime disintegrates. The entangled states we consider have a natural description in terms of tensor networks and may provide a more direct connection between holographic quantum field theory states and the tensor network states that have been proposed as toy models for holography.

• Robert Raussendorf (British Columbia)
    "A computationally universal phase of quantum matter"

We provide the first example of a symmetry protected quantum phase that has universal computational power. Throughout this phase, which lives in spatial dimension two, the ground state is a universal resource for measurement based quantum computation.

• Hal Tasaki (Gakushuin University)
    "Quantum Spin Chains and von Neumann Algebra: A Lieb-Schultz-Mattis type theorem without continuous symmetry"

By a Lieb-Schultz-Mattis type theorem, we mean a no-go theorem that rules out the existence of a unique gapped ground state in a certain class of quantum many-body systems. The original Lieb-Schultz-Mattis theorem, which was proved in 1961 for the antiferromagnetic Heisenberg chain, and its various extensions rely essentially on the U(1) symmetry of the models. Recently it was realized that Lieb-Schultz-Mattis type statements can be shown for one-dimensional quantum many-body systems that have discrete on-site symmetry whose action forms a nontrivial projective representation of the symmetry group. We here present a fully rigorous version of such a Lieb-Schultz-Mattis type theorem for one-dimensional quantum spin systems. Rather surprisingly (at least to the present speaker), the operator algebraic formulation of spin chains seems to be mandatory for the proof. In particular the notion of the von Neumann algebra (especially the Cuntz algebra) plays an essential role in the proof. I start from reviewing the original Lieb-Schultz-Mattis theorem and its proof, and then discuss the statement and the (basic strategy of the) proof of the new theorem. The new theorem can be stated as a no-go theorem for the existence of a translation invariant area-law states (which is not necessarily a ground state). The talk is based on a joint work with Yoshiko Ogata in arXiv:1808.08740 (tComm. Math. Phys. 2019).

• Tzu-Chieh Wei (SUNY)
    "Two-dimensional AKLT states as ground states of gapped Hamiltonians and resource for quantum computation"

Affleck, Kennedy, Lieb, and Tasaki (AKLT) constructed a one-dimensional spin-1 rotation-invariant chain with with an exact ground state and a nonzero spectral gap, supporting for Haldanefs conjecture. They generalized the construction to two dimensions, such as the spin-3/2 model on the honeycomb lattice and the spin-2 one on the square lattice. Despite exponential decay in the correlation functions, the nonzero spectral has not been proved analytically for more than 30 years. On the other hand, unexpectedly, these 2D AKLT states have recently emerged as resource for universal quantum computation in the framework of the measurement-based quantum computation (MBQC). In addition to the two lattices, AKLT states on a few decorated lattice structures were also shown to be universal. A partial understanding of the universality in the AKLT family emerged.

 Recently a breakthrough of proving nonzero gap was made by Abdul-Rahman et al. [arXiv:1901.09297] for AKLT models on decorated honeycomb lattices with n>=3, where n is the number of spin-1 sites added on each original edge. We have extended the proof of nonzero spectral gap to AKLT models to decorated square lattices and ones whose original lattice is of mixed vertex degrees 3 and 4 [arXiv:1905.01275]. We also developed an numerical approach to improve the gappedness to n>=2 for all the above AKLT models. I will give some brief review of the AKLT states as universal resource and explain the proof of the gap, as well as our numerical approach.

[Oral Presentations in QI workshop, June 10-June 14, 2019]

• Thomas Christopher Bohdanowicz (IQIM, Caltech)
  "Universal Hamiltonians for Exponentially Long Simulation: Exploring Susskind's Conjecture"

We construct a Hamiltonian whose dynamics simulate the dynamics of every other Hamiltonian up to exponentially long times in the system size. The Hamiltonian is time-independent, local, one-dimensional, and translation invariant. As a consequence, we show (under plausible computational complexity assumptions) that the circuit complexity of the unitary dynamics under this Hamiltonian grows steadily with time up to an exponential value in system size. This result makes progress on a recent conjecture by Susskind, in the context of the AdS/CFT correspondence, that the time evolution of the thermofield double state of two conformal fields theories with a holographic dual has a circuit complexity increasing linearly in time, up to exponential time. arXiv:1710.02625v2

• Robie Arthur Hennigar (Memorial University of Newfoundland)
  "Universality of squashed-sphere partition functions"

We present several results concerning the free energy of odd-dimensional conformal field theories (CFTs) on squashed spheres. First, we propose a formula which computes this quantity for holographic CFTs dual to higher-curvature gravities with second-order linearized equations of motion. As opposed to standard on-shell action methods for Taub geometries, our formula only involves a simple evaluation of the corresponding bulk Lagrangian on an auxiliary pure-AdS space. The expression is closely related to the function determining the possible AdS vacua of the bulk theory in question, which we argue to act as a generating functional from which correlation functions of the boundary stress tensor can be easily characterized. Finally, based on holographic results and free-field numerical calculations, we conjecture that the sub-leading term in the squashing-parameter free-energy expansion is universally controlled by the stress-tensor three-point function charge t4 for general (2 + 1)-dimensional CFTs. Based on arXiv:1808.02052.

• Nicholas Hunter-Jones (Perimeter Institute)
  "Unitary designs from statistical mechanics in random quantum circuits"

Random quantum circuits are rapid information scramblers and efficient generators of randomness. In this talk we look at the convergence of local random circuits to unitary k-designs, ensembles which approximate moments of the full unitary group. Using a statistical mechanical mapping, we give an exact expression of the distance to forming an approximate design as a lattice partition function. In the statistical mechanics model, the approach to randomness has a simple interpretation in terms of domain walls extending through the circuit. We analytically compute the second moment, showing that random circuits acting on n qudits form approximate 2-designs in O(n) depth. Furthermore, we argue that random circuits form approximate unitary k-designs in O(nk) depth and are thus essentially optimal in both n and k.

• Alexander Jahn (FU Berlin)
  "Majorana dimers and holographic quantum error-correcting codes"

In this talk, we consider a class of ground states of quadratic Hamiltonians characterized by a non-local pairing of Majorana fermions. These dimer-like states appear in stabilizer codes used for quantum error correction. We rigorously establish a framework where the application of local errors, tensor contractions and the computation of entanglement entropy can be performed in a simple diagrammatic fashion. Applied to the holographic pentagon code - a toy model for the AdS/CFT correspondence - our approach yields new insights into the correlation structure of holographic tensor networks. The talk is based on: arXiv:1905.03268

• Aleksander Marek Kubica (Perimeter Institute)
  "Efficient color code decoders in d ≥ 2 dimensions from toric code decoders"

We introduce an efficient decoder of the color code in d ≥ 2 dimensions, the Restriction Decoder, which uses any d-dimensional toric code decoder combined with a local lifting procedure to find a recovery operation. We prove that the Restriction Decoder successfully corrects errors in the color code if and only if the corresponding toric code decoding succeeds. We also numerically estimate the Restriction Decoder threshold for the color code in two and three dimensions against the bit-filp and phase-flip noise with perfect syndrome extraction. We report that the 2D color code threshold p = 10.2% on the square-octagon lattice is on a par with the toric code threshold on the square lattice.

• Adam Levine (UC Berkeley)
• Reevu Maity (Oxford, MIT)
  "Efficient implementation of unitary transformations"

Quantum computation and quantum control operate by building unitary transformations out of sequences of elementary quantum logic operations or applications of control fields. This paper puts upper bounds on the minimum time required to implement a desired unitary transformation on a d-dimensional Hilbert space when applying sequences of Hamiltonian transformations. We show that strategies of building up a desired unitary out of non-infinitesimal and infinitesimal unitaries, or equivalently, using power and band limited controls, can yield the best possible scaling in time O(d^2).

• Yasusada Nambu (Nagoya University)
  "Quantum circuit model of black hole evaporation"

We consider a quantum circuit model describing the evaporation process of black holes. We specifically examine the behavior of the multipartite entanglement represented by this model, and find that the entanglement structure depends on the black hole mass $M$ and the frequency of the Hawking radiation $omega$. For sufficiently small values of $Momega$, the black hole and the radiation system becomes a separable state after the Page time and a firewall-like structure appears. On the contrary, for larger values of $Momega$, the entanglement between the black hole and the radiation is not lost. These behaviors imply that owing to the monogamy property of the multipartite entanglement, low frequency modes of the Hawking radiation destroys the quantum correlation between the black hole and the emitted Hawking radiation.

• Zahra Raissi (ICFO)
  "Constructing k-uniform states of non-minimal support"

A pure quantum state of n subsystems each having local dimension q is called k-uniform state, if all k-qudit reductions of the whole system are maximally mixed. These states form a natural generalization of n qudits EPR and GHZ states which belong to the class 1-uniform states. The k-uniform states are known to play an important role in quantum information processing when dealing with many parties. They are useful for multipartite teleportation and in quantum secret sharing. These states have also deep connections with apparently unrelated areas of mathematics such as combinatorial designs and structures [arXiv:1708.05946], classical error correcting codes (CECC), and quantum error correcting codes (QECC) [arXiv:1701.03359].

The Schmidt decomposition shows that a state can be at most \floor[n/2]-uniform, i.e., k <= \floor[n/2]. The \floor[n/2]-uniform states are called Absolutely Maximally Entangled states or AME states for short. We describe that there can be a direct correspondence between a given CECC and k-uniform state of minimal support if there exists a coordinate such that any k symbols of the codewords can be taken as message symbols. One aspect of this connection can provide a framework to develop a stabilizer formalism and produce an orthonormal basis of a given k-uniform state. We also study the description of these k-uniform states within the graph state formalism. We show the graphical representation for the state constructed from a CECC form a bipartite graph.

We also propose a systematic method to construct a set of non-minimal support k-uniform states. We show that these states have better parameter compare to the k-uniform states that are obtained from the CECCs. More precisely we show, for given n and local dimension q, if both k-uniform state of minimal support and non-minimal support exist, the two states are not local unitary equivalent. In an analogous fashion, we construct a set of Pauli strings that generate a stabilizer group that stabilizes a given k-uniform state of non-minimal support. Also, we compare the graphical representation of the k-uniform state of minimal support and non-minimal support.

• Burak Sahinoglu (IQIM, Caltech)
• Grant Salton (IQIM, Caltech)
  "Covariant quantum error correction, symmetries, and time evolution in holography "

In the usual paradigm of quantum error correction, the information to be protected can be encoded in a system of abstract qubits or modes. But how does this work for physical information, which cannot be described in this way? Just as direction information cannot be conveyed using a sequence of words if the parties involved do not share a reference frame, physical quantum information cannot be conveyed using a sequence of qubits or modes without a shared reference frame. Covariant quantum error correction is a procedure for protecting such physical information against noise in such a way that the encoding and decoding operations transform covariantly with respect to an external symmetry group. In this talk, we'll study covariant QEC, and we will see that there do not exist finite dimensional quantum codes that are covariant with respect to continuous symmetries. Conversely, we'll see that there do exist finite codes for finite groups, and continuous variable (CV) codes for continuous groups. This leads to a CV method of circumventing the Eastin-Knill theorem. By relaxing our requirements to allow for only approximate error correction and covariance, we'll find a fundamental tension between a code's ability to approximately correct errors and covariance with respect to a continuous symmetry. In this way, we'll arrive at an approximate version of the Eastin-Knill theorem, and we'll end by learning what covariant QEC tells us about continuous symmetries in AdS/CFT, among other applications.

• Noburo Shiba (KEK)
  "Direct Expression of Mutual Information of Distant Regions"

We consider the mutual (Renyi) information, I^(n)(A,B)=S^(n)_A+S^(n)_B-S^(n)_{AcupB} , of distant compact spatial regions A and B in the vacuum state of a free scalar field. The distance r between A and B is much greater than their sizes R_{A,B}. It is known that I^(n)(A,B) ~ C^(n)_{AB} ^2 . We obtain the direct expression of C^(n)_{AB} for arbitrary regions A and B. We perform the analytical continuation of n and obtain the mutual information. The direct expression is useful for the numerical computation. By using the direct expression, we can compute directly I(A,B) without computing S_A, S_B and S_{AcupB} respectively, so it reduces significantly the amount of computation.

• Hiroyasu Tajima (University of Electro-Communications)
  "Fundamental exchange rate between coherence and asymmetry"

The relationship between the coherence which is the basic element of quantum mechanics and the conservation law which is the basic law of physics has been studied vigorously since long ago [1,2]. Although the conservation laws impose various restrictions on the operations that we can perform, the sufficient amount of quantum coherence can alleviate the restrictions.

In recent years, the quantum information theory strongly pushes forward the above direction. In the researches, we consider the situation that we try to implement "asymmetric" operations that break conservation laws by using quantum coherence and "symmetric" operations that satisfy conservation laws. One of the open problems in this context is to clarify the "minimal sufficient" amount of coherence required when performing asymmetric unitary operations. This problem was actively studied, and given upper bound [3] and lower bound [4] for the minimal sufficient amount, but there was still a large gap between them.

Here, we solve the problem. We give a simple equality between coherence and asymmetry. We consider the situation that we try to implement a unitary $U_S$ on a system $S$ by the interaction between $S$ and an external system $E$. As a limitation on the total dynamics $U_{SE}$, we impose the conservation law $[U_{SE}, A_S+A_E]=0$. Also, we measure the coherence by quantum Fisher information, as is widely done in recent resource theory of asymmetry [5]. Then, the ``minimal sufficient'' amount of coherence $F$ to realize $U_S$ within error $delta$ satisfies the following simple formula:

F=A_{U_S}/delta+O(1),

where $A_{U_S}$ is the degree of asymmetry of the implemented unitary $U_S$, i.e., the difference between the maximum and the minimum of singular values of the commutator $[A_S,U_S]$.

Because our formula reveals a fundamental link between coherence and symmetry, it can be applied to various fields. One of interesting byproducts of our formula is on resource theory of coherence [6]. In the resource theory of coherence, the "incoherent operations" are treated as free operations, which we can easily use. However, using our results, we show that infinite coherence is required to implement certain kinds of incoherent operations without errors under the conservation law. There are various classes of incoherent operations, e.g., maximally incoherent operations (MIO), incoherent operations (IO), strictly incoherent operations (SIO), physically incoherent operations (PIO) and dephasing covariant incoherent operations (DIO), and these classes have two hierarchical structures, i.e., PIO$subset$SIO$subset$IO$subset$MIO and PIO$subset$SIO$subset$DIO$subset$MIO. Interestingly, the incoherent operations that require the infinite coherence exist even in PIO. Namely, incoherent operations need much coherence.

References:
[1] Y. Aharonov and L. Susskind, Phys. Rev. 155, 1428 (1967).
[2] A. Kitaev, D. Mayers, and J. Preskill, Phys. Rev. A 69, 052326 (2004).
[3] J. Aberg, Phys. Rev. Lett. 113, 150402 (2014).
[4] H. Tajima, N. Shiraishi and K. Saito, Phys. Rev. Lett. 121, 110403 (2018).
[5] I. Marvian, arXiv:1805.01989 (2018).
[6] A. Winter and Dong Yang, Phys. Rev. Lett. 116, 120404 (2016).


• Yuki Takeuchi (NTT Communication Science Laboratories, NTT Corporation)
  "Quantum computational universality of hypergraph states with Pauli-X and Z basis measurements"

Measurement-based quantum computing is one of the most promising quantum computing models. Although various universal resource states have been proposed so far, it was open whether only two Pauli bases are enough for both of universal measurement-based quantum computing and its verification. In this talk, we construct a universal hypergraph state that only requires adaptive Pauli X and Z-basis measurements for universal measurement-based quantum computing. We also show that universal measurement-based quantum computing on our hypergraph state can be verified in polynomial time using only non-adaptive X and Z-basis measurements.

[Poster Presenters on June 12]