Preparing matrix product states via fusion: constraints and extensions
David T. Stephen Oliver Hart








These authors contributed equally to this work
Department of Physics and Center for Theory of Quantum Matter, University of Colorado Boulder, Boulder, Colorado 80309 USA
Department of Physics and Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, California, USA


These authors contributed equally to this work
Department of Physics and Center for Theory of Quantum Matter, University of Colorado Boulder, Boulder, Colorado 80309 USA


    In the era of noisy, intermediate-scale quantum (NISQ) devices, the efficient preparation of many-body resource states is a task of paramount importance. In this paper we focus on the deterministic preparation of matrix-product states (MPS) in constant depth by utilizing measurements and classical communication to fuse smaller states into larger ones. We place strong constraints on the MPS that can be prepared using this method, which we refer to as MPS fusion. Namely, we establish that it is necessary for the MPS to have a flat entanglement spectrum.
    Using the recently introduced split-index MPS (SIMPS) representation, we then introduce a family of states that belong to interesting phases of matter protected by non-onsite symmetries and serve as resources for long-range quantum teleportation, but which lie beyond the scope of ordinary MPS fusion. It is shown constructively that these states can be prepared in constant depth using a broader class of measurement-assisted protocols, which we dub SIMPS fusion. Even in cases when MPS fusion is possible, using SIMPS fusion can give rise to significantly reduced resource overhead. Our results therefore simultaneously establish the boundaries of conventional MPS fusion and push the envelope of which states can be prepared using measurement-assisted protocols.




Preparing matrix product states via fusion: constraints and extensions
    Oliver Hart
    April 29, 2024
======================================================================








The complexity of preparing a many-body quantum state from an initial product state is a problem of both fundamental and practical significance. On one hand, the question of whether a many-body state can be prepared using a finite-depth quantum circuit (FDQC) underpins the modern classification of ground-state phases of matter <cit.>. On the other hand, many-body states are essential in many schemes of quantum metrology <cit.>, communication <cit.>, and computation <cit.>, so any protocol that facilitates their preparation will have important practical consequences.
For these reasons, there has been significant recent interest in developing new protocols to prepare interesting many-body quantum states in quantum computers <cit.>. This interest is also driven by the new tools provided by modern quantum computers that go beyond local unitary circuits. One particularly powerful tool is the ability to perform projective measurements on single degrees of freedom and apply unitary operations based on the measurement outcomes <cit.>. This ability can drastically reduce the circuit depth needed to prepare and manipulate topologically ordered states <cit.>, allow implementation of long-range quantum gates <cit.>, and more generally enable exchange between spatial and temporal quantum resources <cit.>.

A powerful method of using measurements to prepare quantum states is based on the matrix product state (MPS) formalism <cit.>. In Ref. <cit.>, it was shown that the Affleck-Kennedy-Lieb-Tasaki (AKLT) state <cit.>, which is simultaneously a paradigmatic example of an MPS, a symmetry-protected topological (SPT) phase of matter <cit.>, and a resource for quantum computation <cit.>, can be deterministically prepared in constant depth using measurement and feedforward. The approach involves preparing small AKLT chains and fusing them into longer chains using measurements. The special symmetry properties of the AKLT state then allow the effects of undesirable measurement outcomes to be undone using unitary feedforward, resulting in a deterministic protocol. 
Given the fact that MPS are capable of capturing many interesting classes of one-dimensional (1D) many-body states <cit.>, it is important to understand the limitations and potential extensions of this method, which we refer to as MPS fusion.

In this paper, we derive fundamental constraints on MPS fusion, and then describe a new method that goes beyond these constraints. Our constraints show that MPS can only be prepared via fusion if they have a flat entanglement spectrum, as is true for the AKLT state. This constraint matches well with the intuition that the fusability of the AKLT state is related to its non-trivial SPT order <cit.>, which is in turn associated with entanglement spectrum degeneracy <cit.>. For symmetry-breaking MPS with long-range correlations, like the Greenberger-Horne-Zeilinger (GHZ) state, we require that a certain choice of boundary conditions results in a flat entanglement spectrum. 

We then define a family of MPS that do not have a flat entanglement spectrum and therefore cannot be prepared via standard fusion according to our constraints. Nevertheless, we present a generalized approach to fusion that can prepare these states in constant depth. This new approach is based on the recently developed split-index MPS (SIMPS) formalism <cit.>, which was developed to better capture certain features – including symmetry properties – of a subset of MPS. Indeed, the class of states for which we construct SIMPS fusion protocols belong to non-trivial phases of matter protected by symmetries that are not a product of single-site unitaries (i.e., non-onsite symmetries), which SIMPS are particularly suited to capturing. These symmetries are reflected in the fusion protocol, which requires application of non-onsite unitaries in the feedforward step. Furthermore, we argue that the non-onsite symmetries are the reason why MPS fusion fails for these states, thereby demonstrating that SIMPS fusion unlocks the efficient preparation of many-body states belonging to new phases of matter.

We finish by comparing MPS fusion to SIMPS fusion. We show that there are cases where both protocols work, but the SIMPS fusion protocol requires fewer measurements to prepare the same state. We also comment on how SIMPS fusion can be viewed as a kind of generalized MPS fusion with a particular choice of boundary conditions, thereby opening the general question of when two quantum states admit boundary conditions that allow deterministic fusion using measurement and feedforward.

The paper is structured as follows. We begin in Sec. <ref> by discussing the simplest deterministic, measurement-assisted fusion procedure for MPS both with and without long-range entanglement, using the AKLT and GHZ states as examples, respectively. We then derive constraints on when MPS fusion can succeed in a more general setting, in particular allowing for generalized two-qudit fusion measurements and more general kinds of unitary feedforward. Given these constraints, in Sec. <ref> we highlight two states with appealing physical properties that cannot be prepared using standard MPS fusion. We then introduce the SIMPS formalism in Sec. <ref> and show that the two examples from Sec. <ref> can be represented more efficiently as SIMPS. In Sec. <ref> we show that the two example states can be fused deterministically as SIMPS by employing a two-step fusion procedure involving feedforward corrections that have the form of FDQCs. Finally, we compare the resource requirements for MPS and SIMPS fusion in Sec. <ref>. We close with a discussion of our results and their implications.









§ FUSING MPS



We begin by reviewing how two MPS satisfying certain criteria can be deterministically fused using measurements and unitary feedforward <cit.>. Combining many such fusions in parallel allows for arbitrarily large states to be prepared deterministically and exactly using constant-depth quantum circuits, sidestepping the bounds that constrain unitary preparation protocols <cit.>. A translation-invariant MPS for N qudits on periodic boundary conditions (PBC) is defined as



    |ψ⟩ = ∑_i_1,…,i_NTr(A^i_1A^i_2⋯ A^i_N)|i_1,i_2,…,i_N⟩  ,



where A^i is a D × D matrix acting on the virtual space, and each physical index runs over i_k = 0, 1, …, d-1. The parameter D is called the MPS bond dimension. Throughout this paper, we will mainly be concerned with MPS with open boundary conditions (OBC), which we define as



    |ψ̅⟩ = 
        ∑_i_1, …, i_N 
     a,b⟨a | A^i_1 A^i_2⋯ A^i_N | b||%s⟩⟩a, i_1, i_2, …, i_N, b  ,



where we have terminated the chain at either end with a D-dimensional qudit whose states are labeled by a and b. We refer to the d- and D-dimensional qubits as the bulk and boundary qudits, respectively. 

The protocols we discuss are best illustrated using the graphical representation of MPS. The three-index tensor A is represented graphically as



    iab = A_ab^i .



