Quantum state-independent contextuality requires 13 rays

Quantum state-independent contextuality requires 13 rays Adán Cabello 1 , Matthias Kleinmann 2,4 and José R Portillo 3 1 Departamento de Física Aplicada II, Universidad de Sevilla, E-41012 Sevilla, Spain 2 Department of Theoretical Physics, University of the Basque Country UPV/EHU, PO Box 644, E-48080 Bilbao, Spain 3 Departamento de Matemática Aplicada I, Universidad de Sevilla, E-41012 Sevilla, Spain E-mail: [email protected], [email protected] and [email protected] AbstractWe show that, regardless of the dimension of the Hilbert space, there exists no set of rays revealing state-independent contextuality with less than 13 rays. This implies that the set proposed by Yu and Oh in dimension three (2012 Phys. Rev. Lett. 108 030402) is actually the minimal set in quantum theory. This contrasts with the case of Kochen–Specker sets, where the smallest set occurs in dimension four. Keywords: quantum contextuality, Kochen–Specker theorem, graph theory, foundations of quantum physics 1. Introduction Fifty years ago, Kochen and Specker [1]answered the following question: Is it possible that, independently of which is the quantum state, the quantum observables each possess a definite single value, regardless of whether they are measured or not? The Kochen–Specker (KS) theorem states that this is impossible if the dimension of the underlying Hilbert space is larger than two. One consequence of this theorem is the impossibility of reproducing quantum theory in terms of noncontextual hidden variable theories, defined as those in which the outcomes are independent of the context. A context is a set of mutually compatible quantum observables. In this sense, quantum theory is said to exhibit contextuality. The original proof of the KS theorem had two other distinctive traits: (i)it only used a finite set of observables with two outcomes, where one outcome is represented by a rank-one projection onto a ray of the Hilbert space. Hereafter, as it is common in the literature, we will 4 Author to whom any correspondence should be addressed. use ray as synonym of self-adjoint rank-one projection. (ii)The set is KS-uncolorable, i.e., it is impossible to assign values 1 or 0 to each ray while respecting that two orthogonal rays cannot both have assigned 1, and 1 must be assigned to exactly one of dmutually orthogonal rays. These restrictions are motivated by the observation that orthogonal rays correspond to mutually exclusive outcomes of a sharp observable and dmutually orthogonal rays correspond to an exhaustive set of mutually exclusive outcomes for a Hilbert space of dimension d. KS-uncolorable sets of rays are called KS sets [2]. The original KS set had 117 rays in d=3, which can be grouped in 132 contexts. There have been many efforts for finding simpler sets exhibiting state-independent contextuality (SIC). For instance, Peres and Mermin realized that, by considering observables not represented by rank-one projections and replacing KS uncolorability by a similar condition, one can find very compact sets of observables in d=4 and d=8[3,4]. Still, these sets can be rewritten in terms of KS sets [5,6]. So far, it has been shown [2]that the KS set of minimum cardinality occurs in d=4 and has 18 rays [7]. It also has been proved [2]that, in d=3, the KS set with minimum cardinality has more than 22 and less than 32 rays [8]. On the other hand, the KS set with minimum number of contexts known occurs in d=6 and has seven contexts (and 21 rays)[9]. A big step was the observation that SIC based on rays does not need to rely on KS- uncolorable sets. It is enough that they lead to a state-independent violation of a noncontextuality inequality. This substantially simplifies the methods for revealing SIC in d=3. Specifically, Yu and Oh singled out one set with 13 rays in d=3[10]. The optimal stateindependent noncontextuality inequalities for this set were identified in [11]. Sets of rays having a state-independent violation of a noncontextuality inequality are called SIC sets. Recent experiments testing SIC [12–20]and an increasing number of applications, such as device-independent secure communication [21], local contextuality [22,23], Bell inequalities revealing full nonlocality [24], state-independent quantum dimension witnessing [25], and state-independent hardware certification [19], have stimulated the interest in the following question: Which is the minimal set of rays needed for SIC? It is known that, for d=3, the answer is 13 [26], but it would be well possible that the minimal set occurs in some higher dimension, as it happens for KS sets. Here we prove that this is not the case. 2. Main result The basis of our proof is a condition identified by Ramanathan and Horodecki [26,27]to be necessary for any SIC set in dimension d, namely that the orthogonality graph Gof the set of rays has fractional chromatic number ()c>Gd f. The orthogonality graph of a SIC set is the graph in which orthogonal rays are represented by adjacent vertices. A coloring of Gis an assignment of colors to the vertices such that adjacent vertices are associated with different colors. ()cG f is the infimum of a b such that vertices have a set of bassociated colors, out of a colors, where adjacent vertices have associated disjoint sets of colors. Instead of considering all possible SIC sets of size n, we rather investigate all graphs with nvertices. Then, we consider the nondegenerate orthogonal representations (ORs)of any graph G. An OR is an injection f, mapping the vertices of Gto rays, such that adjacent vertices in Gare mapped to orthogonal rays. The OR is faithful (FOR)if, conversely, any two orthogonal rays correspond to an edge of G. We denote by ()XG the smallest dimension of the Hilbert space which still admits a FORs of G. It then follows from the Ramanathan– Horodecki condition that Gis the orthogonality graph of a SIC set only if () ( ) c>XGG f. Our main results is then as follows. 2 Theorem 1. Any graph G with 12 or less vertices has () ( ) cXGG f. Hence, according to quantum theory, no SIC set with less than 13 rays exists. 3. Proof of theorem 1 We proceed by an exhaustive search for a counterexample, examining all 166 122 463 890 nonisomorphic graphs with up to 12 vertices. Applying a cascade of filters we eventually discard all graphs and prove this way theorem 1. We start by introducing the criteria for defining these filters and then explain our procedure providing intermediate results for each of the filters. We denote by V(G)and E(G)the sets of vertices and edges of G, respectively. The complement G of Gis a graph that has the same vertices while the edges are the complemented set, i.e., ( ) ÎeEG if and only if ()ÏeEG . A subgraph Sof Gis any graph with () ( )Ì V SVG and () ( ) Ì E SEG . A subgraph is induced if S is also a subgraph of G .Itisa simple observation that any (F)OR is also a (F)OR of any (induced)subgraph. Defining x analogously to X, but for ORs 5 , this proves the following. Lemma 2. By definition, () () x XGG .If S is a subgraph of G , then () ( ) x xSG . Similarly, if S is an induced subgraph of G , then () ( )XXSG . The union of two graphs È G G 12 consists of the disjoint union of the respective vertex sets and edge sets. The join + G G 12 of two graphs is the union of both graphs adding one edge between any pair ( )()( ) δv v VG VG, 12 1 2 . The graph K 1 with one vertex and no edge takes a special role in the following simple relations. Lemma 3. For two graphs G 1and G 2and {}cxÎXf,, f, we have ()[()() ] È=fG G fG fGmax , 12 1 2and ()()()+= +fG G fG fG 12 1 2 , with the exceptions () È X=KK 2 11 and () È x =KK 2 11 . Proof. For cfthe relations are well-known, see, e.g., [29], section 3.10. For Xand x and the first relation, the maximum is at least a lower bound, since any (F)OR of È G G 12 must also be a (F)OR of G 1 and of G 2 . Conversely, if at least one of the graphs has more than one vertex then also its (F)OR has at least dimension two. This (F)OR can then be transformed by a unitary rotation, such that the image of the (F)ORs of G 1 and G 2 are disjoint and also no rays are orthogonal. Hence one can combine any two (F)ORs of G 1 and G 2 to a (F)OR in the larger of the dimensions of both (F)ORs. The second relation follows at once, noting that { }( )Î+vv EG G, 12 1 2 if and only if either ( ) ÎvVG 11 and ( ) ÎvVG 22 , or vice versa, or { }()Îvv EG, 12 1 ,or { }()Îvv EG, 12 2 . Hence fis a (F)OR for + G G 12 if and only if it is a (F)OR for G 1 and G 2 , and the spans of [( ) ]f VG 1and [( ) ]f VG 2are mutually orthogonal. , These relations are useful for our purposes since they imply that, if a graph or its complement is not connected and () ( ) c>XGG f, then this must already be true for a subgraph of G. Hence in our search we only need to consider connected graphs the complement of whose are also connected. Another important consequence of lemma 3is that 5 The orthogonal rank of a graph is also sometimes denoted by x [28], but there the minimum is taken without the restriction that the OR is an injection. This yields slightly different properties. 3 () x +=+nK mK n m2 21 , where Kℓis the completely connected graph with ℓvertices [30,31]. This implies ()X+Gnm2as soon as + n KmK 21 is a subgraph of G. A weaker form of this condition is that if Kℓis a subgraph of G, then ()XGℓ . As a final ingredient to our proof, we use the seven graphs listed in table 1. If any of those graphs is an induced subgraph Sof G, then () ()XXGS applies. The values of ()XS are obtained by construction, and due to lemma 3it is sufficient to study the five graphs in figure 1. The construction is similar for all five graphs and we demonstrate the method only Figure 1. Graphs from table 1. Graphs (a)and (b)have X=5and graphs (c)–(e)have X=6. The other two graphs from table 1are obtained by adding one or two vertices to graph (a)each being connected to all other vertices. Table 1. List of graphs used for filtering via lemma 2. The graphs ¼ C aterpillark nn,, k 1are linear graphs of length k, where n v leafs are added to vertex v.= H Caterpillar2 2,2, ( ) ¼ee C i,, nm1is the circulant graph, where each vertex is connected to its e 1 th-,K, e m th-next neighbor. ⧹{ } G v is the graph Gwith one vertex removed. Selected graphs are displayed in figure 1.graph6 is a standard graph data format widely used in computer software [37]. The number X is the smallest dimension of any faithful nondegenerate orthogonal representation. The last column shows the number of graphs remaining after filtering for the induced subgraph, see main text. Graph name In figure 1graph6 X Filter Remaining H (a)Ebtw 5(3.1)124 220 ( )C i1,2 8(b)Gbijmo 5(3.2)124 216 + H K1—Fbvzw 6(3.3)4 722 C aterpillar 2 3,2 (c)Fbtzw 6(3.4)569 C aterpillar3 2,1,1 (d)Fbuzw 6(3.5)400 ()⧹{}v C i 1,2,3 11 (e)Ibgzmngjg 6(3.6)366 + H K 2 —Gzznnk 7(3.7)0 4 for the most complicated case ()⧹{}v C i 1,2,3 11 , see figure 1(e). The vertices { }4, 5, 6, 7 form the induced subgraph K 4 and, without loss of generality, we can choose () ( ) f =4 1,0,0,0,0,() ( ) f =5 0,1,0,0,0,() ( ) f =6 0,0,1,0,0, and () f =7 ( )0, 0, 0, 1, 0 . Since vertex 3 is adjacent to the vertices { }4, 5, 6 and not adjacent to vertex 7 or 8, and vertex 7 is adjacent to 8, we have () ( ) f =a3 0,0,0, ,1 with some ¹ a 0 .By similar arguments, () ( ) * f =-ba20,0,,1,1 with ¹ b 0, and, by symmetry, () ( )f =c8 , 0, 0, 0, 1 and () ( ) * f =- cd9 1 , , 0, 0, 1 , with ¹ c d,0 . Using, that vertex 1 is adjacent to the vertices { }4, 9, 3, 2 , we have () ( ) *** f =- - -dxb a10,1, ,1,1 with ∣∣=+xa11 2, and, by symmetry, () ( ) *** f =- - -cyd b10 1 , , 1 ,0,1 with ∣∣=+yc11 2 . Eventually, vertex 1 and 10 are adjacent, implying ∣∣ ∣∣++yd xb 22 =10 , which is a contradiction. However, it is straightforward to find a FOR in dimension 6, proving [( )⧹{}]X=vCi 1, 2, 3 6 11 . For all graphs with less than 13 vertices, we discard those graphs which satisfy at least one of the following filter criteria: (1)Gor G is not connected. (2.1)Ghas subgraph K ℓ , where () c Gℓ f. (2.2)Ghas subgraph +nK mK 21 , where () () c c+< +Gnm G2 1 ff and {}Îm0, 1 . (3.1)–(3.7)Ghas an induced subgraph Sfrom table 1with () ( )  c XGS f. For obvious reasons, we fall back to a computer-based proof. We use geng from the software package nauty [32,33]to generate all nonisomorphic graphs. The fractional chromatic number can be obtained by solving the linear program [29,34], () () ()     å å Î Î Î x xG xvVG maximize: subject to: 1, for all of 0 for all , 1 vVG v v v v where  are independent sets of G, i.e., sets of vertices where all vertices are mutually nonadjacent. We find optimal solutions to this program using the software package GLPK [35]and verify the correctness of the solution by applying the strong duality of linear programs, using an accuracy threshold of  = - 10 12 . We approximate the floating-point value obtained for cfby a rational number with less than òdeviation, while constraining the denominator to be not larger than n m , where nis the number vertices of Gand mis the number of maximal independent sets. This procedure always succeeds and ensures that the calculation of cfis exact, despite floating-point arithmetic being used in intermediate steps. We apply all filters (1)–(3.7)consecutively so that each filter reduces the number of candidate graphs. The numbers of graphs remaining after each step are shown in table 2, for filters (1),(2.1), and (2.2), and as a function of the number of vertices of the graph. The list of 5 66 366 graphs remaining after filter (2.2)is available in graph6-format [36]. For the filters (3.1)–(3.7), we show in table 1the total number of remaining graphs after each filter. No graph remains after applying all filters, which proves theorem 1. 4. Conclusions Contextuality is a fundamental feature of quantum observables and can be completely detached from any features of the quantum state of the system. This SIC already occurs for 5 the most elementary case of observables being sharp and having only two outcomes, one of which is nondegenerate; such observables can be represented by rays in a Hilbert space. Here we have shown that SIC with elementary observables requires at least 13 different observables by performing an exhaustive search over all cases with less observables. The Yu–Oh set is an example of such 13 observables and is already realizable on a three-level quantum system, which is the smallest quantum system allowing for contextuality. This is in contrast to the first instances of SIC, the KS sets, where the smallest set cannot be realized on a threelevel system. Therefore, fifty years after the discovery of SIC in quantum theory, we finally have the answer to the question of which is the simplest way to reveal it, i.e., which is the smallest set of elementary observables exhibiting SIC. Acknowledgments We thank the team of the Scientific Computing Center of Andalusia (CICA)for their help with the distributed computing. This work was supported by Project No. FIS2014-60843-P, ‘Advanced Quantum Information’(MINECO, Spain), with FEDER funds, the project ‘Photonic Quantum Information’(Knut and Alice Wallenberg Foundation, Sweden), the EU (ERC Starting Grant GEDENTQOPT), and by the DFG (Forschungsstipendium KL 2726/ 2-1). References [1]Kochen S and Specker E P 1967 The problem of hidden variables in quantum mechanics J. Math. Mech. 17 59 [2]PavičićM, Merlet J-P, McKay B D and Megill N D 2005 Kochen–Specker vectors J. Phys. A: Math. Gen. 38 1577 [3]Peres A 1990 Incompatible results of quantum measurements Phys. Lett. A151 107 [4]Mermin N D 1990 Simple unified form for the major no-hidden-variables theorems Phys. Rev. Lett. 65 3373 [5]Peres A 1991 Two simple proofs of the Kochen–Specker theorem J. Phys. A: Math. Gen. 24 L175 [6]Kernaghan M and Peres A 1995 Kochen–Specker theorem for eight-dimensional space Phys. Lett. A198 1 Table 2. Number of nonisomorphic graphs with 1–12 vertices. (1)–(2.2)after filtering, see main text. Order Graphs (1)(2.1)(2.2) 11100 22000 34000 411100 534810 6 156 68 2 0 71 044 662 28 0 812 346 9 888 456 0 9 2 74 668 2 47 49 2 15 954 3 10 12 005 168 11 427 97 4 9 57 88 2 98 11 1 018 997 864 9 94 403 266 9 9 869 69 1 5 765 12 165 091 172 592 163 028 488 360 19 715 979 447 5 60 500 6 [7]Cabello A, Estebaranz J M and García-Alcaine G 1996 Bell–Kochen–Specker theorem: a proof with 18 vectors Phys. Lett. A212 183 [8]Conway J H and Kochen S 1995 Quantum Theory: Concepts and Methods ed A Peres (Dordrecht: Kluwer)p 114 [9]Lisoněk P, Badziąg P, Portillo J R and Cabello A 2014 Kochen–Specker set with seven contexts Phys. Rev. A89 042101 [10]Yu S and Oh C H 2012 State-independent proof of Kochen–Specker theorem with 13 rays Phys. Rev. Lett. 108 030402 [11]Kleinmann M, Budroni C, Larsson J-Å, Gühne O and Cabello A 2012 Optimal inequalities for state-independent contextuality Phys. Rev. Lett. 109 250402 [12]Kirchmair G, Zähringer F, Gerritsma R, Kleinmann M, Gühne O, Cabello A, Blatt R and Roos C F 2009 State-independent experimental test of quantum contextuality Nature 460 494 [13]Amselem E, Rådmark M, Bourennane M and Cabello A 2009 State-independent quantum contextuality with single photons Phys. Rev. Lett. 103 160405 [14]Moussa O, Ryan C A, Cory D G and Laflamme R 2010 Testing contextuality on quantum ensembles with one clean qubit Phys. Rev. Lett. 104 160501 [15]Zu C, Wang Y-X, Deng D-L, Chang X-Y, Liu K, Hou P-Y, Yang H-X and Duan L-M 2012 Stateindependent experimental test of quantum contextuality in an indivisible system Phys. Rev. Lett. 109 150401 [16]Zhang X, Um M, Zhang J, An S, Wang Y, Deng D-L, Shen C, Duan L-M and Kim K 2013 Stateindependent experimental test of quantum contextuality with a single trapped ion Phys. Rev. Lett. 110 070401 [17]D’Ambrosio V, Herbauts I, Amselem E, Nagali E, Bourennane M, Sciarrino F and Cabello A 2013 Experimental implementation of a Kochen–Specker set of quantum tests Phys. Rev. X3011012 [18]Cañas G, Etcheverry S, Gómez E S, Saavedra C, Xavier G B, Lima G and Cabello A 2014 Experimental implementation of an eight-dimensional Kochen–Specker set and observation of its connection with the Greenberger–Horne–Zeilinger theorem Phys. Rev. A90 012119 [19]Cañas G, Arias M, Etcheverry S, Gómez E S, Cabello A, Xavier G B and Lima G 2014 Applying the simplest Kochen–Specker set for quantum information processing Phys. Rev. Lett. 113 090404 [20]Jerger M et al 2016 Contextuality without nonlocality in a superconducting quantum system arXiv:1602.00440 [21]Horodecki K, Horodecki M, Horodecki P, Horodecki R, Pawłowski M and Bourennane M 2010 Contextuality offers device-independent security (arXiv:1006.0468) [22]Cabello A 2010 Proposal for revealing quantum nonlocality via local contextuality Phys. Rev. Lett. 104 220401 [23]Liu B-H, Hu X-M, Chen J-S, Huang Y-F, Han Y-J, Li C-F, Guo G-C and Cabello A 2016 Experimental test of the free will theorem (arXiv:1603.08254) [24]Aolita L, Gallego R, Acín A, Chiuri A, Vallone G, Mataloni P and Cabello A 2012 Fully nonlocal quantum correlations Phys. Rev. A85 032107 [25]Gühne O, Budroni C, Cabello A, Kleinmann M and Larsson J-Å2014 Bounding the quantum dimension with contextuality Phys. Rev. A89 062107 [26]Cabello A, Kleinmann M and Budroni C 2015 Necessary and sufficient condition for quantum state-independent contextuality Phys. Rev. Lett. 114 250402 [27]Ramanathan R and Horodecki P 2014 Necessary and sufficient condition for state-independent contextual measurement scenarios Phys. Rev. Lett. 112 040404 [28]Cameron P J, Montanaro A, Newman M W, Severini S and Winter A 2007 On the quantum chromatic number of a graph Electr. J. Comb. 14 R81 [29]Scheinerman E R and Ullman D H 1997 Fractional Graph Theory. A Rational Approach to the Theory of Graphs (New York: Wiley) [30]Solís A 2012 Algoritmos para la Resolución del problema de representación ortogonal Master Thesis Universidad de Sevilla [31]Solís A and Portillo J R 2015 Orthogonal representation of graphs (arXiv:1504.03662) [32]McKay B D and Piperno A 2014 Practical graph isomorphism: II J. Symb. Comput. 60 94 [33]nauty and Traces http://pallini.di.uniroma1.it/ [34]Bertsimas D and Tsitsiklis J N 1997 Introduction to Linear Optimization (Belmont, MA: Athena Scientific) [35]GNU Linear Programming Kit http://gnu.org/software/glpk/ 7 [36]http://personal.us.es/josera/minSIC/sha256-digest a23b d030 d126 a3e5 44c0 f820 afcf aa9a ac31 a991 4ae1 416a 6a1a 682f 9bbe 2535 [37]McKay B D Description of graph6 and sparse6 encodings http://cs.anu.edu.au/~bdm/data/ formats.txt 8