Towards Minimal Resources of Measurement-based Quantum Computation
Towards Minimal Resources of Measurement-based
Quantum Computation
Simon Perdrix
PPS, CNRS - Université Paris 7
E-mail: simon.perdrix@pps.jussieu.fr
Abstract. We improve the upper bound on the minimal resources required for measurement-
based quantum computation [4, 3, 6]. Minimizing the resources required for this model is a key
issue for experimental realization of a quantum computer based on projective measurements.
This new upper bound allows also to reply in the negative to the open question presented in
[5] about the existence of a trade-off between observable and ancillary qubits in measurement-
based quantum computation.
1. Introduction
The discovery of new models of quantum computation (QC), such as the one-way quantum
computer [7] and the projective measurement-based model [4], have opened up new
experimental avenues toward the realisation of a quantum computer in laboratories. At the
same time they have challenged the traditional view about the nature of quantum computation.
Since the introduction of the quantum Turing machine by Deutsch [1], unitary
transformations plays a central rôle in QC. However, it is known that the action of unitary
gates can be simulated using the process of quantum teleportation based on projective
measurements-only [4]. Characterizing the minimal resources that are sufficient for this model
to be universal, is a key issue.
Resources of measurement-based quantum computations are composed of two
ingredients: (i) a universal family of observables, which describes the measurements that can
be performed (ii) the number of ancillary qubits used to simulate any unitary transformation.
Successive improvements of the upper bounds on these minimal resources have been
made by Leung and others [2, 3]. These bounds have been significantly reduced when the
state transfer (which is a restricted form of teleportation) has been introduced: one two-qubit
observable (Z ⊗ X) and three one-qubit observables (X , Z and (X + Y )/
2), associated
with only one ancillary qubit, are sufficient for simulating any unitary-based QC [6]. Are
these resources minimal ? In [5], a sub-family of observables (Z ⊗X , Z, and (X − Y )/
is proved to be universal, however two ancillary qubits are used to make this sub-family
universal.
These two results lead to an open question : is there a trade-off between observables and
ancillary qubits in measurement-based QC ? In this paper, we reply in the negative to this
http://arxiv.org/abs/0704.0202v1
Towards Minimal Resources of Measurement-based Quantum Computation 2
open question by proving that the sub-family {Z ⊗ X,Z, (X − Y )/
2} is universal using
only one ancillary qubit, improving the upper bound on the minimal resources required for
measurement-based QC.
2. Measurement-based QC
The simulation of a given unitary transformation U by means of projective measurements can
be decomposed into:
• (Step of simulation) First, U is probabilistically simulated up to a Pauli operator, leading
to σU , where σ is either identity or a Pauli operator σx, σy, or σz .
• (Correction) Then, a corrective strategy consisting in combinig conditionally steps of
simulation is used to obtain a non-probabilistic simulation of U .
Teleportation can be realized by two successive Bell measurements (figure 1), where a
Bell measurement is a projective measurement in the basis of the Bell states {|Bij〉}i,j∈{0,1},
where |Bij〉 = 1√
(σiz ⊗ σjx)(|00〉+ |11〉). A step of simulation of U is obtained by replacing
the second measurement by a measurement in the basis {(U † ⊗ Id)|Bij〉}i,j∈{0,1} (figure 2).
Figure 1. Bell measurement-based teleportation
ΦUσ ΦUσ
Figure 2. Simulation of U up to a Pauli operator
If a step of simulation is represented as a probabilistic black box (figure 3, left), there
exists a corrective strategy (figure 3, right) which leads to a full simulation of U . This strategy
consists in conditionally composing steps of simulation of U , but also of each Pauli operator.
A similar step of simulation and strategy are given for the two-qubit unitary transformation
ΛX (Controlled-X) in [4]. Notice that this simulation uses four ancillary qubits.
As a consequence, since any unitary transformation can be decomposed into ΛX and
one-qubit unitary transformations, any unitary transformation can be simulated by means
of projective measurements only. More precisely, for any circuit C of size n – with basis
ΛX and all one-qubit unitary transformations – and for any ǫ > 0, O(n log(n/ǫ)) projective
measurements are enough to simulate C with probability greater than 1− ǫ.
Towards Minimal Resources of Measurement-based Quantum Computation 3
Φ Φσy σz
Figure 3. Left: step of simulation abstracted into a probabilistic black box representation –
Rigth: conditional composition of steps of simulation.
Approximative universality, based on a finite family of projective measurements, can
also be considered. Leung [3] has shown that a family composed of five observables
F0 = {Z,X ⊗ X,Z ⊗ Z,X ⊗ Z, 1√
(X − Y ) ⊗ X} is approximatively universal, using
four ancillary qubits. It means that for any unitary transformation U , any ǫ > 0 and any
δ > 0, there exists a conditional composition of projective measurements from F0 leading to
the simulation of a unitary transformation Ũ with probability greater than 1− ǫ and such that
||U − Ũ || < δ.
Figure 4. State transfer
ΦUσVb
X Φ U ZU
ΦUσVVXVb
Figure 5. Step of simulation based on state transfer
In order to decrease the number of two-qubit measurements – four inF0 – and the number
of ancillary, an new scheme called state transfer has been introduced [6]. The state transfer
(figure 4) replaces the teleportation scheme for realizing a step of simulation. Composed
of one two-qubit measurements, two one-qubit measurements, and using only one ancillary
qubit, the state transfer can be used to simulate any one-qubit unitary transformation up to a
Pauli operator (figure 5). For instance, simulations ofH andHT – see section 3 for definitions
of H and T – are represented in figure 6. Moreover a scheme composed of two two-qubit
measurements, two one-qubit measurements, and using only one ancillary qubit can be used
to simulated ΛX up to a Pauli operator (figure 7). Since {H, T,ΛX} is a universal family
of unitary transformations, the family F1 = {Z ⊗ X,X,Z, 1√
(X − Y )} of observables is
approximatively universal, using one ancillary qubit [6]. This result improves the result by
Leung, since only one two-qubit measurement and one ancillary qubit are used, instead of four
two-qubit measurements and four ancillary qubits. Moreover, one can prove that at least one
Towards Minimal Resources of Measurement-based Quantum Computation 4
two-qubit measurement and one ancillary qubit are required for approximative universality.
Thus, it turns out that the upper bound on the minimal resources for measurement-based QC
differs form the lower bound, on the number of one-qubit measurements only.
b Z X
Z X−Y/  2Φ
b Z X
Figure 6. Simulation of H and HT up to a Pauli operator.
σ Λ X
Figure 7. Simulation of ΛX up to a Pauli operator.
In [5], it has been shown that the number of these one-qubit measurements can be
decreased, since the family F2 = {Z ⊗ X,Z, 1√
(X − Y )}, composed of one two-qubit
and only two one-qubit measurements, is also approximatively universal, using two ancillary
qubit. The proof is based on the simulation of X-measurements by means of Z and Z ⊗ X
measurements (figure 8). This result leads to a possible trade-off between the number
of one-qubit measurements and the number of ancillary qubits required for approximative
universality.
Figure 8. X-measurement simulation
In this paper, we meanly prove that the family F2 is approximatively universal, using
only one ancillary qubit. Thus, the upper bound on the minimal resources required for
approximative universality is improved, and moreover we answer the open question of the
trade-off between observables and ancillary qubits. Notice that we prove that the trade-off
conjectured in [5] does not exist, but another trade-off between observables and ancillary
qubits may exist since the bounds on the minimal resources for measurement-based quantum
computation are not tight.
3. Universal family of unitary transformations
There exist several universal families of unitary transformations, for instance {H, T,ΛX} is
one of them:
Towards Minimal Resources of Measurement-based Quantum Computation 5
H = 1√
, T =
, ΛX =
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 −1
We prove that the family {HT, σy,ΛZ} is also approximatively universal:
Theorem 1 U = {HT, σy,ΛZ} is approximatively universal.
The proof is based on the following properties. Let R
(α) be the rotation of the Bloch
sphere about the axis n through an angle α.
Proposition 1 If n = (a, b, c) is a real unit vector, then for any α, R
(α) = cos(α/2)I −
i sin(α/2)(aσx + bσy + cσz).
Proposition 2 For a given vector n of the Bloch sphere, if θ is an irrational multiple of π,
then for any α and any ǫ > 0, there exists k such that
(α)− R
(θ)k)|| < ǫ/3
Proposition 3 If n and m are non parallel vectors of the Bloch sphere, then for any one-
qubit unitary transformation U , there exists α, β, γ, δ such that:
U = eiαR
Proposition 4 (Włodarski [8]) If α is not an integer multiple of π/4 and cos β = cos2 α,
then either α or β is an irrational multiple of π.
Proof of theorem 1:
First we prove that any 1-qubit unitary transformation can be approximated by HT and
σyHT . Consider the unitary transformations U1 = T , U2 = HTH , U3 = σyHTHσy. Notice
that T is, up to an unimportant global phase, a rotation by π/4 radians around z axis on the
Block sphere:
U1 = T = e
−iπ/8(cos(π/8)I − i sin(π/8)σz)
U2 = HTH = e
−iπ/8(cos(π/8)I − i sin(π/8)σx)
U3 = σyHTHσy = e
−iπ/8(cos(π/8)I + i sin(π/8)σx)
Composing U1 and U2 gives, up to a global phase:
U2U1 = (cos(π/8)I − i sin(π/8)σx)(cos(π/8)I − i sin(π/8)σz)
= cos2(π/8)I − i[cos(π/8)(σx + σz)− sin(π/8)σy] sin(π/8)
Towards Minimal Resources of Measurement-based Quantum Computation 6
According to proposition 1, U2U1 is a rotation of the Bloch sphere about an axis along
n = (cos(π/8), − sin(π/8), cos(π/8)) and through an angle θ defined as a solution of
cos(θ/2) = cos2(π/8). Since π/8 is not an integer multiple of π/4 but a rational multiple
of π, according to proposition 4, a such θ is an irrational multiple of π. This irrationality
implies that for any angle α, the rotation around n about angle α can be approximated to
arbitrary accuracy by repeating rotations around n about angle θ (see proposition 3). For any
α and any ǫ > 0, there exists k such that
(α)− R
(θ)k)|| < ǫ/3
Moreover, composing U1 and U3 gives, up to a global phase:
U3U1 = (cos(π/8)I + i sin(π/8)σx)(cos(π/8)I − i sin(π/8)σz)
= cos2(π/8)I − i[cos(π/8)(−σx + σz) + sin(π/8)σy] sin(π/8)
U3U1 is a rotation of the Bloch sphere about an axis alongm = (− cos(π/8), sin(π/8), cos(π/8))
and through the angle θ. Thus, for any α and any ǫ > 0, there exists k such that
(α)− R
(θ)k)|| < ǫ/3
Since n and m are non-parallel, any one-qubit unitary transformation U , according to
proposition 2, can be decomposed into rotations around n and m : There exist α, β, γ, δ such
U = eiαR
Finally, for any U and ǫ > 0, there exist k1, k2, k3 such that
||U − R
(θ)k1R
(θ)k2R
(θ)k3 || < ǫ
Thus, any one-qubit unitary transformation can be approximated by means of U2U1, and
U3U1. Since U2U1 = (HT )(HT ) and U3U1 = σyHTHσyT = −(σyHT )(σyHT ), the family
{HT, σy} approximates any one-qubit unitary transformation.
With the additional ΛZ gate, the family U is approximatively universal. �
4. Universal family of projective measurements
In [5], the family of observables F2 = {Z ⊗ X,Z, X−Y√
} is proved to be approximatively
universal using two ancillary qubits. We prove that this family requires only one ancillary
qubit to be universal:
Theorem 2 F2 = {Z ⊗X,Z, X−Y√
} is approximatively universal, using one ancillary qubit
only.
The proof consists in simulating the unitary transformations of the universal family U .
First, one can notice that HT can be simulated up to a Pauli operator, using measurements of
F2, as it is depicted in figure 6. So, the universality is reduced to the ability to simulate ΛZ
and the Pauli operators – Pauli operators are needed to simulated σy ∈ F , but also to perform
the corrections required by the corrective strategy (figure 3).
Towards Minimal Resources of Measurement-based Quantum Computation 7
Lemma 5 For a given 2-qubit register a, b and one ancillary qubit c, the sequence of
measurements according to Zc, Za⊗Xc, Zc⊗Xb, and Zb (see figure 9) simulates ΛZ(Id⊗H)
on qubits a, b, up to a Pauli operator. The resulting state is located on qubits a and c.
Z(Id  H)Z
ZΦ Φc
Figure 9. Simulation of ΛZ(Id⊗H)
Proof: One can show that, if the state of the register a, b is |Φ〉 before the sequence of
measurements, the state of the register a, b after the measurements is σΛZ(Id⊗H)|Φ〉, where
σ = σs1z ⊗ σs3x σs2+s4z and si’s are the classical outcomes of the sequence of measurements. �
In order to simulate Pauli operators, a new scheme, different from the state transfer, is
introduced.
Lemma 6 For a given qubit b and one ancillary qubit a, the sequence of measurements Za,
Xa ⊗ Zb, and Za (figure 10) simulates, on qubit b, the application of σz with probability 1/2
and Id with probability 1/2.
Figure 10. Simulation of σ
Proof: Let |Φ〉 = α|0〉+ β|1〉 be the state of qubit b. After the first measurement, the state of
the register a, b is |ψ1〉 = (σs1x ⊗ Id)|0〉 ⊗ |Φ〉 where s1 ∈ {0, 1} is the classical outcome of
the measurement.
Since 〈ψ1|X ⊗ Z|ψ1〉 = 0, the state of the register a, b is:
|ψ2〉 =
(σs1x ⊗ Id)(Id+ (−1)s2X ⊗ Z)|0〉 ⊗ |Φ〉
(σs1x σ
z ⊗ Id)(|0〉 ⊗ |Φ〉+ |1〉 ⊗ (σz|Φ〉)
Let s3 ∈ {0, 1} be the outcome of the last measurement, on qubit a. If s1 = s3 then state
of the qubit b is |Φ〉, and σz|Φ〉 otherwise. One can prove that these two possibilities occur
with equal probabilities. �
Lemma 7 For a given qubit b and one ancillary qubit a, the sequence of measurements
, Za ⊗ Xb, and
(figure 11) simulates, on qubit b, the application of σx
with probability 1/2 and Id with probability 1/2.
Towards Minimal Resources of Measurement-based Quantum Computation 8
(X−Y)/  2 (X−Y)/  2
Figure 11. Simulation of σ
The proof of lemma 7 is similar to the proof of lemma 6.
Proof of theorem 2:
First notice that the family of unitary transformations U ′ = {HT, σy,ΛZ(I ⊗ H)} is
approximatively universal since U = {HT, σy,ΛZ} is universal.
HT and ΛZ(I⊗H) can be simulated up to a Pauli operator (lemmas 5). The universality
of the family of observables F2 = {Z ⊗ X,Z, X−Y√
} is reduced to the ability to simulate
any Pauli operators. Lemma 7 (resp. lemma 6), shows that σx (σz) can be simulated with
probability 1/2, moreover if the simulation fails, the resulting state is same as the original one.
Thus, this simulation can be repeated until a full simulation of σx (σz). Finally, σy = iσzσx
can be simulated, up to a global phase, by combining simulations of σx and σz. Thus,
F2 = {Z ⊗X,Z, X−Y√
} is approximatively universal using only one ancillary qubit. �
5. Conclusion
We have proved a new upper bound on the minimal resources required for measurement-
based QC: one two-qubit, and two one-qubit observables are universal, using one ancillary
qubit only. This new upper bound has experimental applications, but allows also to prove that
the trade-off between observables and ancillary qubits, conjectured in [5], does not exist. This
new upper bound is not tight since the lower bound on the minimal resources for this model
is one two-qubit observable and one ancillary qubit.
References
[1] D. Deutsch. Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. R.
Soc. Lond. A, 400:97–117, 1985.
[2] S. A. Fenner and Y. Zhang. Universal quantum computation with two- and three-qubit projective
measurements, 2001.
[3] D. W. Leung. Quantum computation by measurements. IJQI, 2:33, 2004.
[4] M. A. Nielsen. Universal quantum computation using only projective measurement, quantum memory, and
preparation of the 0 state. Phys. Rev. A, 308:96–100, 2003.
[5] S. Perdrix. Qubit vs observable resouce trade-offs in measurement-based quantum computation. In
proceedings of Quantum communication measurement and computing, 2004.
[6] S. Perdrix. State transfer instead of teleportation in measurement-based quantum computation.
International Journal of Quantum Information, 3(1):219–223, 2005.
[7] R. Raussendorf, D. E. Browne, and H. J. Briegel. The one-way quantum computer - a non-network model
of quantum computation. Journal of Modern Optics, 49:1299, 2002.
[8] L. Wlodarski. On the equation cosα1+cosα2 cosα3+cosα4 = 0. Ann. Univ. Sci. Budapest. Eötvös Sect.
Math., 1969.
	Introduction
	Measurement-based QC
	Universal family of unitary transformations
	Universal family of projective measurements
	Conclusion