The upper leg represents the physical index, and the left and right legs are the virtual indices. Then, the MPS on OBC (<ref>) is represented for N=4, as



    < g r a p h i c s >
     ,



where we have bent the virtual legs at the boundary to emphasize that they correspond to physical degrees of freedom. For notational simplicity, we will often omit the index labels.







 §.§ AKLT state



To illustrate the general features of the MPS fusion procedure, we work with the AKLT <cit.> state, studied in detail in Ref. <cit.>.
The AKLT state is defined by the following D=2 matrices for a particular physical basis of the d=3 qudits,

    A^0 = 1/√(3) X ,    
        A^1 = 1/√(3) Y ,    
        A^2 = 1/√(3) Z .



The MPS (<ref>) is a paradigmatic example of a state possessing SPT order <cit.> and hence cannot be prepared (even approximately) by a symmetry-respecting FDQC <cit.>.
The 2 ×2 symmetry of the AKLT state, which with PBC is generated by, e.g., rotation by π about the x and z axes, ∏_kexp(iπ S^x_k) and ∏_kexp(iπ S^z_k), manifests as a local symmetry of the tensor (<ref>),



    U_PPP,



up to a global phase, where P ∈{I, X, Y, Z} are the Pauli operators and, e.g., U_X = exp(iπ S^x) <cit.>. Thus, application of a unitary operator to the physical degrees of freedom can be converted via (<ref>) to Pauli operators acting in the virtual space. Equivalently, since P^2 = I, a Pauli operator acting on the right virtual leg can be pushed to the left leg (and vice versa) by the same mechanism. 

Two preexisting, disjoint AKLT states can be fused deterministically by employing a Bell measurement between the boundary qudits of the two chains and feedforward of the measurement outcomes <cit.>.
As depicted in Fig. <ref>, this fuses the two boundary legs into a single virtual leg, up to a Pauli defect, the presence of which is heralded by the measurement outcome. Using the symmetries (<ref>) of the tensor A, such defects can be paired up or pushed to the boundaries by application of U_P to the physical degrees of freedom. The initial AKLT states of size N=O(1) can be prepared, e.g., using a sequential unitary scheme <cit.>.

To generate an AKLT state on PBC, we perform the same fusion measurement on the final pair of virtual legs to close the boundaries. However, this means we no longer have any open virtual legs. 
As a result, there is nowhere to push byproducts in order to remove them.
Instead, we can use the same pushing-through operation to cancel byproducts pairwise, leaving behind at most one byproduct. The resulting MPS with one Pauli P sitting somewhere in the virtual space is a symmetry-twisted version of the AKLT state <cit.>. If we want the untwisted version, we need P=I, which can be achieved with postselection. Importantly, the amount of postselection is independent of system size, since we can keep 1/4 of experiments for all N.

A simple argument showing that the AKLT state cannot be made exactly with an FDQC comes from the fact that it has exponentially decaying correlations. This implies a nonzero correlation length, whereas any state generated by an FDQC has strictly zero correlations outside the circuit Lieb-Robinson light cone <cit.>. This demonstrates the interesting fact that, by incorporating measurements, we can construct exact states with nonzero correlation length in constant depth. Note that this argument applies even to circuits that do not respect the symmetry, but does not prohibit approximate preparation with an FDQC employing symmetry-breaking gates.









 §.§ GHZ state



Next, we illustrate the MPS-fusion approach to preparing the GHZ state. This is not the optimal way to prepare a GHZ state in terms of resource overhead, as discussed in Sec. <ref>, but it nonetheless serves as another example where MPS fusion is possible. The state is defined as,



    |GHZ⟩ = 1/√(2)(|00⋯ 0⟩ + |11⋯ 1⟩) ,

and involves a macroscopic superposition of MPS and, correspondingly, exhibits long-range correlations and entanglement. The MPS representation of the GHZ state
is constructed from the rank-1 matrices



    A^0 = |0⟩⟨ 0|,    A^1 = |1⟩⟨ 1|
          .



The GHZ MPS tensor obeys the following symmetry relations:



    XXX
        ,
            IZZ
        .



The first encodes the global symmetry ∏_i X_i of the state, while the second is physically associated with the long-range order of the state. 
Since X and Z generate all Pauli operators, the symmetries (<ref>) can be used to push any Pauli. In contrast to the AKLT example, the symmetries imply that Z operators in the virtual space can be pushed “for free,” i.e., without application of any unitary operator to the physical legs. Hence, as in Sec. <ref>, given N copies of the tensor A^i_ab interpreted as a three-qubit state |A⟩, the N-qubit GHZ state (plus two boundary qubits) can be prepared deterministically by 


[label=(*)]
    
  * fusing the interstitial legs using a Bell measurement,
    
  * pairing up or pushing to the edge any P ≠ I using (<ref>).



The initial states |A⟩ are simply three-qubit GHZ states and can be prepared in parallel unitarily.
As discussed in Ref. <cit.>, the disentangled qubits resulting from Bell measurements can be reincorporated into the N-qubit GHZ state using reset operations and entangling gates.







 §.§ Constraints on MPS fusion



Here, we derive the constraints on when MPS fusion is possible. First, we define the class of fusion protocols that we will consider. Our goal is to prepare the OBC MPS (<ref>) defined by a tensor A^i. We won't discuss the PBC case, but we note that it can be obtained from the OBC MPS with some O(1) postselection overhead, as in the AKLT example (i.e., by postselecting on the outcome of the final fusion measurement). The most general MPS that we will try to prepare by fusion is defined by the matrices,



    A^i=⊕_α=1^N_b A^i_α  ,



where A^i_α are D_α× D_α matrices (with ∑_α D_α = D). We assume that each tensor A^i_α generates a short-range entangled state, and that the states corresponding to different α are all linearly independent for sufficiently large N. Then, the MPS generated by A^i can be written as |ψ⟩ = ∑_α |ψ_α⟩ where each |ψ_α⟩ is short-range entangled and lim_N→∞⟨ψ_α|ψ_β⟩ = 0  when α≠β. We say an MPS is normal if N_b=1, and otherwise it is non-normal <cit.>.
Physically, normal MPS (like the AKLT state) have a finite correlation length, whereas non-normal MPS (like the GHZ state) have long-range correlations and long-range entanglement. Interestingly, the protocols for fusing these two distinct kinds of MPS are largely the same, as seen in the two examples shown in Sec. <ref>. 

A general MPS fusion protocol proceeds as follows. Starting with a product of many three-leg MPS tensors
of the form Eq. (<ref>),
we apply fusion measurements to pairs of neighbouring virtual legs.
The most general fusion measurements we consider will consist of applying a two-site unitary to the two virtual legs to be fused, followed by projective measurements of both legs in the computational basis. This applies the following fusion operation to the pair of legs,



    [baseline=(0,0), x=1pt, y=1pt]
             [thick] (-15, -20) – (-15, 20);
             [thick] (15, -20) – (15, 20);
             (rect) at (0, 0) [draw,thick,minimum width=40pt,minimum height=15pt,fill=opcolor,rounded corners] U;
             [above] at (-15, 20) ⟨s_1|;
             [above] at (15, 20) ⟨s_2|;
        ≡1/√(D)  [baseline=(0,0),x=1pt, y=1pt]
             [thick] (-20, -20) – (-20, 0) – (20, 0) – (20, -20);
             (rect) at (0, 0) [draw,thick,minimum width=20pt,minimum height=15pt,fill=opcolor,rounded corners] V^s⃗;



