# Local hidden variable values without optimization procedures

1Departamento de Física, Facultad de Ciencias Básicas, Universidad de Antofagasta, Casilla 170, Antofagasta, Chile
2Institute of Theoretical Physics, Jagiellonian University, ul. Łojasiewicza 11, 30-348 Kraków, Poland
3Department of Mathematics, Faculty of Science, University of Ostrava, 701 03 Ostrava, Czech Republic
4School of Electronic and Electrical Engineering, University of Leeds, Leeds LS2 9JT, UK
5Center for Theoretical Physics, Polish Academy of Sciences, Al. Lotników 32/46, 02-668 Warsaw, Poland

### Abstract

The problem of computing the local hidden variable (LHV) value of a Bell inequality plays a central role in the study of quantum nonlocality. In particular, this problem is the first step towards characterizing the LHV polytope of a given scenario. In this work, we establish a relation between the LHV value of bipartite Bell inequalities and the mathematical notion of excess of a matrix. Inspired by the well developed theory of excess, we derive several results that directly impact the field of quantum nonlocality. We show infinite families of bipartite Bell inequalities for which the LHV value can be computed exactly, without needing to solve any optimization problem, for any number of measurement settings. We also find tight Bell inequalities for a large number of measurement settings.

Quantum non-locality is a fundamental property of nature, inequivalent to quantum entanglement. These two non-classical resources have several practical applications. For instance, quantum non-locality is useful to generate genuine random numbers and to define protocols that can be certified without relying on the measurement devices, so-called device independent quantum protocols. Bell inequalities, associated with a given multipartite physical system and a measurement scheme, provide rigorous criteria allowing us to detect quantum non-locality. Any such inequality can be characterized by two positive real numbers $C$ and $Q$, defined as the maximal value that the analyzed function can take when local strategies are implemented in the classical and quantum setups, respectively. The number $C$ is called the local hidden variable (LHV) value, as it corresponds to local theories. By construction one has $C \le Q$. In several cases $C$ is strictly smaller than $Q$, and confirming this in an experiment provides an evidence that the quantum theory is essentially non-local. The task of finding the LHV value $C$ is hard in general, as it requires a large computational power. In this work, we shed some light on this issue by establishing a one-to-one correspondence between the LHV value and the notion of $\textit{maximal excess}$ of a matrix — a well-developed concept in mathematics, extensively studied for the last five decades. As a consequence, we determine the LHV value for infinitely many Bell inequalities, for any number of measurement settings per party. We also generalize the mathematical notion of maximal excess and extend the validity of some properties of the excess of Hadamard matrices to a larger class of complex matrices of any order.

### ► References

[1] J. Bell, On the Einstein Podolsky Rosen paradox, Physics 1, 3, 195 (1964).
https:/​/​doi.org/​10.1103/​PhysicsPhysiqueFizika.1.195

[2] A. Einstein, B. Podolsky, N. Rosen, Can Quantum-Mechanical Description of Physical Reality Be Considered Complete? Phys. Rev. 47, 777 (1935).
https:/​/​doi.org/​10.1103/​PhysRev.47.777

[3] R. Cleve and H. Buhrmann, Substituting quantum entanglement for communication, Phys. Rev. A 56, 1201 (1997).
https:/​/​doi.org/​10.1103/​PhysRevA.56.1201

[4] T.S. Cubitt, D. Leung. W. Matthews, A. Winter, Improving zero-error classical communication with entanglement, IEEE Transf. Theory 57(8), 5509 (2011).
https:/​/​doi.org/​10.1103/​PhysRevLett.104.230503

[5] Y. Liu et al., Experimental measurement-device-independent quantum key distribution, Phys. Rev. Lett. 111, 13, 130502 (2013).
https:/​/​doi.org/​10.1103/​PhysRevLett.111.130502

[6] T.F. da Silva et al., Proof-of-principle demonstration of measurement-device-independent quantum key distribution using polarization qubits, Phys. Rev. A 88, 052303 (2013).
https:/​/​doi.org/​10.1103/​PhysRevA.88.052303

[7] J. Barrett, L. Hardy, A. Kent, No signaling and quantum key distribution, Phys. Rev. Lett. 95, 010503 (2005).
https:/​/​doi.org/​10.1103/​PhysRevLett.95.010503

[8] A. Acín, N. Gisin, Ll. Masanes, From Bell's theorem to secure quantum key distribution, Phys. Rev. Lett. 97, 120405 (2006).
https:/​/​doi.org/​10.1103/​PhysRevLett.97.120405

[9] A. Acín, N. Brunner, N. Gisin, S. Massar, S. Pironio, V. Scarani, Device-independent security of quantum cryptography against collective attacks, Phys. Rev. Lett. 98, 230501 (2007).
https:/​/​doi.org/​10.1103/​PhysRevLett.98.230501

