The measurement calculus

The calculus allows rewriting any pattern to a standard form where entanglement is done first, then measurements, then local corrections.

“allows the rewriting of any pattern to a standard form where entanglement is done first, then measurements, then local corrections.”

• Also stated in: § 1 Introduction · plain

  “we derive from it a simple algorithm by which any general pattern can be put into a standard form where entanglement is done first, then measurements, then corrections.”

From the generating set, the paper obtains a 14-qubit implementation for the controlled-U family.

“and a 14 qubit implementation for the controlled-U family”

The proposed calculus of local equations over one-way computing patterns preserves interpretations (is sound).

“We propose a calculus of local equations over one-way computing patterns [RBB03], which preserves interpretations”

• Also stated in: § 1 Introduction · boosted

  “We show that this calculus is sound in that it preserves the patterns interpretations.”

• cites RBB03Not checked yet

  Not checked in the free run.

Conjugating a measurement Mα_i by X_i gives M−α_i.

“X i M α i X i = M -α i (4)”

• Also stated in: § 2.1 Commands · plain

  “M α i X i = M -α i”

The paper's generating set consists of two simple patterns, each using only 2 qubits.

“Specifically, our generating set consists of two simple patterns, each one using only 2 qubits.”

The calculus exploits the fact that 1-qubit xy-measurements are closed under conjugation by Pauli operators.

“a calculus of local equations over patterns that exploits the fact that 1-qubit xy-measurements are closed under conjugation by Pauli operators.”

There is an easy proof of universality based on a family of 2-qubit patterns.

“An easy proof of universality, based on a family of 2-qubit patterns follows.”

The X and Z actions on measurements commute, so the order in which one applies them does not matter.

“Note that these two actions are commuting, since -α + π = -α -π up to 2π, and hence the order in which one applies them doesn't matter.”

From the generating set, the paper obtains a 3-qubit realisation of the Rz rotations.

“From it we obtain a 3 qubits realisation of the R z rotations”

Pattern combinations by composition and tensor product reflect the corresponding combinations of unitary operators.

“We show next that such pattern combinations reflect the corresponding combinations of unitary operators.”

Conjugating a measurement Mα_i by Z_i gives Mα+π_i.

“M α i Z i = M α+π i”

For any input state q, the sum over q' such that q → P q' of ||q'||^2 equals ||q||^2.