The operators V^s⃗ with s⃗≡ (s_1, s_2) are the byproduct operators that need to be pushed through the virtual space. For a Bell measurement, as in the AKLT protocol, these are the Pauli operators. In a more general case, we see from Eq. (<ref>) that the set of byproduct operators must always satisfy completeness ∑_s⃗ V^s⃗_ijV̅^s⃗_kl = D δ_ikδ_jl and orthonormality ( V^s⃗† V^s⃗')  = Dδ_s⃗s⃗'. Since V^s⃗ are orthonormal matrices, they form a basis for the space of all D × D matrices.

After the fusion measurement, the next step we allow in the protocol involves applying unitaries to the bulk qudits to push the byproducts to the boundary qudits, and then undoing the byproducts on the boundary. Since we want to undo the byproduct operators at the end, they should be unitary themselves [We remark that non-unitary operators can be applied to the boundaries using postselection. See, e.g., Ref. <cit.>.].
We also assume for now that the byproduct operators are dealt with using onsite push-through relations like the one in Eq. (<ref>), which generalizes to,



    ∑_j u^i_jA^j = VA^iV^†  ,



for some unitaries u and V. 
Using this equation, we can apply u to the physical leg of the MPS tensor to push V from one virtual leg to the other. 
In Appendix <ref> we show that identical constraints can be derived when
Eq. (<ref>) is relaxed to asymmetric push-through relations (V may be pushed to a different unitary W) and to cases where the unitary operator used to push is not translationally invariant and not a product of onsite operators.

Our goal is to constrain MPS that have enough push-through relations of the form (<ref>) to remove all possible byproduct operators resulting from the fusion measurements. The starting point for the derivation of our constraints is the MPS transfer matrix T, defined as,



    T = ∑_i A^i⊗A̅^i   .



If Eq. (<ref>) holds for some u and V, then (V⊗V̅)T(V^†⊗ V^T) = T. This implies that V⊗V̅ maps fixed-points of T to fixed-points such that,

    (V⊗V̅)Π(V^†⊗ V^T) = Π  ,

where Π=∑_α|R_α⟩⟨L_α| is the projector onto the space spanned by the fixed-points of T, where the left and right fixed-points, ⟨L_α| and |R_α⟩, respectively, are normalized such that ⟨L_α | R_β|=⟩δ_αβ. Taking the partial trace of Eq. (<ref>) over the second subsystem in the tensor product gives,

    V Π̃ V^† = Π̃  ,

where 
Π̃=Tr_2Π
is the partial trace of Π.

Now, if we have a push-through relation (<ref>) for V=V^s⃗ for all measurement outcomes s⃗, then Eq. (<ref>) implies that Π̃ commutes with all V^s⃗. Since the V^s⃗ span the space of all D× D matrices, this is only possible if Π̃ is proportional to the identity. 
Physically, this constraint has implications for the entanglement spectrum of fusible MPS.
Note that we can always write the right and left fixed-points of T in terms of matrices σ_R_α and σ_L_α, i.e., defining
|X⟩ = √(D)(σ_X⊗ I)|Ω⟩, with |Ω⟩ the D-dimensional qudit Bell state with normalization ⟨Ω | Ω|=⟩ 1.
Then, we can write,

    Π̃ = ⊕_α=1^N_bσ_R_ασ_L_α^T  .

In Appendix <ref>, we show that the spectrum of Π̃ is exactly the entanglement spectrum of the OBC MPS in the thermodynamic limit. 
Therefore, the constraint Π̃∝ I means that any fusible MPS must have a flat entanglement spectrum. This is our main result that we will use to constrain MPS fusion.

In the case of non-normal MPS fusion, the constraint Π̃∝ I has further consequences that give important intuition. From Eq. (<ref>) we deduce that the Bell states |Ω_d⟩ = d^-1/2∑_i=0^d-1 |ii⟩ and ⟨Ω_d| must be right and left fixed-points, respectively, for each diagonal block of the MPS (see Appendix <ref> for details). Normalization of the fixed-points then implies 



    Π̃ = ⊕_α=1^N_b D_α^-1 I_α  ,



with I_α the D_α× D_α identity matrix.
Hence, it is only possible to satisfy Π̃∝ I if the blocks being fused are of equal size, i.e., D_α = D/N_b for all α.
Given the deep connection between bond dimension and entanglement, this means that MPS fusion can only prepare non-normal MPS that are superpositions of short-range-entangled states, where each state has roughly the same amount of entanglement. This is true for GHZ states, where each state in the superposition is a product state, but will not be true for an example we present later.

We stress that the above constraints are only necessary conditions for fusibility; we do not attempt to provide also sufficient conditions here. For instance, we do not ask that the different correction unitaries u commute with each other, which in general means that the correction step could require a circuit depth that is linear in the number of fusion measurements.

In the rest of the paper, we show how a more general notion of fusion can be used to get around the above constraints. We remark that MPS with non-degenerate entanglement spectrum were also generated with measurements in constant depth using a different method in Ref. <cit.>.




§ EXAMPLES OF NON-FUSIBLE MPS



Having understood how potential MPS fusion protocols are constrained, we now consider a pair of examples that cannot be fused as MPS. These states are interesting for two reasons. First, they belong to phases of matter protected by exotic symmetries which are not products on onsite unitaries, which relates interesting physics involving anomalies and dualities. Second, they can also serve as resources for long-range quantum teleportation and measurement-based quantum computation like the AKLT state.



 §.§ Non-normal example


Our first example is a non-normal MPS. We consider the following state defined on PBC,



    |ϕ⟩ = 1/√(𝒩)(|++⋯ +⟩ + |C⟩)


for some N-dependent normalization factor 𝒩, where |C⟩ is the 1D cluster state <cit.>, defined as,



    |C⟩ = U_|++⋯ +⟩  ,



where |+⟩=(|0⟩+|1⟩)/√(2),  U_𝖢𝖹=∏_i=1^N _i,i+1, and = |0⟩⟨ 0|⊗ I + |1⟩⟨ 1|⊗ Z is the controlled-Z operator. Since |ϕ⟩ is a macroscopic superposition of MPS, it has long-range correlations and is non-normal. 
Because the two states in the superposition are exchanged by U_, the state |ϕ⟩ is associated with the spontaneous breaking of this symmetry, which is non-onsite in the sense that it is not a product of single-site unitaries, even after blocking. Such non-onsite symmetries are often associated with anomalies on the lattice <cit.>. We claim that any state with this property cannot be prepared with MPS fusion. Roughly speaking, any U_ symmetry-breaking state can be written as |ψ⟩ + U_|ψ⟩ for some state |ψ⟩. The state U_|ψ⟩ will generically be more entangled than the state |ψ⟩, meaning it will require a larger MPS bond dimension. Therefore, the non-normal MPS which describes the superposition of the two states will have blocks of different sizes, which we have argued above is incompatible with MPS fusion. We will make argument this more precise for the state |ϕ⟩ shortly.

The state |ϕ⟩ is also closely related to other states of interest. For instance, applying a local change of basis maps the state to another important example of an MPS: the Majumdar-Ghosh state <cit.> (see Appendix <ref>). Also, by applying the so-called Kennedy-Tasaki transformation <cit.>, we can map the state (<ref>) to (|++⋯ +⟩ + )^⊗ 2. This state is interesting since it is associated with the spontaneous breaking of a non-invertible symmetry, namely the Kramers-Wannier duality, which interchanges |++⋯ +⟩↔ <cit.>. Since the Kennedy-Tasaki transformation can be implemented by an FDQC and the Kramers-Wannier transformation <cit.>, and the latter can be implemented in constant depth with measurements and feedforward <cit.>, our protocol for preparing |ϕ⟩ also gives a constant-depth protocol for preparing (two copies of) |++⋯ +⟩ +.

We can write |ϕ⟩ as an MPS by taking a direct sum of the MPS matrices for the product state |++⋯+⟩ and |C⟩ <cit.>,



    A^0 = 1/√(2)[ 1 0 0; 0 1 1; 0 0 0 ]  ,    
        A^1 = 1/√(2)[  1  0  0;  0  0  0;  0  1 -1 ]  .



Using standard MPS technology <cit.>, we can find a parent Hamiltonian H = ∑_i h_i for |ϕ⟩ where,



    h_i = (3-X_i)(1 - Z_i-1X_iZ_i+1) - 2P_i^+(X_i-1X_i+1+Y_i-1Y_i+1)



where P_i^+=(1+X_i)/2 is the projector onto the state |+⟩ on site i. By construction, the Hamiltonian H annihilates both |++…+⟩ and the cluster state |C⟩, while all other eigenstates are separated by a gap. The Hamiltonian defined by (<ref>) is maximally local but is not symmetric under the non-onsite symmetry U_. A symmetric parent Hamiltonian can be constructed from the symmetrized local terms h_i + U_𝖢𝖹h_iU_𝖢𝖹. We could also construct a parent Hamiltonian by starting from that of the Majumdar-Ghosh state or of |++⋯ +⟩ + <cit.> and applying the transformations discussed above.

As discussed above, the two blocks of the MPS have different sizes (1 vs. 2), so we expect that MPS fusion is not possible. To show this explicitly, we compute the projector onto the fixed-point space of the MPS transfer matrix, 



    Π = |00⟩⟨ 00| + 1/2(|11⟩ + |22⟩)(⟨ 11| + ⟨ 22|)
          .



Note that, since the MPS (<ref>) is non-normal, the transfer matrix has degenerate fixed-points.
Taking the partial trace over the second subsystem Π̃ = _2Π, we obtain

    Π̃ = |0⟩⟨ 0| + 1/2 (|1⟩⟨ 1| + |2⟩⟨ 2|)   .

Since Π̃ is not equal to the identity, the entanglement spectrum of the MPS is not flat, and we see from Sec. <ref> that the state (<ref>) cannot be prepared using MPS fusion.

An alternative way to understand the failure of MPS fusion is to constrain the byproduct operators that can be pushed through the virtual space using Eq. (<ref>). Specifically, commutation of V with Π̃ enforces that V is block diagonal with the  block structure



    V= [ 1 0 0; 0 · ·; 0 · · ]  .



This is clearly not sufficient to correct for all byproduct operators that would result from a qutrit Bell measurement, which include, e.g., 𝒳 = |0⟩⟨ 1| + |1⟩⟨ 2| + |2⟩⟨ 0|.
As an example of an operator that is pushable, observe that the tensor (<ref>) obeys the symmetry A^i = W A^i W^† where,

    W = 
        [  1  0  0;  0 -1  0;  0  0 -1 ]  .





 §.§ Normal example


The second example MPS is defined by the following D=3 matrices:



    A^0 = 1/√(2)[ 1 0 0; 0 0 0; 0 1 1 ]  ,    
        A^1 = 1/√(2)[  0  1 -1; -1  0  0;  0  0  0 ]  .



A closely related example was presented in Ref. <cit.>. Like the AKLT state, the state (<ref>) is a normal MPS with non-zero correlation length, so it cannot be prepared exactly using an FDQC. The state also has computational utility, since it can act as a resource for long-range quantum teleportation and measurement-based quantum computation <cit.>.
As before, we can use the physical properties of the state to argue that it cannot be prepared via MPS fusion. 
While the non-normal MPS (<ref>) belongs to a symmetry-breaking phase of the non-onsite symmetry U_, we will show in Sec. <ref> that the normal MPS defined by Eq. (<ref>) has non-trivial SPT order protected by U_ and another 2 symmetry. In Ref. <cit.>, it was shown that SPT order with non-onsite symmetries is not associated with entanglement spectrum degeneracy. Therefore,  the results of Sec. <ref> would imply that MPS fusion is not possible.

To confirm this intuition, we can straightforwardly obtain the unique fixed-points of the transfer matrix corresponding to Eq. (<ref>),


 
    
    |L⟩   = 1/√(3)(|00⟩ + |11⟩ + |22⟩), 
    
        |R⟩   = 1/√(6)(2|00⟩ + |11⟩ + |22⟩).




Observe that, while |L⟩ is a qutrit Bell state, |R⟩ is not. We can then compute that Π̃ has the same form as in Eq. (<ref>). Hence, the entanglement spectrum is not flat, and we again deduce that the state cannot be fused as an MPS. As in the non-normal case, this can also be seen by the fact that pushable byproducts V must have a block diagonal form. In this case, the matrix W in Eq. (<ref>) corresponds to a global onsite Z symmetry since,

    ∑_j Z_ijA^j = W A^i W^†  .








§ SIMPS



The two examples of non-fusible MPS that we presented in the previous section share a common property: they possess the non-onsite symmetry U_. Symmetries played an important role in the AKLT and GHZ fusion protocols describes in Sec. <ref>, so one might expect that U_ could play a role in a fusion protocol. However, while the MPS formalism is able to capture such symmetries <cit.>, the treatment is more complicated than the case of onsite symmetries. To address this, we use the recently introduced SIMPS formalism <cit.> which is able to capture such non-onsite symmetries more elegantly than MPS can. In this section, we review SIMPS and their graphical representation and show how to convert an MPS to a SIMPS. We then describe how the SIMPS representation motivates an alternative two-step, LOCC-assisted preparation procedure that takes full advantage of the non-onsite symmetries of the states, and demonstrate this procedure for the examples presented in the previous section.

With periodic boundaries, a SIMPS defined on N qudits of local Hilbert space dimension d is <cit.>,



    |ψ⟩ = ∑_i_1, …, i_N (B^i_1 i_2 B^i_2 i_3⋯ B^i_N i_1) |i_1 i_2 ⋯ i_N⟩  ,



where B^ij is a χ^i ×χ^j matrix.
The examples that we consider have uniform χ^i = χ, referred to as the SIMPS bond dimension.
With open boundaries, 



    |ψ̅⟩ = ∑_i_1, …, i_2 
     a, b⟨a | B^i_1 i_2 B^i_2 i_3⋯ B^i_N-1 i_N | b||%s⟩⟩a, i_1 i_2 ⋯ i_N, b  ,



which includes χ-dimensional qudits at the left and right boundaries of the system indexed by a and b that run from 0 to χ-1. It is helpful to introduce a graphical description of SIMPS. We denote the four-index tensor as,



    < g r a p h i c s >



We will also make extensive use of δ-tensors, denoted by a small black circle, which enforce that all indices are in the same state in the Z-basis,



    < g r a p h i c s >



All examples that we present are expressed using the physical Z basis. 
Using (<ref>), we can depict a SIMPS with open boundaries (for N=5) as,



    < g r a p h i c s >



Each physical index is split across two adjacent SIMPS tensors B^ij.
We note an important property of δ-tensors that we will use throughout this work. Since all indices connected by a δ-tensor take the same value in the Z basis, any controlled unitary that is controlled by one of the indices can equivalently be controlled by any other index that is connected via a δ tensor. For example,

    < g r a p h i c s >
     .
 

MPS and SIMPS are equivalent in the sense that any state that can efficiently be represented as an MPS can also be efficiently represented as a SIMPS, and vice versa. This can be shown using explicit procedures to convert between MPS and SIMPS <cit.>. To convert an MPS to a SIMPS, we first write A^i=A^iP^iP^i† where P^iP^i† is the projector onto the rowspace of A^i, and P^i:ℂ^χ^i→ℂ^D is an isometry satisfying P^i†P^i=𝕀_χ^i where χ^i is the rank of A^i. Then we define the SIMPS tensor,



    B^ij=P^i†A^jP^j
          .



The SIMPS generated by the tensor B^ij is the same state as the MPS generated by A^i on periodic boundaries. On open boundaries, however, the states will differ near the boundaries, which is the important fact that enables our fusion protocols. The above procedure demonstrates the important fact that the MPS that are amenable to a SIMPS representation are those for which the matrices A^i are not full rank. 
Since the rank of A^i depends on the choice of physical basis {i}, the SIMPS bond dimension also depends on the physical basis. As a consequence, it is generally necessary to identify an ideal physical basis for fusing SIMPS.



 §.§ Non-fusible MPS as SIMPS


Now, we show how to write the two non-fusible MPS from Sec. <ref> as SIMPS. We then describe the symmetry properties of the SIMPS tensors that we will use for SIMPS fusion. We focus on the normal example and discuss the minor modifications needed to understand the non-normal example at the end.

Observe that the MPS matrices A^0 and A^1 in  Eq. (<ref>) both have rank two. Using Eq. (<ref>), we can derive the equivalent SIMPS tensor with χ=2,



    B^00   = I       B^01 = I 
    
        B^10   = X    B^11 = XZ




On periodic boundaries, this SIMPS generates the same state as the MPS in Eq. (<ref>) up to normalization. Note that all B^ij are unitary.
Later, we will view the tensor B as a four-qubit quantum state, which we call |B⟩. This state can be defined in terms of a quantum circuit,



    |B⟩ = 𝖢𝖷_13𝖢𝖢𝖹_123|+⟩_1|+⟩_2|Ω_2⟩_34  ,



where 𝖢𝖢𝖹 = I - 2|111⟩⟨ 111| is the controlled-controlled-Z operator, and 𝖢𝖷=|0⟩⟨ 0|⊗ I+ |1⟩⟨ 1|⊗ X is the controlled-X operator. Graphically, this circuit is,



    < g r a p h i c s >




From this circuit representation, we can straightforwardly show that the tensor B is invariant under the following four operations, which can be regarded as generalized push-through relations,



    < g r a p h i c s >
     ,
        < g r a p h i c s >
     ,
        < g r a p h i c s >
     ,
        < g r a p h i c s >
     .



These symmetries completely specify the state |B⟩ up to a global phase. 
From the first two symmetries, we can derive a 2×2 global symmetry of the SIMPS. 
With open boundaries, the generating symmetries are 

    U̅_Z    = Z⊗∏_k=1^N-1 Z_k⊗ Z, 
    U̅_   = X⊗∏_k=1^N-1_k,k+1⊗ X.

The symmetry U̅_ is a non-onsite symmetry that acts on the bulk qudits as an FDQC. On PBC, U_ itself is a symmetry of the state. These symmetries follow from the symmetries of the local SIMPS tensor, as depicted in Fig. <ref> for U̅_. Indeed, one of the main strengths of SIMPS versus MPS is their ability to capture such non-onsite symmetries in the same way that MPS capture onsite symmetries <cit.>. The fact that the actions of the two 2 symmetries on one of the boundary qudits anticommute indicates that this state has non-trivial SPT order under the 2×2 symmetry <cit.>. Thus the situation is similar to the AKLT state, except now one of the symmetries is non-onsite. 

The non-normal example in Eq. (<ref>) is similar. The corresponding SIMPS tensor is block diagonal in the virtual space,



    B^00   = I     B^01 = I 
    
        B^10   = I    B^11 = Z



From these tensors it follows that Eq. (<ref>) is the same except the 𝖢𝖷 operator is absent and Eq. (<ref>) is modified to,



    < g r a p h i c s >
     ,
        < g r a p h i c s >
     ,
        < g r a p h i c s >
     ,
        < g r a p h i c s >
     .



Notice that the leftmost symmetry has no Z action on the upwards-pointing leg meaning virtual Z operators can be pushed for free like in the GHZ state. Finally, U̅_ is still a symmetry of the non-normal SIMPS, but the other 2 symmetry acts only as Z on the two boundary qubits with no action in the bulk.









§ FUSING SIMPS






Now, we show how the SIMPS representation leads to a deterministic protocol for creating the non-fusible MPS in constant depth with measurements and feedforward. The key idea is as follows. Since the SIMPS representation effectively has two legs connecting each tensor [see Eq. (<ref>)], the fusion protocol consists of two steps where we first merge the upper legs connecting each tensor and then the lower legs. The protocol for the normal SIMPS is shown in Fig. <ref>. The protocol for the non-normal SIMPS is identical, except that byproduct Z operators are pushed to the boundary for free, rather than by using bulk Z's as in the normal case. We only discuss preparing the SIMPS on OBC. As for MPS, we can prepare the SIMPS on PBC by fusing the legs at the two boundaries of the SIMPS on OBC and postselecting on the outcome that has no Pauli byproduct.

We note two distinct features of SIMPS fusion as compared to MPS fusion. First, the protocol involves two distinct rounds of measurement where the correction unitaries resulting from the first round of measurements must be applied before the second round of measurements are performed. These measurements also occur on χ=2 dimensional qudits rather than the D=3 dimensional qudits that would be measured in MPS fusion. Second, the correction unitaries are not always single-site operators and instead involve two-site entangling unitaries as well. This is a consequence of the non-onsite symmetries of the SIMPS, which we are employing to push byproduct operators through the SIMPS virtual space (Fig. <ref>). 
Practically, the application of entangling correction unitaries does not drastically affect the resource requirements of the procedure
since entangling operations between degrees of freedom are already required to perform the Bell measurements.

The SIMPS fusion in these examples is non-generic in that the classical communication required in the first step is local, meaning each correction unitary only depends on nearby measurement outcomes. This should be compared to the non-local classical communication that is necessary in MPS fusion and the second step of SIMPS fusion, i.e., the correction unitaries can depend on the outcomes of arbitrarily distant measurements. In general, the first step of SIMPS fusion may also require non-local classical communication. This occurs, for example, when SIMPS fusion is used to construct GHZ states, as discussed in Sec. <ref>. It should be noted that some degree of non-local classical communication is necessary if one wants to prepare states with non-zero correlation length in constant depth <cit.>.

Finally, we remark that, because the first step of SIMPS fusion in Fig. <ref> requires only local classical communication, it can in fact be done unitarily, i.e., without measurements. Rather than measuring the qubit in the first step, we can apply a controlled unitary that implements the necessary correction unitary depending on the state of that qubit. In the particular case described in Fig. <ref>, this amounts to applying a 𝖢𝖢𝖹 operator to the qubit that would be measured and the two qubits on which the 𝖢𝖹 correction unitary acts. Since the protocol is deterministic, this will result in the desired fusion of SIMPS legs, where the qubit that would have been measured ends up in a disentangled product state. In the more general case where non-local classical communication is necessary, these controlled unitaries would be long-range and potentially many-body, making them infeasible to implement, so using measurements is preferable.










 §.§ Fusing a general family of SIMPS

The two example SIMPS discussed so far can be generalized to a larger family defined by the tensors,



    B^ij_a⃗b⃗ = X^a_ij Z^b_ij  ,



where a⃗ and b⃗ are binary d × d matrices and i,j=0,…,d-1.
In this notation, the normal SIMPS example (<ref>) has a_ij = i and b_ij = ij, while the non-normal SIMPS example (<ref>) has a_ij=0 and b_ij=ij.
The operators X and Z in (<ref>) are Paulis, but can be straightforwardly extended to shift and phase operators if χ > 2.
Observe that the first two generalized push-through relations in (<ref>) become,




    (-1)^a_ij B^ij_a⃗b⃗   = Z B^ij_a⃗b⃗ Z   , 
    
        (-1)^b_ij B^ij_a⃗b⃗   = X B^ij_a⃗b⃗ X   .





Therefore, Pauli operators can be pushed around in the virtual space by acting with the generically non-onsite symmetry operators u_ij^a⃗ or u_ij^b⃗, where u_ij^a⃗|ij⟩ = (-1)^a_ij|ij⟩ and similarly for u_ij^b⃗. The symmetries (<ref>) of the tensor B_a⃗b⃗ give rise to a 2 ×2 symmetry of the SIMPS, denoted G_a⃗b⃗=⟨ U^a⃗, U^b⃗⟩.
With OBC, this symmetry is generated by the FDQC unitaries,



    U̅^a⃗ = Z ⊗∏_k=1^N-1 u^a⃗_k,k+1⊗ Z ,   U̅^b⃗ = X ⊗∏_k=1^N-1 u^b⃗_k,k+1⊗ X.



Anticommutation of the two generators in the virtual space again implies that the state has non-trivial SPT order under G_a⃗b⃗ <cit.>.
The local symmetries (<ref>) alone are however insufficient to perform fusion.
We also require the generalization of the latter two relations in (<ref>), which become




    B^i+1,j_a⃗b⃗   = X^a_ij+a_i+1,j B^ij_a⃗b⃗ Z^b_ij+b_i+1,j, 
    
        B^i,j+1_a⃗b⃗   = X^a_ij+a_i,j+1 B^ij_a⃗b⃗ Z^b_ij+b_i,j+1,





where all addition acting on indices i,j is performed modulo d. Equipped with (<ref>) and (<ref>), we are able to perform a generalization of the fusion procedure outlined in Fig. <ref>.
We begin with disjoint SIMPS tensors constructed using a circuit resembling Eq. (<ref>).
The first step is generalized to qudits by applying the controlled gate ∑_n=0^d-1𝒳^n ⊗|n⟩⟨n| between two adjacent physical legs, and then measuring 𝒵 on the first qudit, where 𝒳 = ∑_n=0^d-1|n⟩⟨n+1| and the basis |n⟩ diagonalizes 𝒵. This has the effect of fusing the physical legs into a δ-tensor and inserting 𝒳^s, where s is the measurement outcome. Combining (<ref>) and (<ref>), we see that



    ∑_l=0^d-1𝒳^s_jl B^il_a⃗b⃗ = (-1)^b_ij(a_ij+a_i,j+s) B^ij_a⃗b⃗ X^a_ij+a_i,j+s Z^b_ij+b_i,j+s



which allows us to remove 𝒳^s by applying controlled unitaries to the remaining unmeasured qudits. Crucially, the trick in Eq. (<ref>) can be used to control the unitaries using the physical legs.
The fusion is completed by applying a qubit Bell measurement between the intervening boundary qubits and pushing any undesirable Paulis to the outer boundary degrees of freedom using the non-onsite symmetries u_ij^a⃗ and u_ij^b⃗.









§ COMPARING MPS AND SIMPS FUSION
 

We now make some comparisons between MPS and SIMPS fusion. First, we remark that SIMPS fusion is strictly more powerful than MPS fusion. This is because any MPS defined by the tensor A^i can be written as a SIMPS with B^ij=A^i, although this will in general not give the minimal SIMPS bond dimension, which would be provided by Eq. (<ref>). If MPS fusion is possible for the tensor A^i, then it is straightfoward to see that SIMPS fusion will also be possible for B^ij=A^i. The problem is that the first step of SIMPS fusion is essentially pointless in this case, resulting in wasted resources. Nevertheless, it stands that SIMPS fusion is possible whenever MPS fusion is. 

In the rest of this section, we comment on cases where SIMPS fusion and MPS fusion are both possible, but SIMPS fusion requires arbitrarily fewer ancilla qubits.
We then show how SIMPS fusion can be viewed as a type of MPS fusion with special boundary conditions.




 §.§ Resource comparison


In general, MPS fusion requires measuring two D-dimensional ancilla qudits per site, whereas SIMPS fusion requires measuring two χ-dimensional qudits but only one d-dimensional qudit per site (since one of the d-dimensional qudits becomes part of the final state). Therefore, if we measure complexity of the fusion by the size of the ancillary Hilbert space needed for each fusion, SIMPS fusion outperforms MPS fusion whenever dχ^2 < D^2.

We define the quantity Θ = log_2 D^2-log_2 dχ^2, which counts the difference in the number of ancilla qubits per site needed for MPS fusion versus SIMPS fusion (assuming that both are possible).
For almost all SIMPS with physical dimension d and bond dimension χ, the corresponding MPS bond dimension will be D=dχ. Therefore, we generically have D^2=d^2χ^2 such that Θ = log_2 d. Since d can be arbitrarily large, SIMPS fusion can be arbitrarily better than MPS fusion in terms of the number of ancillary qubits. Conversely, for a generic MPS of bond dimension D, the SIMPS bond dimension will be χ=D, such that Θ = -log_2 d and MPS fusion is more resource efficient. This suggests the intuitive idea that that generic MPS and more suited to MPS fusion whereas generic SIMPS are more suited to SIMPS fusion. 

The above argument is somewhat tenuous since generic MPS and SIMPS are not fusible, and it may be the case that the relationship between the bond dimensions of generic MPS and SIMPS is different in the case that both are fusible. Nevertheless, we can realize the large gap between MPS and SIMPS fusion explicitly with qudit GHZ states defined as,

    |GHZ_d⟩ = 1/√(d)∑_i=0^d-1|ii⋯ i⟩.

These can be realized as MPS with bond dimension D=d defined by the matrices A^i=|i⟩⟨ i|. Then, MPS fusion uses two ancillary qudits per site. Instead, we can write |GHZ_d⟩ as a χ=1 SIMPS defined by the tensor B^ij=δ_ij. Note that D=dχ (the generic case) holds here. Since χ=1, the second step of SIMPS fusion is non-existent. Therefore, SIMPS fusion uses only one ancillary qudit per site, so Θ = log_2 d. For d=2, this reproduces the resource overhead of the preparation scheme of Ref. <cit.>. We remark that, in this case, unlike the examples in Sec. <ref>, the first step of SIMPS fusion for the GHZ state involves non-local classical communication. Another family of states with Θ=log_2 d is given by qudit cluster states <cit.>, although these are somewhat trivial since they can be constructed in constant depth without measurements.



 §.§ SIMPS fusion as a form of MPS fusion
 

Since SIMPS and MPS are equivalent, it should be possible to formulate the SIMPS fusion protocol in terms of MPS. Indeed, here we show that SIMPS fusion corresponds to fusing MPS that have a very particular (and unusual) choice of open boundary conditions. First, Eq. (<ref>) says that we can decompose the SIMPS tensor B^ij in terms of the corresponding MPS tensor A^i as,

    < g r a p h i c s >

where we recall that A^i=A^iP^iP^i† by definition, so that,

    < g r a p h i c s >

Then, the SIMPS fusion protocol illustrated in Fig. <ref> can be reinterpreted as accomplishing the following transformation,

    < g r a p h i c s >

The states before and after the transformation can be viewed as MPS with a particular choice of boundary Hilbert space involving χ-dimensional qudits (rather than D-dimensional), and a particular tensor defining the boundary conditions in this Hilbert space. From the MPS representation alone, this would be a very unusual choice of boundary termination, whereas it is the most natural choice when the state is viewed as a SIMPS.







§ DISCUSSION


We presented constraints on which states can be deterministically prepared using fusion measurements on MPS. The main constraint can be summarized by the necessity of a flat entanglement spectrum. We then showed how to go beyond this constraint by instead expressing states in the SIMPS representation. This leads to a new preparation protocol which has novel properties compared to MPS fusion such as the necessity of multiple rounds of measurement and unitary corrections that have the form of FDQCs. The examples we prepared with SIMPS fusion are associated with symmetry-breaking and SPT order protected by non-onsite symmetries, and we argued that MPS fusion cannot prepare states with these physical properties, meaning that our protocol unlocks the preparation of new physical phases of matter.

Our construction can be viewed as an extension of MPS fusion that employs a particular boundary termination of the initial states. This perspective begs the question: When does there exist a boundary termination of a given many-body state such that we can deterministically fuse two states into a single longer state with LOCC? MPS fusion and SIMPS fusion represent two possible answers. We leave further exploration of this question to future work.

Another natural extension is to consider preparing higher-dimensional tensor networks like projected entangled pair states (PEPS) and the multiscale entanglement renormalization ansatz (MERA) with fusion. This has already been considered for some simple topological PEPS in Refs. <cit.>. When moving to more general models like string-net PEPS, the push-through relations are expressed in terms of matrix product operators <cit.>, and it is not clear how these relations can be leveraged to perform deterministic fusion of legs in the PEPS. We remark that it is still an open question whether string nets like the doubled Fibonnaci model can be deterministically created in constant depth with measurements <cit.>, and the generalized perspective on fusion that we have presented herein may be helpful there.

Finally, while we focused on deterministic state preparation, it is also interesting to consider the properties of the ensembles of states that result from different measurement outcomes. These so-called projected ensembles are useful for generating quantum state designs <cit.> and realizing exotic kinds of entanglement and criticality <cit.>. It would be interesting to formulate some of these phenomena in terms of ensembles of tensor network states resulting from fusion measurements.

Note added.—
The posting of this preprint to the arXiv was coordinated with simultaneous postings by Sahay and Verresen <cit.> and Smith et al. <cit.>. Both discuss the measurement-based preparation of matrix product states, and were developed independently from the work here.


OH is supported by the Air Force Office of Scientific Research under Grant FA9550-20-1-0222. DTS is supported by the Simons Collaboration on Ultra-Quantum Matter, which is a grant from the Simons Foundation (651440).







§ ENTANGLEMENT SPECTRUM OF OBC MPS
 

Here we derive a formula for the entanglement spectrum of the OBC MPS defined in Eq. (<ref>), following Ref. <cit.>. The first step is to take a non-normal MPS and write it in canonical form <cit.>, i.e.,

    A^i = ⊕_α=1^N_b A^i_α

where the matrices A^i_α in each block have dimension D_α× D_α and define normal MPS, meaning that _i_1,…,i_L A_α^i_1⋯ A_α^i_L is the space of all D_α× D_α matrices <cit.>. The OBC MPS can be written as,

    |ψ⟩ = 
        ∑_i_1, …, i_N 
     a,b⟨a | ⊕_α A_α^i_1 A_α^i_2⋯ A_α^i_N | b||%s⟩⟩a, i_1, i_2, …, i_N, b  .

If we label the basis states of the boundary Hilbert space by the blocks α, such that a takes values α_1,…,α_D_α for all α, then we can write,

    |ψ⟩ = ⊕_α=1^N_b  |ψ_α⟩

where, for each block, we have,

    |ψ_α⟩ = 
        ∑_i_1, …, i_N 
     a,b⟨a | A_α^i_1 A_α^i_2⋯ A_α^i_N | b||%s⟩⟩a, i_1, i_2, …, i_N, b
        ,

where a,b now run over the restricted set α_1,…,α_D_α. The direct sum structure appears here due to the boundary particles; each state |ψ_α⟩ is supported in a different sector of the boundary Hilbert space.
Note that each |ψ_α⟩ is a normal MPS.
Now, we can write,

    ρ^A=⊕_α=1^N_bρ^A_α  ,

where ρ^A_α = _B |ψ_α⟩⟨ψ_α| for some spatial bipartition of the system into contiguous subsystems A and B. Since each state |ψ_α⟩ is a normal MPS, one can show that,



    (ρ_α^A) ≃( √(σ_L_α^T)σ_R_α√(σ_L_α^T))



where ≃ denotes that the two sides have identical non-zero eigenvalues.
The matrices σ_L_α, σ_R_α are the left and right fixed points, respectively, of the transfer matrix corresponding to the MPS tensor A^i_α <cit.>. Since σ_L_α is invertible, ρ^A_α has the same non-zero eigenvalues as σ_R_ασ_L_α^T. Therefore, the full reduced density matrix ρ^A shares its non-zero eigenvalues with

    σ = ⊕_α=1^N_bσ_R_ασ_L_α^T  .

Thus, the non-zero eigenvalues of the entanglement spectrum are encoded in σ.

Equation (<ref>) is exactly Π̃ defined below Eq. (<ref>).
To see this, we write the MPS transfer matrix as

    T = ⊕_α,β T_αβ

where, in terms of the blocks in Eq. (<ref>),

    T_αβ = ∑_i A^i_α⊗A̅^i_β  .

Note that, for a PBC system of size N, we have ⟨ψ_α|ψ_β⟩ =  T^N_αβ. Using the assumed linear independence of the states generated by different blocks (α≠β), we obtain that this overlap is δ_αβ for N→∞, and it follows that the matrices T_αβ must have leading eigenvalue strictly less than 1 for α≠β. Therefore, we can write the fixed-point projector as,

    Π = ⊕_α,βδ_αβΠ_α ,

where Π_α=|R_α⟩⟨ L_α| is the projector onto the unique fixed-points of the block T_αα. This gives,

    Π̃ = ⊕_ασ_R_ασ_L_α^T = σ ,

as claimed. 





§ GENERALIZED PUSH-THROUGH RELATIONS





Here, we remove some of the assumptions made in the main text about the structure of the push-through relations which allows more general measurement and feedforward protocols. We then show that we can derive the same constraint of a flat entanglement spectrum as in the main text. The relations that we assume are the following,
 

    A^i_1⋯ A^i_NV = ∑_j_1,…,j_N U^i_1,…, i_N_j_1,…,j_N WA^j_1⋯ A^j_N  , 
    
        VA^i_1⋯ A^i_N = ∑_j_1,…,j_NŨ^i_1,…, i_N_j_1,…,j_N A^j_1⋯ A^j_NW̃  ,


which hold for some complete set of byproduct operators V and all N where U, W, Ũ, and W̃ (which all implicitly depend on V and N) are assumed to be unitary since they are the correction operators we need to apply. We do not assume the byproduct operators V are unitary, but we will later show that this must be true. 

These relations, shown in Fig. <ref>, mean that there are some unitary operators that can be applied to push V all the way to the left or right boundary and then annihilate it for all lengths N, thereby allowing us to prepare MPS of arbitrary length via fusion. Assuming that V can be pushed to either the left or right has practical motivation, since it means we can always push V to the nearest boundary, reducing the number of correction unitaries that we need to apply. The push-through relations in the main text (<ref>) satisfy this definition with W=W̃=V and U=Ũ=u^⊗ N. In the more general case of Eq. (<ref>), V is able change to another operator as it is pushed through the tensors, and the correction unitary U need not be translationally invariant or even onsite. The former case can occur in the most general symmetry relation for non-normal MPS, where W=VΘ and Θ is a matrix of phases in each block <cit.>, while the latter case covers systems with spatially modulated symmetries <cit.> and allows for correction unitaries that are FDQCs, as are required in SIMPS fusion.

Now we rederive the constraint of flat entanglement spectrum with these generalized assumptions. The derivation has two steps: (i) proving the entanglement spectrum is flat in each block of the MPS and (ii) proving that all blocks have equal size.




 §.§ Flat entanglement spectrum in each block



Observe that Eq. (<ref>) implies that the MPS transfer matrix satisfies



    (W⊗W̅) T^N  = T^N (V⊗V̅)
          .



Acting with ⟨Ω| on the left gives,



    ⟨Ω| T^N  = ⟨Ω| T^N (V⊗V̅)
          .



where we used the unitarity of W. Now, we can use completeness of the operators V to get,



    ⟨Ω| T^N  = ⟨Ω| T^N |Ω⟩⟨Ω|  .



In the limit of large N, T^N converges exponentially quickly to Π, the projector onto fixed points.
We therefore arrive at the constraint,



    ⟨Ω|Π = ⟨Ω | Π | Ω|⟨%s|⟩Ω  .



If ⟨Ω|Π  = λ⟨Ω| then acting with Π gives ⟨Ω|Π(1-λ) = 0. Assume for now that the MPS is normal, so N_b=1. Then, the quantum Perron-Frobenius theorem ensures that the fixed points can all be taken to be positive <cit.>. Hence, Π | Ω⟩ > 0 and it follows that λ = 1 since Π is a projector. If the MPS is not normal then we can make the same argument block-by-block. Namely, using Eq. (<ref>) and the fact that |Ω⟩∝⊕_α,βδ_αβ√(D_α) |Ω_α⟩, where |Ω_α⟩ is shorthand for the normalized D_α-dimensional qudit Bell state, we can decompose ⟨Ω | Π | Ω|∝⟩∑_α D_α⟨Ω_α | Π_α | Ω_α|$⟩ (where the implied proportionality constant is positive). Since every blockαcorresponds to a normal MPS, we see that Π_α| Ω_α⟩ > 0for allα, so the sum is positive too, and we again findλ= 1.

Therefore⟨Ω|must be a left fixed point ofT.
Using Eq. (<ref>) now gives⟨Ω|=⟨Ω|V⊗V̅, which implies thatVmust be unitary, as claimed.
If we instead used Eq. (<ref>), we would similarly find that|Ω⟩is a right fixed-point ofT. 
For normal MPS, where the fixed-points are unique, these results immediately imply a flat entanglement spectrum using Eq. (<ref>).
For non-normal MPS, using the fact thatΠhas the same block structure (<ref>), it follows that|Ω_α⟩(⟨Ω_α|) is a right (left) eigenvector of the blockΠ_α. That is, the entanglement spectrum is flat in every blockα. However, to have the full spectrum be flat, we need all blocks to have equal size. This is what we prove in the next section.



 §.§ Equal block size


Now we show that, in the case of non-normal MPS, fusion is only possible if the blocksαare all of the same sizeD_α= D/N_b. Recall that the most general MPS that we attempt to fuse are block injective:



    A^i = ⊕_α=1^N_b A_α^i


where_i_1,…,i_L A^i_1⋯A^i_Lis equal to the space of all block-diagonal matrices with the same block structure as Eq. (<ref>) forLlarger than someL_0<cit.>. 

For simplicity, we assumeL_0=1(or, alternatively,  that we have blocked at leastL_0sites). 
LetP_αbe the projector onto the states belonging to the blockα. Then,P_αA^i P_β= δ_αβ A^i_αfollows from Eq. (<ref>). Now, Eq. (<ref>) withN=1reads,



    ∑_j U^i_jA^j    = WA^iV^†  , 
    ∑_j Ũ^i_jA^j    = V A^i W̃^†



Since the left-hand side of Eq. (<ref>) is a linear combination of theA^i, it must possess the same block structure asA^i. Inserting resolutions of identity∑_αP_αinto (<ref>), we deduce that,



    ∑_β (P_α V P_β) A_β^i  (P_β W^† P_γ) = 0   ∀α≠γ.


Using the shorthand notationP_αV P_β≡V_αβ(regarded as aD_α×D_βmatrix) andP_βW^†P_γ≡(W^†)_βγ = (W_γβ)^†,
we write Eq. (<ref>) in an enlarged space 



    ⊕_β (V_αβ⊗W̅_γβ) |A_β^i⟩  = 0   ∀α≠γ.


Block injectivity requires that this equation must hold for all vectors|A_β^i⟩, and we find that the matrixV_αβ ⊗W̅_γβmust strictly vanish∀β,  α≠γ. 
We therefore arrive atV_αβ = 0orW̅_γβ = 0. Given this structure, it is convenient to parameterize the blockV_αβasv_αβ 𝕍_αβ(no sum), wherev_αβ ∈{ 0, 1 }keeps track of the zero blocks and𝕍_αβthe matrix part. Similarly, we writeW_αβ = w_αβ 𝕎_αβ.

Unitarity ofV(which was demonstrated in the previous section) implies that, for eachα,



    ∑_β V_αβ (V_αβ)^† = ∑_β (V_βα)^† V_βα = I_α  .


Therefore, at least onev_αβmust be non-zero in each row and in each column, else the sum vanishes. Suppose thatv_αβhas  exactly one nonzero entry in every row and every column. ThenV_αβ = 0orW̅_γβ = 0∀β,  α≠γuniquely fixesw_αβ = v_αβ. If one row ofv_αβcontains more than one non-zero entry thenw_αβnecessarily contains a row that vanishes, violating unitarity ofW. We deduce thatv_αβandw_αβmust be identical permutation matrices. Ifv_αβ = 1then we require,



    𝕍_αβ𝕍_αβ^† = I_α  and  𝕍_αβ^†𝕍_αβ = I_β  .


That is,𝕍_αβmust be unitary and we must haveD_α = D_β. IfD_α ≠D_βthenv_αβmust vanish and theVcannot form a complete basis forD ×Dmatrices. It follows that, if we require that theVform a complete basis, then 


[label=(*)]
    
  *  all blocks must be the same size, D_α = D/N_b
  *  the V and W take the form V = P (⊕_α V_α) and W = P (⊕_α W_α), where P is a permutation matrix that permutes blocks and V_α, W_α are unitary matrices.


We remark that the latter condition is consistent with the general push-through relations that arise from global symmetries in non-normal MPS <cit.>.



§ MAJUMDAR-GHOSH MODEL


In this Appendix we discuss the precise connections between the non-normal MPS example from Eq. (<ref>) and the Majumdar-Ghosh (MG) state <cit.>. The MG model is defined by the Hamiltonian



    H = 
        ∑_i σ_i·σ_i+1 + 1/2∑_i σ_i·σ_i+2  ,


whereσ_i = (X_i, Y_i, Z_i)is the vector of Pauli matrices. With PBC the Hamiltonian (<ref>) has two ground states corresponding to the two distinct pairings of nearest neighbors into singlets. The symmetric superposition of these ground states is often called the MG state,



    = ⊗_i |Y⟩_2i,2i+1 + ⊗_i |Y⟩_2i-1,2i ,


where|Y⟩= (iY⊗I)|Ω_2⟩= (|01⟩- |10⟩)/√(2)is the singlet Bell state. 

We now show thatis related to the state|ϕ⟩(<ref>) via a local unitary change of basis. Specifically, we have,



    ∏_i H_2iY_2i = ⊗_i |H⟩_2i,2i+1 + (-1)^N/2⊗_i |H⟩_2i-1,2i


where|H⟩= (H⊗I)|Ω_2⟩andH=(X+Z)/√(2)is the Hadamard matrix. Observe that|H⟩= |++⟩. Then, we have,



    ∏_i _2i,2i+1 H_2iY_2i 
        = |++⋯ +⟩ + (-1)^N/2|C⟩


which matches Eq. (<ref>) whenN/2is even.