[10] Ll. Masanes, S. Pironio, A. Acín, Secure device-independent quantum key distribution with causally independent measurement devices, Nature Comm. 2, 238 (2011).
https:/​/​doi.org/​10.1038/​ncomms1244

[11] S. Pironio, Ll. Masanes, A. Leverrier, A. Acín, Security of device-independent quantum key distribution in the bounded-quantum-storage model, Phys. Rev. X, 3, 031007 (2013).
https:/​/​doi.org/​10.1103/​PhysRevX.3.031007

[12] U. Vazirani, T. Vidick, Fully device-independent quantum key distribution, Phys. Rev. Lett. 113, 140501 (2014).
https:/​/​doi.org/​10.1103/​PhysRevLett.113.140501

[13] J. Kaniewski, S. Wehner, Device-independent two-party cryptography secure against sequential attacks, New J. Phys. 18, 5, 055004 (2016).
https:/​/​doi.org/​10.1088/​1367-2630/​18/​5/​055004

[14] R. Colbeck, Quantum and relativistic protocols for secure multi-party computation, Ph.D. thesis, University of Cambridge (2007), arXiv:0911.3814 [quant-ph].
https:/​/​doi.org/​10.48550/​arXiv.0911.3814
arXiv:0911.3814

[15] R. Colbeck, A. Kent, Private randomness expansion with untrusted devices, J. Phys. A: Math. Theor. 44, 095305 (2011).
https:/​/​doi.org/​10.1088/​1751-8113/​44/​9/​095305

[16] S. Pironio et al., Random Numbers Certified by Bell's Theorem, Nature 464, 1021 (2010).
https:/​/​doi.org/​10.1038/​nature09008

[17] R. Colbeck, R. Renner, Free randomness can be amplified,Nature Physics 8, 450 (2012).
https:/​/​doi.org/​10.1038/​nphys2300

[18] D. Alsina, J.I. Latorre, Experimental test of Mermin inequalities on a five-qubit quantum computer, Phys. Rev. A 94, 012314 (2016).
https:/​/​doi.org/​10.1103/​PhysRevA.94.012314

[19] D. García Martín, G. Sierra, Five experimental tests on the 5-Qubit IBM quantum computer, J. Appl. Math. Phys. 6(7), 1460 (2018).
https:/​/​doi.org/​10.4236/​jamp.2018.67123

[20] A. Smith, M.S. Kim, F. Pollmann, J. Knolle, Simulating quantum many-body dynamics on a current digital quantum computer, npj Quantum Inf 5, 106 (2019).
https:/​/​doi.org/​10.1038/​s41534-019-0217-0

[21] M. Herrero-Collantes, J.C. Garcia-Escartin, Quantum random number generators, Rev. Mod. Phys. 89, 015004 (2017).
https:/​/​doi.org/​10.1103/​RevModPhys.89.015004

[22] N. Gisin, G. Ribordy, W. Tittel, H. Zbinden, Quantum cryptography, Rev. Mod. Phys. 74, 145 (2002).
https:/​/​doi.org/​10.1103/​RevModPhys.74.145

[23] N. Brunner, Device-Independent Quantum Information Processing, in Research in Optical Sciences, OSA Technical Digest (online), Optical Society of America, paper QW3A.2 (2014).
https:/​/​doi.org/​10.1364/​QIM.2014.QW3A.2

[24] P. Diviánszky, E. Bene, T. Vértesi, Qutrit witness from the Grothendieck constant of order four, Phys. Rev. A 96, 012113 (2017).
https:/​/​doi.org/​10.1103/​PhysRevA.96.012113

[25] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, S. Wehner, Bell nonlocality, Rev. Mod. Phys. 86, 419 (2014).
https:/​/​doi.org/​10.1103/​RevModPhys.86.419

[26] D. Rosset, J.-D. Bancal, N. Gisin, Classifying 50 years of Bell inequalities, J. Phys. A: Math.& Theor. 47, 424022 (2014).
https:/​/​doi.org/​10.1088/​1751-8113/​47/​42/​424022

[27] K.W. Schmidt, Problem 863, Math. Mag. 46, 103 (1973).
https:/​/​doi.org/​10.2307/​2688271

[28] M. Best, The excess of a Hadamard matrix, Indag. Math. 39, 357 (1977).
https:/​/​doi.org/​10.1016/​1385-7258(77)90049-X

[29] M. Araújo, F. Hirsch, M.T. Quintino, Bell nonlocality with a single shot.Quantum, 4, 353 (2020).
https:/​/​doi.org/​10.22331/​q-2020-10-28-353