“Indeed one has: {q ′ |q→ P q ′ } q ′ 2 = q 2 (7”

Changing α to α + π amounts to swapping the outcomes of the measurements.

“Thus changing α to α + π amounts to swap the outcomes of the measurements”

The Z-action leaves measurements globally invariant, in the sense that |+_{α+π}, |-_{α+π} = |-_α, |+_α.

“Note that the Z-action leaves measurements globally invariant, in the sense that |+ α+π , |-α+π = |-α , |+ α .”

The pattern M α 2 is deterministic.

“Thus this pattern is indeed deterministic”

Applying the local correction X 2 on either branch makes both outputs coincide.

“However, if one applies the local correction X 2 on either of the branches ends, both outputs will be made to coincide.”

The identity t [M α i ] s = S t i [M α i ] s holds.

“t [M α i ] s = S t i [M α i ] s(6)”

The pattern M α 2 implements the identity up to a global phase.

“and implements the identity up to a global phase”

The pattern M 0 1 E 12 is not deterministic.

“Both branches end up with different outputs, so the pattern is not deterministic.”

For the pattern M 0 1 E 12, both transitions happen with equal probabilities 1 2.

“and since a + b 2 + a -b 2 = 2( a 2 + b 2 ), both transitions happen with equal probabilities 1 2 .”

H realises the Hadamard operator.

“We have just proved H = U H , that is to say H realises the Hadamard operator.”

The pattern H(2,3)J(α)(1,2) implements R_z(α).

“However, just as in the case of the R x rotation, we also have R z (α) = HJ(α) up to a global phase, hence the pattern H(2, 3)J(α)(1, 2) also implements R z (α)”

• AssumptionRests on an assumption: R_z(α) = H J(α) up to a global phase.

Reaching the standard form takes at most quadratic time in the number of instructions in P.

“Reaching the standard form takes at most quadratic time in the number of instructions in P.”

Whenever P rewrites to P' and both patterns are deterministic, U_P = U_P'.

“Because all our equations are sound, one has that whenever P ⇒ ⋆ P ′ , and both patterns are deterministic, then U P = U P ′ .”

• AssumptionRests on an assumption: All equations of the measurement calculus are sound.

Extended standardisation of the wild ∧U pattern yields a pattern with depth complexity 7.

“Figure 2 shows the dependency structure of the resulting standard pattern for ∧U, and one sees it has depth complexity 7.”

The composite pattern J(α)(2,3)•H(1,2) implements R_x(α).

“We know that R x (α) = J(α)H up to a global phase, hence the composite pattern J(α)(2, 3) • H(1, 2) implements R x (α).”

• AssumptionRests on an assumption: R_x(α) = J(α)H up to a global phase.

E ij = E ji.

“Because E ij = E ji , there are only two cases to consider:”

For all patterns P, there exists a unique standard P' such that P rewrites to P' and P' satisfies the (EMC) condition.

“One can show by a standard rewriting theory argument, that for all P, there exists a unique standard P ′ , such that P ⇒ ⋆ P ′ , and moreover P ′ satisfies the (EMC) condition.”

• Also stated in: § 8 Conclusion · plain

  “Proposition 8 (Standardisation) For all P, there exists a unique standard P ′ , such that P ⇒ ⋆ P ′ , and P ′ satisfies the (EMC) condition.”

The composite pattern J(β)(2,3)•J(α)(1,2) standardises to the pattern J(α,β).

“J(β)(2, 3) • J(α)(1, 2) = X s 2 3 M -β 2 E 23 X s 1 2 M -α 1 E 12 ⇒ EX X s 2 3 M -β 2 X s 1 2 Z s 1 3 M -α 1 E 23 E 12 ⇒ M X X s 2 3 Z s 1 3 [M -β 2 ] s 1 M -α 1 E 23 E 12”

• Also stated in: § Teleportation. · plain

  “Let us call the pattern just obtained J(α, β).”

Condition (D) is preserved under rewriting.

“Condition (D) is easily seen to be preserved under rewriting.”

If a pattern P implements a unitary U and P's command sequence has measurements only of the M_x and M_y kind, then U has a standard implementation with only independent M_x and M_y measurements, hence depth complexity at most 2.

“Lemma 6 Let P be a pattern implementing some unitary U, and suppose P's command sequence has measurements only of the M x and M y kind, then U has a standard implementation, having only independent measurements, all being of the M x and M y kind (therefore of depth complexity at most 2).”

If a pattern P implements a unitary U and P's command sequence has no dependencies, then U is in the Clifford group.

“Theorem 2 Let P be a pattern implementing some unitary U, and suppose P's command sequence doesn't have any dependencies, then U is in the Clifford group.”

The only modifications induced by rewriting concern local corrections and dependencies.

“The only induced modifications concern local corrections and dependencies.”

Under rewriting, the entanglement commands remain the same.

“Under rewriting, the computation space, inputs and outputs remain the same, and so are the entanglement commands.”

A unitary operator U is in the Clifford group iff there exists a pattern P implementing U with measurements only of the M_x and M_y kind.

“Theorem 1 Let U be a unitary operator, then U is in the Clifford group iff there exists a pattern P implementing U, having measurements only of the M x and M y kind.”

For α = π/2, the pattern X s 2 3 Z s 1 +1 3 M x 2 M y 1 E 123 implements P(π/2).

“In particular, if α = π 2 , using the extended calculus, we get the following pattern for P ( π 2 ): X s 2 3 Z s 1 +1 3 M x 2 M y 1 E 123 .”

• AssumptionRests on an assumption: R_z(α) is the same as the phase operator P(α) up to a global phase.

For all patterns P, there exist finitely many P' such that P rewrites to P'.

“Lemma 7 (Termination) For all P, there exists finitely many P ′ such that P ⇒ ⋆ P ′ .”

Unicity of the standard form is obtained because the CC free commutations and all EE commutations were dropped, giving a rigid notion of command sequence.

“Note first that unicity is obtained because we dropped the CC free commutations, and all EE commutations, thus having a very rigid notion of command sequence.”

The calculus defines a quadratic-time standardisation algorithm transforming any pattern to a standard form where entanglement is done first, then measurements, then local corrections.

“We have shown further that our calculus defines a quadratic-time standardisation algorithm transforming any pattern to a standard form where entanglement is done first, then measurements, then local corrections.”

Rewriting a pattern to standard form reveals parallelism in the pattern computation.

“Third, the rewriting of a pattern to standard form reveals parallelism in the pattern computation.”

Patterns using only Pauli measurements can only realise unitaries belonging to the Clifford group.

“patterns with no dependencies, or using only Pauli measurements, can only realise unitaries belonging to the Clifford group.”

• Also stated in: § 1 Introduction · plain

  “patterns using no dependencies, or using only the restricted class of Pauli measurements, can only realise a unitary belonging to the Clifford group.”

The extended notion of pattern obtains more efficient implementations of unitaries, in the sense of fewer qubits.

“and this obtains more efficient -in the sense of fewer qubits -implementations of unitaries.”

Patterns with no dependencies can only realise unitaries belonging to the Clifford group.

“patterns with no dependencies, or using only Pauli measurements, can only realise unitaries belonging to the Clifford group.”

• Also stated in: § 1 Introduction · plain

  “patterns using no dependencies, or using only the restricted class of Pauli measurements, can only realise a unitary belonging to the Clifford group.”

• Also stated in: § 2 Computation Patterns · plain

  “patterns without those classical dependencies can only realise unitaries that are in the Clifford group.”

After standardisation, the dependency structure is relaxed, resulting in low depth complexity.

“whereas after standardisation, the dependency structure is relaxed, resulting in low depth complexity.”

Dependencies are crucial if one wants to define a universal computing model, that is, a model where all finite-dimensional unitaries can be realised.

“Thus dependencies are crucial if one wants to define a universal computing model; that is to say a model where all finite-dimensional unitaries can be realised”

Because local corrections come last in standard form, only the output qubits will ever need corrections.

“Second, since local corrections come last, only the output qubits will ever need corrections.”

That →P is a relation and not a map reflects that measurements a priori introduce non-determinism in the evolution of quantum states.

“That it is a relation and not a map reflects the fact that measurements a priori introduce non determinism in the evolution of the quantum states.”

A deterministic pattern implements a cp-map preserving pure density operators.

“Then a deterministic pattern will implement a cp-map preserving pure density operators.”

If P 1 and P 2 respectively realise unitaries U 1 and U 2, then the composite pattern P 2 P 1 realises U 2 U 1.

“Suppose this is the case, and suppose further that P 1 and P 2 respectively realise some unitaries U 1 and U 2 , then the composite pattern P 2 P 1 realises U 2 U 1 .”

The unitaries J(α) and ∧Z form a universal set.

“Second, we know that these unitaries form a universal set [DKP04].”

• cites [DKP04]Not checked yet

  Not checked in the free run.

The patterns J(α) and ∧Z are universal.

“Proposition 5 The patterns J(α) and ∧Z are universal.”

When P is deterministic, the map U_P depends on the choice of q′ only up to a global phase.

“Note also that because P is deterministic, this map depends on the choice of q ′ only up to a global phase.”

Such cp-maps are liftings of unitary embeddings.

“From the Kraus representation theorem for cp-maps, it is easy to see that such cp-maps are liftings of unitary embeddings.”

Shifting allows the t action of a measurement to be split.

“and shifting allows to split the t action of a measurement, resulting sometimes in convenient optimisations of standard forms.”

P 2 ⊗ P 1 realises U 2 ⊗ U 1.

“A similar argument applies to the case of a tensor combination, and one has that P 2 ⊗ P 1 realises U 2 ⊗ U 1 .”

Pattern combinations correspond to combinations of their interpretations.

“With our definitions in place, we first infer that pattern combinations correspond to combinations of their interpretations.”

Conditions (D0) and (D1) ensure that a pattern can always be run meaningfully.

“Conditions (D0) and (D1) ensure that a pattern can always be run meaningfully.”

The map U_P must be a unitary embedding.

“This map U P must actually be a unitary embedding, since all quantum definable deterministic transformations are unitaries.”

• AssumptionRests on an assumption: All quantum definable deterministic transformations are unitaries.

The Pauli group is closed under conjugation by the entanglements E ij.

“very much like equations (11) and (12) express the fact that the Pauli group is closed under conjugation by the entanglements E ij .”

The measurements M α i are closed under conjugation by the Pauli group.

“They express the fact that the measurements M α i are closed under conjugation by the Pauli group”

Combining the corresponding patterns will generate patterns realising all finite-dimensional unitaries.

“Therefore, from the preceding section, we infer that combining the corresponding patterns will generate patterns realising all finite-dimensional unitaries.”

Any universal set of patterns has to include dependencies.

“From this section, we conclude in particular that any universal set of patterns has to include dependencies (by the preceding theorem)”

No set of patterns without any measurement could be a generating set.

“No set of patterns without any measurement could be a generating set”

• AssumptionRests on an assumption: Patterns without any measurement can only implement unitaries in the Clifford group.

For any 1-qubit unitary U, ∧U has the decomposition in terms of the generators J(α) given in [DKP04].

“For any 1-qubit unitary U, one has the following decomposition of ∧U in terms of the generators J(α) [DKP04]:”

• cites DKP04Not checked yet

  Not checked in the free run.

Teleportation models are embeddable in the one-way model in a very strong sense.

“This actually shows that teleportation models are embeddable in the one-way model in a very strong sense.”

Any universal set of patterns needs to use measurements M_α where α = 0 modulo π/2.

“and also needs to use measurements M α where α = 0 modulo π 2 (by the theorem before).”