Search tips
Search criteria 


Logo of springeropenLink to Publisher's site
Quantum Information Processing
Quantum Inf Process. 2016; 15(3): 1043–1056.
Published online 2015 December 28. doi:  10.1007/s11128-015-1206-7
PMCID: PMC5591609

How to build a device that cannot be built


In this paper, we show how the GHZ paradox can be used to design a computing device that cannot be physically implemented within the context of classical physics, but nonetheless can be within quantum physics, i.e., in a quantum physics laboratory. This example gives an illustration of the many subtleties involved in the quantum control of distributed quantum systems. We also show how the second elementary symmetric Boolean function can be interpreted as a quantification of the nonlocality and indeterminism involved in the GHZ paradox.

Keywords: GHZ paradox, Quantum paradoxes, Quantum algorithms, Quantum computation, Quantum information, Quantum control, Distributed quantum algorithms, Quantum entanglement


This paper began with an invitation to give the Annual George Washington University Mathematics Department April Fools Day Lecture in April of 2014. After some thought, I decided what better topic to choose for the talk than how quantum mechanics makes fools of us all. For that reason, I chose to speak on the GHZ paradox, as embodied in Mermin’s machine [5].

In this paper, we show how the Greenberger–Horne–Zeilinger (GHZ) paradox can be used to design a computing device that cannot be physically implemented within the context of classical physics, but nonetheless can be within quantum physics, i.e., in a quantum physics laboratory. This example gives an illustration of the many subtleties involved in the quantum control of distributed quantum systems [8].

Corollary 1 in Sect. 6 can be interpreted as showing that the second elementary symmetric Boolean function σ2 explicitly quantifies the nonlocality and indeterminism involved in the GHZ paradox.

The device

A blueprint describing Mermin’s machine [5, 6] is shown below in Fig. 1:

Fig. 1
A blueprint of the device

As illustrated, the device consists of two different types of components, i.e., a source S, and three identical detectors, labeled A, B, and C.

The source, as illustrated below in Fig. 2, is a device that contains three objects, called particles, labeled A, B, and C, and a blue button, which, when pressed, ejects the three particles A, B, and C in the directions toward the detectors A, B, and C, respectively (Fig. 3).

Fig. 2
Source S
Fig. 3
Detector A, B, or C

Each detector, upon encountering an incoming particle, flashes either red R or green G. Moreover, each detector has a switch with two settings 0 and 1, which is randomly set at anytime before the arrival of the particle.

As stated below in the design specifications, the only switch settings of interest are those for which an odd number of the three switches is set to 1, i.e.,

equation image

No other switch settings are important, i.e., of interest.

The design specifications are as follows:

Spec 1
After all particles are detected, for switch settings 001, 010, and 100, only an odd number of the detectors flash red R.
Spec 2
After all particles are detected, for switch setting 111, only an even number of detectors flash red R.

These design specifications are subject to the following three constraints:

Constraint 1
The detectors cannot communicate with one another. (They are separated by a spacelike distance.)
Constraint 2
After being ejected from the source S, the particles can no longer communicate with one another.
Constraint 3
The particles only communicate with the detector upon impact.

It can’t be built!

Because of the above constraints, each particle must locally carry instructions telling its respective detector whether to flash red R or green G.

For example, particle A must carry a local instruction fA(sA) of the form

equation image

where cA0R or G and cA1R or G for switch settings sA = 0 or 1, respectively. In like manner, the remaining two particles B and C must carry local instructions fB(sB) and fC(sC), respectively.

Let us rename the colors R and G as R = 1 and G = 0, respectively. Thus, for each jABC, the local instruction fj(sj) is simply a Boolean function

fj:{0, 1} ⟶ {0, 1} .

It is now immediate that Specs 1 and 2 are equivalent to the following linear system of equations:


which is obviously inconsistent.

In other words, the device cannot be built! It’s simply impossible.

Oh, but it can be built!

However, within the context of quantum physics, it can actually be built, i.e., can be physically implemented.

But before we can show how this device can actually be built, we need a few definitions.

Definition 1

We define a Boolean unitary transformation as a map from {0,1}k into a group of unitary transformations. In like manner, a Boolean Hermitian operator is defined as a map from {0,1}k into an algebra of observables. If b ( = 0 or 1) and if U is a unitary transformation, then Ub will denote the Boolean unitary transformation

equation image

where I denotes the identity operator. In like manner, if Ω is an observable, then bΩ will denote the Boolean observable

equation image

where O denotes the zero operator.

Remark 1

In other words, Boolean unitary and Boolean Hermitian operators are unitary and Hermitian transformations controlled by classical bits.

Remark 2