[30] K.F. Pál, T. Vértesi, Platonic Bell inequalities for all dimensions. Quantum, 6, 756 (2022).
https:/​/​doi.org/​10.22331/​q-2022-07-07-756

[31] K.W. Schmidt, E.T.H. Wang, The weights of Hadamard matrices, J. Combin. Theory Ser. A 23, 257 (1977).
https:/​/​doi.org/​10.1016/​0097-3165(77)90017-6

[32] N. Farmakis, S. Kounias, The excess of Hadamard matrices and optimal designs, Discr. Math. 67, 2 165 (1987).
https:/​/​doi.org/​10.1016/​0012-365X(87)90025-2

[33] S. Kounias, N. Farmakis, On the excess of Hadamard matrices, Discr. Math. 68, 1 59 (1988).
https:/​/​doi.org/​10.1016/​0012-365X(88)90041-6

[34] C. Koukouvinos. J. Seberry, Hadamard matrices of order 8 (mod 16) with maximal excess, Discr. Math. 92, 1, 3, 173 (1991).
https:/​/​doi.org/​10.1016/​0012-365X(91)90278-A

[35] H. Kharaghani, An infinite class of Hadamard matrices of maximal excess, Discr. Math. 89, 3, 307 (1991).
https:/​/​doi.org/​10.1016/​0012-365X(91)90123-J

[36] T. Xia, M. Xia, J. Seberry, Regular Hadamard matrix, maximum excess and SBIBD, Australas. J. Comb. 27, 263 (2003).

[37] J.F. Clauser, M.A. Horne, A. Shimony, R.A. Holt, Proposed experiment to test local hidden-variable theories, Phys. Rev. Lett. 23, 880 (1969).
https:/​/​doi.org/​10.1103/​PhysRevLett.23.880

[38] A. Fine, Hidden variables, joint probability, and the Bell inequalities, Phys. Rev. Lett. 48, 291 (1982).
https:/​/​doi.org/​10.1103/​PhysRevLett.48.291

[39] A. Aspect, P. Grangier, G. Roger, Experimental tests of realistic local theories via Bell's theorem, Phys. Rev. Lett. 47, 460 (1981).
https:/​/​doi.org/​10.1103/​PhysRevLett.47.460

[40] A. Salavrakos, R. Augusiak, J. Tura, P. Wittek, A. Acín, S. Pironio, Bell inequalities tailored to maximally entangled states, Phys. Rev. Lett. 119, 040402 (2017).
https:/​/​doi.org/​10.1103/​PhysRevLett.119.040402

[41] M. Naimark, Spectral functions of a symmetric operator, Izv. Akad. Nauk SSSR Ser. Mat. 4, 277318 (1940).
https:/​/​www.mathnet.ru/​eng/​im/​v4/​i3/​p277

[42] S. Popescu, D. Rohrlich, Quantum nonlocality as an axiom, Found. Phys. 24, 379 (1994).
https:/​/​doi.org/​10.1007/​BF02058098

[43] R. Craigen, H. Kharaghani, Weaving Hadamard matrices with maximum excess and classes with small excess, J. Comb. Designs 12, 4, 233 (2004).
https:/​/​doi.org/​10.1002/​jcd.20012

[44] H. Kharaghani, J. Seberry, The excess of complex Hadamard matrices, Graphs Combin. 9, 47 (1993).
https:/​/​doi.org/​10.1007/​BF01195326

