Documentation

FormalConjectures.OpenQuantumProblems.«35»

Open Quantum Problem 35: existence of absolutely maximally entangled pure states #

Problem: For which numbers of parties $n$ and local dimensions $d$ does there exist a pure absolutely maximally entangled state $\psi$?

A pure state $\psi$ on $n$ parties of local dimension $d$ is called absolutely maximally entangled (AME) if, for every subset of at most half of the parties, the corresponding reduced density matrix is maximally mixed.

References:

This file formalizes the problem of determining for which pairs $(n,d)$ there exists an absolutely maximally entangled pure state $\mathrm{AME}(n,d)$.

We represent an $n$-partite state of local dimension $d$ by the finite-dimensional Hilbert space EuclideanSpace ℂ (Config n d), whose coordinates in the computational basis are amplitudes. The helper mkStateVector turns an amplitude function into such a state, and normalization is imposed explicitly via IsNormalized, i.e. via the ambient $L^2$ norm.

The main reusable lemma is reducedDensityFirst_of_completion: if a state is a uniform superposition over the graph of an injective completion function completion : Config m d → Config (n - m) d, then the reduced state on the first $m$ parties is maximally mixed.

As demonstration, we show that the Bell states with $n=2$ and GHZ states with $n=3$ are AME states, and the GHZ state with $n=4$ is not an AME state.

@[reducible, inline]

A computational-basis configuration of $n$ parties with local dimension $d$.