There is much more that could be said in regard to Boolean unitary and Hermitian operators. But that would take us too far afield of the intended objectives of this paper. So the following will have to suffice: Let 𝔹 be a Boolean algebra or Boolean ring. Let 𝕌 be a unitary group, and let u denote its Lie algebra. The set 𝕌𝔹map(𝔹, 𝕌) of Boolean unitary operators forms a Lie group containing the group 𝕌 as a sub-Lie group. Moreover, the set u𝔹map(𝔹, u) of Boolean Skew Hermitian operators is the Lie algebra of 𝕌𝔹 and contains u as a sub-Lie algebra.

figure 11128_2015_1206_Figa_HTML

Let X, Y, Z, respectively, denote the Pauli spin operators


Moreover, let H denote the Hadamard gate


and let U be the single-qubit gate


A wiring diagram summarizing a physical implementation of Mermin’s machine is shown in Fig. 4.

Fig. 4
Wiring diagram of device

In this diagram, a single line indicates a wire carrying a qubit and a double line indicates a wire carrying a classical bit. The graphics

equation image

denote, respectively, a Controlled-Not and a measurement in the standard basis. Finally the graphic

denotes the Boolean gate Hsj, controlled by the classical bit sj, where sj denotes the complement of the j-th switch setting sj. In other words,

equation image

Remark 3

Please note that HZHX. Hence, if |φ is a single-qubit state, then measurement of Hsjφ with respect to the observable Z is equivalent to measurement of |φ with respect to the Boolean observable HsjZHsj=sjX+sjZ. So, each detector portion of the wiring diagram can be simplified to a local measurement with respect to the Boolean observable sjX+sjZ, for j = 1, 2, 3 (please refer to Fig. 5). In fact, each detector portion of the diagram can be even further simplified to local measurement of the GHZ state with respect to Boolean observable Us1X+s1ZU=sjY+sjX, for j = 1, 2, 3.

Fig. 5
An equivalent wiring diagram for Mermin’s machine, where Υ(sj) is the Boolean observable Υsj=sjX+sjZ

The three leftmost gates provide a preparation of the GHZ state


The local unitary1 transformation U⊗3U ⊗ U ⊗ U transforms the GHZ state into the entangled state


which will be used to control the flashing light patterns of the three detectors.2

Let even and odd denote the Hilbert subspaces of the underlying three-qubit Hilbert space spanned, respectively, by the standard basis elements labeled by bit strings of even and odd Hamming weight. It now follows from the following table:

equation image



Thus, if the switch setting is s = 111, application of each and all local detector measurements with respect to the standard basis (no matter in which temporal order) will project the state Hs1Hs2Hs3ψ into even, necessarily resulting in a standard basis state |c1c2c3 of even Hamming weight, and corresponding eigenvalues (-1)c1, (-1)c2, (-1)c3 with c1c2c3 = 0(mod2). Using the same argument for the switch settings s = 001, 010, 001, the three local detector measurements of Hs1Hs2Hs3ψ will result in a standard basis element |c1c2c3 of odd Hamming weight with corresponding eigenvalues (-1)c1, (-1)c2, (-1)c3 with c1c2c3 = 1(mod2).

Thus, using cj = 0 as the control bit instruction to flash Green G and cj = 1 as the control bit instruction to flash Red, we have shown that the device defined by the wiring diagram satisfies all the required specs and constraints.

So the device can be built after all!


So where has the impossibility argument given in Sect. 3 of this paper gone awry?

Certainly the proof in Sect. 3 of this paper of the following proposition, on which the proof of impossibility is based, is beyond reproach:

Proposition 1

There exist no Boolean functions

fA:{0, 1} ⟶ {0, 1},  fB:{0, 1} ⟶ {0, 1},  fC:{0, 1} ⟶ {0, 1}

such that

fAs1+fBs2+fCs31mod2ifs=s1,s2,s3=001,010, or100.0mod2ifs=s1,s2,s3=111

The logic is flawless.3 But the crux of the matter is that the argument of impossibility found in Sect. 3 is only as sound as the assumptions upon which it is based.

More specifically, the argument of impossibility fails because at least one of the following two tacitly assumed premises is false:

Premise 1. Reality Principle: What is measured is completely determined before it is measured (for a more refined definition of this principle and the concept of an element of reality, please refer to [1] and [7]).

Premise 2. Principle of Locality: Spacelike separated regions of spacetime are physically independent.

Remark 4

It is not clear that these are fully independent principles. For how can that which is not fully determined already be localized? Moreover, can that which is not localized already be fully determined?

The above two premises lead to the following unfounded conclusions:

Unfounded Conclusion 1. Based on Premise 1 (The Reality Principle), the detector lamp instructions fA, fB, fC must already be predetermined well-defined total functions 4 at the time of particle ejection.

