All-versus-nothing (AVN) proofs [1--6] show the conflict between Einstein, Podolsky, and Rosen's (EPR) elements of reality [7] and the perfect correlations of some quantum states. The name of "all-versus-nothing" [8] reflects a particular feature of these proofs: If one consider a set of perfect correlations and asumes EPR elements of reality, then a subset of these correlations leads to a conclusion that is opposite of the one obtained from the complementary subset of correlations.

The perfect correlations among single qubit measurements required for AVN proofs are given by the 2n stabilizer operators of an n-qubit graph state. The possibility of experimentally preparing new classes of graph states [9--11] naturally leads to the following problem: Does a distribution of an n-qubit graph state between m parties allow an AVN proof? This problem has been solved for m = 2 [12]. Here we describe a method to decide whether a given n-qubit m-particle graph state allows an m-partite AVN proof specific for this state (i.e., which cannot be obtained using a graph state with fewer qubits) [13]. This method requires that two observables of each qubit are EPR elements of reality. This forces a series of constraints that are only satisfied by a reduced group of the graph state's stabilizer operators. We detail these requirements and apply them to decide whether some n-qubit m-particle graph states recently prepared in the laboratory [9--11] allow m-partite AVN proofs.

We also address the following problem: Given an n-qubit graph state, what is the minimum number m of parties that allows a specific m-partite AVN proof? The solution of this problem enables us to obtain all inequivalent distributions allowing AVN proofs with n < 9 qubits and an arbitrary number m of parties [13].

These results provide the tools to help experimentalists to design tests of new AVN proofs and new Bell inequalities based on these proofs [14].

[1] P. Heywood and M. L. G. Redhead, Found. Phys. 13, 481 (1983).

[2] D. M. Greenberger, M. A. Horne, and A. Zeilinger, in Bells Theorem, Quantum Theory, and Conceptions of the Universe, edited by M. Kafatos (Kluwer Academic, Dordrecht, 1989), p. 69.

[3] D. M. Greenberger, M. A. Horne, A. Shimony, and A. Zeilinger, Am. J. Phys. 58, 1131 (1990).

[4] A. Cabello, Phys. Rev. Lett. 86, 1911 (2001).

[5] A. Cabello, Phys. Rev. Lett. 87, 010403 (2001).

[6] A. Cabello, Phys. Rev. Lett. 95, 210401 (2005).

[7] A. Einstein, B. Podolsky, and N. Rosen, Phys. Rev. 47, 777 (1935).

[8] N. D. Mermin, Phys. Rev. Lett. 65, 1838 (1990).

[9] R. Ceccarelli, G. Vallone, F. De Martini, P. Mataloni, and A. Cabello, Phys. Rev. Lett. 103, 160401 (2009).

[10] W.-B. Gao, X.-C. Yao, P. Xu, O. Gühne, A. Cabello, C.-Y. Lu, C.-Z. Peng, T. Yang, Z.-B. Chen, and J.-W. Pan, arXiv:0906.3390 (2009).

[11] W.-B. Gao, C.-Y. Lu, X.-C. Yao, P. Xu, O. Gühne, A. Goebel, Y.-A. Chen, C.-Z. Peng, Z.-B. Chen, and J.-W. Pan, Nat. Phys. 6, 331 (2010).

[12] A. Cabello and P. Moreno, Phys. Rev. Lett. 99, 220402 (2007).

[13] A. Cabello and P. Moreno, Phys. Rev. A 81, 042110 (2010).

[14] A. Cabello, O. Gühne, and D. Rodríguez, Phys. Rev. A 77, 062106 (2008).