Interessant twittertråd: https://x.com/lorenzo_leone_/status/1773609330039824580?s=46 Basert på paperet [Magic-induced computational separation in entanglement theory](https://arxiv.org/abs/2403.19610), som systematisk sammenligner [[Sammenfiltring]] og [[Kvantemagi]]. Fra abstract: > Entanglement serves as a foundational pillar in quantum information theory, delineating the boundary between what is classical and what is quantum. The common assumption is that higher entanglement corresponds to a greater degree of ‘quantumness’. However, this folk belief is challenged by the fact that classically simulable operations, such as Clifford circuits, can create highly entangled states. The simulability of these states raises a question: what are the differences between ‘low-magic’ entanglement, and ‘high-magic’ entanglement? We answer this question in this work with a rigorous investigation into the role of magic in entanglement theory. (...) Specifically, we find a sharp operational separation that splits Hilbert space into two distinct phases: the entanglement-dominated (ED) phase and magic-dominated (MD) phase. Roughly speaking, ED states have entanglement that significantly surpasses their magic, while MD states have magic that dominates their entanglement. The competition between the two resources in these two phases induces a computational phase separation between them: there are sampleand time-efficient quantum algorithms for almost any entanglement task on ED states, while these tasks are provably computationally intractable in the MD phase. Virker som et viktig skritt fremover i det [[John Preskill]] kalte [[The High-Entaglement Frontier]]. ![[Pasted image 20240329155747.png]] > FIG. 1. The sharp distinction between entanglement-dominated and magic-dominated states. The landscape visualizes the entanglement structure of states: in the entanglement-dominated phase, entanglement is highly structured and easily manipulable, while in the magic-dominated phase, entanglement can be scrambled in such a complex way that it is completely intractable to measure or manipulate. De oppsummerer: > Within the ED phase, entanglement is always structured in such a way that it can be manipulated efficiently and (almost) reversibly. In contrast, for general states in the MD phase, there is almost no structure in the entanglement, making entanglement manipulation inefficient and irreversible. Interessant spørsmål som akkurat falt meg inn: Eksisterer det [[QMA]]-problemer i MD-landskapet som sitter utenfor [[NP]]? Kan de brukes til noe? > We also develop an efficient testing algorithm which can classify states within the ED and MD phases. Okei, så å *klassifisere* tilstandene lar seg i det minste gjøre effektivt (av en kvantealgoritme, antar jeg): > In light of the clear distinction between ED-MD phases, one might ask whether it is possible, given query access to an unknown state |ψ⟩, to determine the phase in which it resides. We formalize this task as a property testing problem and show that the separation between ED-MD phases can indeed be efficiently tested. More precisely, in Theorem 23, we present a polynomial-time algorithm that can discriminate whether |ψ⟩ is an ED state or it is ϵ-far from any state in the entanglement-dominated phase and, as such, lies in the MD phase. Rettelse: Nei, ser ut til å være klassisk! (Hvordan leser man av en generell kvantetilstand med en effektiv klassisk algoritme?) > We show how to *exactly* compute the 2-Rényi entanglement entropy of a state with stabilizer nullity ν using a classical algorithm whose runtime is $O(4^ν n^3)$. We then show how to efficiently monitor the stabilizer entanglement produced by a $t$-doped Clifford circuit using an efficient classical algorithm, and finally show how to efficiently witness entanglement for ED states.