Unfounded Conclusion 2. Based on Premise 2 (The Principle of Locality), the detector lamp instructions fA , fB , fC must be local. Hence, fj is a function only of the j th switch setting sj and independent of the two other switch settings.

We will show in the next section that the detector lamp instructions fA, fB, fC are neither predetermined well-defined functions before ejection, nor local independent functions.

Under the mathematical microscope

It is instructive to take a closer look at Mermin’s machine.

We will now explicitly compute the random functions fA, fB, fC. In so doing, we will find, contrary to the unfounded conclusions given in the previous section, that these functions are:

  1. Random partial functions,
  2. Global interdependent functions of the switch settings, and
  3. Not fully defined until measured by the detectors.

For reasons of transparency, it will prove more convenient to work with the equivalent wiring diagram shown in Fig. 5, where

An external file that holds a picture, illustration, etc.
Object name is 11128_2015_1206_Figb_HTML.jpg

denotes the sj-controlled gate for the Boolean observable

equation image

That this wiring diagram is equivalent to the one found in Fig. 4 follows from the fact that HZHX. Hence, measurement of Hsjψ with respect to Z is equivalent to measurement of |ψ with respect to HsjZHsj=sjX+sjZ.

We will also need to use the quantum measurement function Q, which takes as input a pair consisting of an existing quantum state and a quantum observable and then upon evaluation produces as output a pair consisting of a resulting eigenstate and the corresponding eigenvalue. For example, if ρ is a density operator representing the state of a quantum system and if Ω an observable with spectral decomposition


then on evaluation Q(ρΩ) produces


where Pj is the projection operator for the eigenspace corresponding to the eigenvalue λj.

Please note that the function Q is a random output function, very much like the random number generator found on most classical computers, except that its output is not pseudorandom, but actually truly random. A pseudorandom number generator is a predeterministic function, i.e., a function fully predefined before evaluation, which upon evaluation deterministically produces an output. On the other hand, the function Q is indeterministic,5 i.e., it is a function that is not fully defined (and not fully determined) as a function until it is evaluated.

We finally are ready to take a closer look at the implementation of Mermin’s machine, as described by the wiring diagram found in Fig. 5.

After the state preparation of the entangled state |ψ and before ejection of the particles, the detector lamp instructions fA, fB, fC are indeterministic, i.e., only partially defined (and only partially localized) by the entangled state |ψ. This is a result of the state of each individual qubit of |ψ being indeterministic, i.e., not yet fully defined, and not yet fully localized.

In Sect. 4, it was pointed out that the property that the final resulting light pattern always satisfies the machine specifications and constraints is independent of the temporal order of the detector measurements. For this reason, we focus only on the case for which the detector measurements occur in the temporal order tA < tB < tC, where tA, tB, tC denote the measurement times for detectors A, B, C, respectively.

Remark 5

The topic of the temporal order of measurements is remarkably subtle. To say that the detector light pattern is independent of the order of the measurements is counterfactual and hence physically meaningless. However, it is meaningful (not counterfactual) to say that the state specifications and constraints are met, independent of the order of measurements. On the other hand, because of relativity, there can be, for each possible temporal order, a different observer that observes the measurements in that order. The fact that each of three different observers sees the measurements in a different temporal order is not counterfactual because all observers are viewing the same measurements.

We recall that the spectral decompositions of the Pauli spin operators X and Z are, respectively,

X = (-1)0P+ + (-1)1P- and Z = (-1)0P0 + (-1)1P1 ,



and where


Notation 1

In the calculations to follow, we use the following notational convention:

equation image

An external file that holds a picture, illustration, etc.
Object name is 11128_2015_1206_Figc_HTML.jpg

At the time tA, the function fA(s1) is evaluated as follows:

equation M293

where j1 = 0 or 1, and where Tr23(|ψ〉〈ψ|) is the partial trace of |ψ〉〈ψ| over qubits 2 and 3. The resulting state of the three qubits is


An external file that holds a picture, illustration, etc.
Object name is 11128_2015_1206_Figd_HTML.jpg

At the time tB, the function fB(s2) is evaluated as follows:

equation M307

where j2 = 0 or 1, and where Tr13(|ψ〉〈ψ|) is the partial trace of |ψ〉〈ψ| over qubits 1 and 3. The resulting state of the three qubits is


An external file that holds a picture, illustration, etc.
Object name is 11128_2015_1206_Fige_HTML.jpg

At the time tC, the function fC(s3) is evaluated as follows:

equation M321

where j3 = 0 or 1, and where Tr12(|ψ〉〈ψ|) is the partial trace of |ψ〉〈ψ| over qubits 1 and 2 The resulting state of the three qubits is


Remark 6