[45] J. Ford, A. Gál, Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity, In Proc. 32nd International Conference on Automata, Languages and Programming (ICALP'05), 1163, (2005).
https:/​/​doi.org/​10.1007/​11523468_94

[46] J. Hammer, R. Levingston, J. Seberry, A remark on the excess of Hadamard matrices and orthogonal designs, Ars Comb. 5, 237 (1978).
https:/​/​ro.uow.edu.au/​infopapers/​984/​

[47] S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and the hardness of approximation problems, J. ACM, 45(3), 501, (1998).
https:/​/​doi.org/​10.1145/​278298.278306

[48] M. Epping, H. Kampermann, D. Bruß, Designing Bell inequalities from a Tsirelson bound, Phys. Rev. Lett. 111, 240404 (2013).
https:/​/​doi.org/​10.1103/​PhysRevLett.111.240404

[49] J. de Vicente, Simple conditions constraining the set of quantum correlations, Phys. Rev. A 92, 032103 (2015).
https:/​/​doi.org/​10.1103/​PhysRevA.92.032103

[50] N. Linden, S. Popescu, A.J. Short, A. Winter, Quantum nonlocality and beyond: limits from nonlocal computation, Phys. Rev. Lett. 99, 180502 (2007).
https:/​/​doi.org/​10.1103/​PhysRevLett.99.180502

[51] R. Ramanathan, A. Kay, G. Murta, P. Horodecki, Characterising the performance of XOR games and the Shannon capacity of graphs, Phys. Rev. Lett. 113, 240401 (2014).
https:/​/​doi.org/​10.1103/​PhysRevLett.113.240401

[52] M. Hall, Hadamard Matrices of order 16, J.P.L. Research Summary 1, 36–10, 21 (1961).

[53] H.J. Ryser, Combinatorial mathematics, Willey, New York (1963).

[54] W.P. Orrick, B. Solomon, Large-determinant sign matrices of order $4k+1$, Discr. Math. 307, 2, 226 (2007).
https:/​/​doi.org/​10.1016/​j.disc.2006.04.041

[55] B. Jenkins, C. Koukouvinos, S. Kounias, J. Seberry, R. Seberry, Some results on the excesses of Hadamard matrices, J. Comb. Math. Comput. 4, 155 (1988).

[56] K. Momihara, S. Suda, Conference matrices with maximum excess and two-intersection sets, Integers 17, A30 (2017).
http:/​/​math.colgate.edu/​~integers/​vol17.html

[57] M. Hirasaka, K. Momihara, S. Suda, A new approach to the excess problem of Hadamard matrices, Algebr. Comb. 1, 5, 697 (2018).
https:/​/​doi.org/​10.5802/​alco.33

[58] M. Yamada, On a series of Hadamard matrices of order 2 and the maximal excess of Hadamard matrices of order 221, Graphs Combin. 4, 297 (1988).
https:/​/​doi.org/​10.1007/​BF01864168

[59] J. Seberry, SBIBD$(4k^2, 2k^2 + k, k^2 + k)$ and Hadamard matrices of order $4k^2$ with maximal excess are equivalent, Graphs Combin. 5, 373 (1989).

[60] C. Koukouvinos, S. Kounias, Construction of some Hadamard matrices with maximum excess, Discr. Math. 85, 295 (1990).
https:/​/​doi.org/​10.1016/​0012-365X(90)90385-U

[61] C. Koukouvinos, S. Kounias, J. Seberry, Supplementary difference sets and optimal designs, Discr. Math. 88, 49 (1991).
https:/​/​doi.org/​10.1016/​0012-365X(91)90058-A

[62] H. Buhrman, W. van Dam, P. Hoyer, A. Tapp, Multiparty Quantum Communication Complexity, Phys. Rev. A 60, 2737 (1999).
https:/​/​doi.org/​10.1103/​PhysRevA.60.2737

[63] H. Nozaki, S. Suda, Weighing matrices and spherical codes, J. Algebr. Comb. 42, 283 (2015).
https:/​/​doi.org/​10.1007/​s10801-015-0581-6

[64] H. Kharaghani, S. Suda, Unbiased orthogonal designs, Des. Codes Cryptogr. 86, 1573 (2018).
https:/​/​doi.org/​10.1007/​s10623-017-0414-9

[66] L. Escolà, J. Calsamiglia, A. Winter, All tight correlation Bell inequalities have quantum violations, Phys. Rev. Research 2, 012044(R) (2020).
https:/​/​doi.org/​10.1103/​PhysRevResearch.2.012044

[67] B. G. Bodmann, H. J. Elwood, Complex Equiangular Parseval Frames and Seidel Matrices containing $p$-th roots of unity, P. Am. Math. Soc. 138, 4387–4404 (2010).
https:/​/​doi.org/​10.1090/​S0002-9939-2010-10435-5

[68] F. Szöllősi, Complex Hadamard matrices and equiangular tight frames, Linear Algebra Appl. 438, 1962–1967 (2013).
https:/​/​doi.org/​10.1016/​j.laa.2011.05.034

[69] D. Goyeneche, O. Turek, Equiangular tight frames and unistochastic matrices, J. Phys. A: Math. Theor. 50 245304 (2017).
https:/​/​doi.org/​10.1088/​1751-8121/​aa6e16

[70] M. L. Almeida, J.-D. Bancal, N. Brunner, A. Acin, N. Gisin, S. Pironio, Guess your neighbour's input: a multipartite non-local game with no quantum advantage, Phys. Rev. Lett. 104, 230404 (2010).
https:/​/​doi.org/​10.1103/​PhysRevLett.104.230404

### Cited by

[1] Ravishankar Ramanathan, "Violation of all two-party facet Bell inequalities by almost-quantum correlations", Physical Review Research 3 3, 033100 (2021).

The above citations are from SAO/NASA ADS (last updated successfully 2023-03-23 04:53:29). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2023-03-23 04:53:27).