Equations
Instances For
    @[reducible, inline]

    A state vector in the computational basis, viewed as a finite-dimensional Hilbert space.

    Equations
    Instances For
      @[reducible, inline]
      abbrev OpenQuantumProblem35.mkStateVector {n d : } (ψ : Config n d) :

      Build a state vector from its computational-basis amplitudes.

      Equations
      Instances For

        A state vector can be evaluated on a computational-basis configuration to read its amplitude.

        Equations
        @[simp]
        theorem OpenQuantumProblem35.mkStateVector_apply {n d : } (ψ : Config n d) (x : Config n d) :
        (mkStateVector ψ).ofLp x = ψ x

        A state built from amplitudes has those amplitudes as its coordinates.

        A state vector is normalized if it has $L^2$ norm $1$.

        Equations
        Instances For

          A state is normalized iff its squared $L^2$ norm is $1$.

          def OpenQuantumProblem35.permuteConfig {n d : } (π : Equiv.Perm (Fin n)) (x : Config n d) :
          Config n d

          Permute the parties of a configuration.

          Equations
          Instances For

            The identity permutation leaves a configuration unchanged.

            Permute the parties of a state vector.

            Equations
            Instances For
              @[simp]
              theorem OpenQuantumProblem35.permuteState_apply {n d : } (π : Equiv.Perm (Fin n)) (ψ : StateVector n d) (x : Config n d) :
              (permuteState π ψ).ofLp x = ψ.ofLp (permuteConfig π x)

              Evaluating a permuted state vector reads the amplitude at the permuted configuration.

              The identity permutation leaves a state vector unchanged.

              def OpenQuantumProblem35.combineFirst {n d : } (m : ) (hm : m n) (x : Config m d) (y : Config (n - m) d) :
              Config n d

              Merge a configuration on the first $m$ parties and a configuration on the remaining $n-m$ parties into a configuration on all $n$ parties.

              Equations
              Instances For
                def OpenQuantumProblem35.leftIndex {m n : } (hm : m n) (i : Fin m) :
                Fin n

                The embedding of the first $m$ indices into $\mathrm{Fin}\, n$.

                Equations
                Instances For
                  def OpenQuantumProblem35.rightIndex {m n : } (hm : m n) (i : Fin (n - m)) :
                  Fin n

                  The embedding of the last $n-m$ indices into $\mathrm{Fin}\, n$.

                  Equations
                  Instances For
                    @[simp]
                    theorem OpenQuantumProblem35.combineFirst_leftIndex {n d m : } (hm : m n) (x : Config m d) (y : Config (n - m) d) (i : Fin m) :
                    combineFirst m hm x y (leftIndex hm i) = x i

                    Combining and then restricting to the left block recovers the left input.

                    @[simp]
                    theorem OpenQuantumProblem35.combineFirst_rightIndex {n d m : } (hm : m n) (x : Config m d) (y : Config (n - m) d) (i : Fin (n - m)) :
                    combineFirst m hm x y (rightIndex hm i) = y i

                    Combining and then restricting to the right block recovers the right input.

                    noncomputable def OpenQuantumProblem35.reducedDensityFirst {n d : } (m : ) (hm : m n) (ψ : StateVector n d) :
                    Matrix (Config m d) (Config m d)

                    The reduced density matrix obtained by tracing out the last $n-m$ parties.

                    The subsystem is always the first $m$ parties; different subsystems are handled by first permuting the parties.

                    Equations
                    • One or more equations did not get rendered due to their size.
                    Instances For
                      noncomputable def OpenQuantumProblem35.maximallyMixed (m d : ) :
                      Matrix (Config m d) (Config m d)

                      The maximally mixed state on $m$ parties.

                      Equations
                      Instances For

                        A state has maximally mixed reduction on the first $m$ parties.

                        Equations
                        Instances For

                          A state $\psi$ is absolutely maximally entangled.

                          Standard AME definitions quantify over all subsets $A \subseteq \mathrm{Fin}\, n$ with $|A| \le \lfloor n/2 \rfloor$ and require that the reduction on $A$ be maximally mixed. For pure states it is enough to check subsets of size exactly $\lfloor n/2 \rfloor$; see the references of Helwig--Cui--Riera--Latorre--Lo (2012) and Goyeneche--Alsina--Latorre--Riera--Życzkowski (2015). In this file, a subsystem of that size is encoded by first permuting the chosen parties to the front and then tracing out the remaining parties.

                          We also require $\psi$ to be normalized explicitly.

                          Equations
                          • One or more equations did not get rendered due to their size.
                          Instances For

                            Existence of an $\mathrm{AME}(n,d)$ state.

                            Equations
                            Instances For

                              No absolutely maximally entangled state exists in local dimension $0$ once $n \ge 1$.

                              @[simp]

                              The number of computational-basis configurations on $m$ parties of local dimension $d$ is $d^m$.

                              theorem OpenQuantumProblem35.maximallyMixed_apply {m d : } (x y : Config m d) :
                              maximallyMixed m d x y = if x = y then (↑(Fintype.card (Config m d)))⁻¹ else 0

                              The matrix entries of the maximally mixed state are diagonal and equal to the inverse subsystem dimension.

                              noncomputable def OpenQuantumProblem35.uniformCoeff (d : ) :

                              The common amplitude of the Bell and GHZ witnesses.

                              Equations
                              Instances For

                                A configuration is constant if all coordinates agree.

                                Equations
                                Instances For

                                  The constant configuration with value $a$.

                                  Equations
                                  Instances For

                                    Every constant configuration is constant.

                                    A simple binary two-party configuration with different entries is not constant.

                                    noncomputable def OpenQuantumProblem35.diagonalState (n d : ) :

                                    The diagonal $n$-party state: the uniform superposition over constant computational-basis strings.

                                    Equations
                                    • One or more equations did not get rendered due to their size.
                                    Instances For
                                      @[simp]

                                      Evaluating the diagonal state returns the uniform coefficient on constant strings and 0 otherwise.

                                      @[reducible, inline]
                                      noncomputable abbrev OpenQuantumProblem35.bellState (d : ) :

                                      The standard $d$-dimensional Bell state.

                                      Equations
                                      Instances For
                                        @[reducible, inline]
                                        noncomputable abbrev OpenQuantumProblem35.ghzState (d : ) :

                                        The standard $d$-dimensional GHZ state on $3$ parties.

                                        Equations
                                        Instances For
                                          @[reducible, inline]
                                          noncomputable abbrev OpenQuantumProblem35.ghzState4 (d : ) :

                                          The standard $d$-dimensional GHZ state on $4$ parties.

                                          Equations
                                          Instances For

                                            The completion function for constant-support states reduced to one party.

                                            Equations
                                            Instances For

                                              On a nonempty index type, different constants give different constant configurations.

                                              A configuration on a nonempty index type is constant iff it is equal to some constant configuration.

                                              The squared norm of the uniform coefficient is the inverse local dimension.

                                              The squared norm of the uniform coefficient is the inverse local dimension.

                                              For $n \ge 1$ and $d \ge 1$, the diagonal state is normalized.

                                              Permuting the parties preserves the property of being a constant configuration.

                                              The diagonal state is invariant under permutations of the parties.

                                              theorem OpenQuantumProblem35.constantCompletion_eq_iff {n d : } (x : Config 1 d) (z : Config (n - 1) d) :
                                              z = constantCompletion x ∀ (i : Fin (n - 1)), z i = x 0

                                              A tail configuration equals the constant completion of $x$ iff all of its entries agree with the unique entry of $x$.

                                              theorem OpenQuantumProblem35.eq_leftIndex_zero_or_eq_rightIndex {n : } (hn : 1 n) (i : Fin n) :
                                              i = leftIndex hn 0 ∃ (j : Fin (n - 1)), i = rightIndex hn j

                                              Every index in $\mathrm{Fin}\, n$ is either the unique left index or a right index when the left block has size $1$.

                                              The completion map for constant configurations is injective once $n \ge 2$.

                                              A configuration obtained by combining one entry with a tail is constant iff the tail is the constant completion of that entry.

                                              The diagonal state on a split configuration is nonzero exactly on the graph of the constant completion map.

                                              theorem OpenQuantumProblem35.reducedDensityFirst_of_completion {n d m : } (hm : m n) (ψ : StateVector n d) (completion : Config m dConfig (n - m) d) (coeff : ) ( : ∀ (x : Config m d) (z : Config (n - m) d), ψ.ofLp (combineFirst m hm x z) = if z = completion x then coeff else 0) (hinj : Function.Injective completion) :
                                              reducedDensityFirst m hm ψ = (coeff * star coeff) 1

                                              A uniform superposition over the graph of an injective completion map has reduced density matrix $(c\overline c) I$ on the first subsystem.

                                              theorem OpenQuantumProblem35.hasMaximallyMixedFirstReduction_of_completion {n d m : } (hm : m n) (ψ : StateVector n d) (completion : Config m dConfig (n - m) d) (coeff : ) ( : ∀ (x : Config m d) (z : Config (n - m) d), ψ.ofLp (combineFirst m hm x z) = if z = completion x then coeff else 0) (hinj : Function.Injective completion) (hnorm : coeff * star coeff = (↑(Fintype.card (Config m d)))⁻¹) :

                                              The completion criterion gives a maximally mixed reduced state once the coefficient has the correct squared norm.

                                              The diagonal state has maximally mixed one-party reductions once $n \ge 2$.

                                              theorem OpenQuantumProblem35.diagonalState_isAME_of_div_two_eq_one {n d : } (hn : 2 n) (hhalf : n / 2 = 1) (hd : 2 d) :

                                              If $\lfloor n/2 \rfloor = 1$, then the diagonal state is $\mathrm{AME}(n,d)$ for every $d \ge 2$.

                                              The standard Bell state is $\mathrm{AME}(2,d)$ for every physical local dimension $d \ge 2$.

                                              The standard $3$-party GHZ state is $\mathrm{AME}(3,d)$ for every physical local dimension $d \ge 2$.

                                              theorem OpenQuantumProblem35.ame_2_exists {d : } (hd : 2 d) :

                                              The Bell state witnesses the existence of $\mathrm{AME}(2,d)$ for every local dimension $d \ge 2$.

                                              theorem OpenQuantumProblem35.ame_3_exists {d : } (hd : 2 d) :

                                              The $3$-party GHZ state witnesses the existence of $\mathrm{AME}(3,d)$ for every local dimension $d \ge 2$.

                                              theorem OpenQuantumProblem35.diagonalState_combineFirst_two_of_ne {d : } {x z : Config 2 d} (h : x 0 x 1) :
                                              (diagonalState 4 d).ofLp (combineFirst 2 x z) = 0

                                              On $4$ parties, the diagonal state vanishes on any split configuration whose first two entries are different.

                                              Sanity check: the standard GHZ family on $4$ parties is not absolutely maximally entangled for any local dimension $d \ge 2$.

                                              Source-backed benchmark statement: the Bell state witnesses the existence of an $\mathrm{AME}(2,2)$ state.

                                              Source-backed benchmark statement: the three-qubit GHZ state witnesses the existence of an $\mathrm{AME}(3,2)$ state.

                                              Source-backed benchmark statement: an $\mathrm{AME}(5,2)$ state exists. This is one of the four qubit cases $n=2,3,5,6$; see the OQP page and Scott (2004).

                                              Source-backed benchmark statement: an $\mathrm{AME}(6,2)$ state exists. This is one of the four qubit cases $n=2,3,5,6$; see the OQP page and Scott (2004).

                                              Source-backed benchmark statement: no $\mathrm{AME}(4,2)$ state exists; see Higuchi--Sudbery (2000) and the OQP page.

                                              Source-backed benchmark statement: no $\mathrm{AME}(7,2)$ state exists; see Huber--Gühne--Siewert (2017) and the OQP page.

                                              Source-backed benchmark statement: an $\mathrm{AME}(4,3)$ state exists; see Helwig et al. (2012) and Goyeneche et al. (2015).

                                              Source-backed benchmark statement: an $\mathrm{AME}(4,6)$ state exists; see Rather et al. (2022).

                                              Open benchmark statement: does an $\mathrm{AME}(7,6)$ state exist?

                                              Open benchmark statement: does an $\mathrm{AME}(7,10)$ state exist?

                                              Open benchmark statement: does an $\mathrm{AME}(8,4)$ state exist?

                                              Open benchmark statement: does an $\mathrm{AME}(8,6)$ state exist?

                                              Open benchmark statement: does an $\mathrm{AME}(8,10)$ state exist?

                                              Open benchmark statement: does an $\mathrm{AME}(9,6)$ state exist?

                                              Open benchmark statement: does an $\mathrm{AME}(9,10)$ state exist?

                                              Open benchmark statement: does an $\mathrm{AME}(10,6)$ state exist?

                                              Open benchmark statement: does an $\mathrm{AME}(10,10)$ state exist?

                                              Open benchmark statement: does an $\mathrm{AME}(11,3)$ state exist?

                                              Open benchmark statement: does an $\mathrm{AME}(11,4)$ state exist?

                                              Open benchmark statement: does an $\mathrm{AME}(11,5)$ state exist?

                                              The DeepMind prover agent has shown that such a state exists.

                                              Open benchmark statement: does an $\mathrm{AME}(11,6)$ state exist?

                                              Open benchmark statement: does an $\mathrm{AME}(11,10)$ state exist?

                                              Open benchmark statement: does an $\mathrm{AME}(12,5)$ state exist?

                                              Open benchmark statement: does an $\mathrm{AME}(12,6)$ state exist?

                                              Open benchmark statement: does an $\mathrm{AME}(12,10)$ state exist?

                                              theorem OpenQuantumProblem35.oqp_35 :
                                              {nd : × | 2 nd.1 2 nd.2 ExistsAME nd.1 nd.2} = sorry

                                              Open Quantum Problem 35: classify all pairs $(n,d)$ with $n \ge 2$ and $d \ge 2$ for which an $\mathrm{AME}(n,d)$ state exists.