Please note that each of the instructions fA(s), fB(s), fC(s) can only be a nonlocal function of s = (s1s2s3). For from relativity, there can be three different observers Alice, Bob, and Charlie each observing the same measurements, but each observing the same measurements in the three different temporal orders tA < tB < tC, tB < tC < tA, tC < tA < tB, respectively. If Alice observes fA as only a function of s1, so would Bob and Charlie.

We are now in a position to explicitly quantify the interdependence of the random Boolean partial functions fA, fB, fC. To do so, we will make use of the following well-known combinatorial formula [3]:

Theorem 1

Let b = (b1b2b3, …, bn) be a binary string of length n > 0. The binary expansion of the Hamming weight Wt(b) of b is given by the following formula:


where σ2k(b) denotes the 2k-th elementary symmetric function modulo 2, i.e.,


In light of the above theorem, an immediate consequence of the above measurement calculations is the following lemma and corollary:

Lemma 1

If the switch setting s = (s1s2s3) is of odd Hamming weight, then

Pj1s1Pj2s21ψlies in11Pj3s3H,


j3j1j2σ2(s) + 1 (mod2) ,

and where σ2(s) denotes the second elementary symmetric function

σ2(s) = s1s2s2s3s3s1 .


|ψ″′〉 = |ψ〉 .

Corollary 1

For a switch setting s = (s1s2s3) of odd Hamming weight, the detector lamp instructions fA, fB, fC are the random partial functions given by:


with the Boolean algebraic dependence

fA(s) + fB(s) + fC(s) = σ2(s1s2s3) + 1 (mod2) ,

where σ2 denotes the second elementary symmetric function

σ2(s1s2s3) = s1s2s2s3s3s1 .

Hence, the random Boolean instruction functions fA, fB, fC are global and interdependent partial functions, thereby refuting Unfounded Conclusions 1 and 2, found in Sect. 5 of this paper.

Remark 7

It is interesting to note that the Boolean function σ2(s1s2s3), involved in the above algebraic interdependence, in some way fully encapsulates the entire paradox. In other words, this second elementary symmetric Boolean function somehow quantifies the nonlocality and the indeterminism involved in the GHZ paradox.


We conclude with no conclusion, but with a question:

Question 1

Is quantum mechanics trying to tell us that the very fabric of reality is indeterminate, i.e., not fully defined until it is observed?


I would like to thank Jozef Przytycki and Valentina Harizanov for their gracious invitation to give the George Washington University April Fools Day Lecture in April 2014. I would like to thank John Meyers for a number of helpful discussions and Lou Kauffman for his encouragement to write up my lecture. I would also like to thank Alain Connes and Rad Balu for their helpful conversations. Finally, I would like to thank my good friend Howard Brandt for our many challenging discussions on quantum physics. This work was partially supported by NASA Grant No. NNX15AK58, by Mathematisches Forschungsinstitut Oberwolfach, by the 2015 Army Research Laboratory Faculty Research Program, and by the L-O-O-P Fund.


1It is important to note that U⊗3 is a local unitary transformation that does not change entanglement type. For a better understanding of the significance of this fact, please refer to [4].

2For a more in-depth explanation of the use of entanglement as a distributed control mechanism, please refer to [8].

3Actually, as we will see, the above proposition is a proof of the counterfactuality of the lamp instructions being total functions, and not a proof that the device cannot be built.

4A total function is a function that is defined for all possible values of its arguments. A partial function is a function defined for some of its argument values, but not necessarily all. For more information, please refer to any text on recursive function theory.

5Please note that we have avoided use of the term “nondeterministic” because this term has an entirely different meaning in the theory of computation.


1. Bub J. Interpreting the Quantum World. Cambridge: Cambridge University Press; 1997.
2. Greenberger DM, Horne M, Zeillenger A. Going beyond Bell’s theorem. In: Kafatos M, editor. Bell’s Theorem, Quantum Theory, and Conceptions of the Universe. Dordrecht: Kluwer Academic; 1989.
3. Knuth D. The Art of Computer Programming. 2. Boston: Addison-Wesley; 1981.
4. Lomonaco, S. J., Jr.: An Entangled Tale of Quantum Entanglement, AMS PSAPM, vol. 58, pp. 305–349 (2002).
5. Mermin ND. Quantum mysteries revisited. Am. J. Phys. 1990;58(750):731–734. doi: 10.1119/1.16503. [Cross Ref]
6. Mermin ND. Quantum Computer Science: An Introduction. Cambridge: Cambridge University Press; 2007.
7. Redhead M. Incompleteness, Nonlocality, and Realism: A Prolegomenon to the Philosophy of Quantum Mechanics. Oxford: Oxford University Press; 2002.
8. Yimsiriwattana, A., Lomonaco, S.J., Jr.: Generalized GHZ States and Distributed Quantum Computing, AMS CONM/381, pp. 131–147 (2005) .

Articles from Springer Open Choice are provided here courtesy of Springer