Tight bounds for antidistinguishability and circulant sets of pure quantum states

Nathaniel Johnston; Vincent Russo; Jamie Sikora

doi:10.22331/q-2025-02-04-1622

Tight bounds for antidistinguishability and circulant sets of pure quantum states

Nathaniel Johnston¹, Vincent Russo², and Jamie Sikora³

¹Department of Mathematics & Computer Science, Mount Allison University, Sackville, NB, Canada
²Unitary Fund
³Department of Computer Science, Virginia Polytechnic Institute and State University, Blacksburg, Virginia, USA

Published:	2025-02-04, volume 9, page 1622
Editor:	Gael Sentís
Eprint:	arXiv:2311.17047v2
Doi:	https://doi.org/10.22331/q-2025-02-04-1622
Citation:	Quantum 9, 1622 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

A set of pure quantum states is said to be antidistinguishable if upon sampling one at random, there exists a measurement to perfectly determine some state that was not sampled. We show that antidistinguishability of a set of $n$ pure states is equivalent to a property of its Gram matrix called $(n-1)$-incoherence, thus establishing a connection with quantum resource theories that lets us apply a wide variety of new tools to antidistinguishability. As a particular application of our result, we present an explicit formula (not involving any semidefinite programming) that determines whether or not a set with a circulant Gram matrix is antidistinguishable. We also show that if all inner products are smaller than $\sqrt{(n-2)/(2n-2)}$ then the set must be antidistinguishable, and we show that this bound is tight when $n \leq 4$. We also give a simpler proof that if all the inner products are strictly larger than $(n-2)/(n-1)$, then the set cannot be antidistinguishable, and we show that this bound is tight for all $n$.

► BibTeX data

@article{Johnston2025tightbounds,
  doi = {10.22331/q-2025-02-04-1622},
  url = {https://doi.org/10.22331/q-2025-02-04-1622},
  title = {Tight bounds for antidistinguishability and circulant sets of pure quantum states},
  author = {Johnston, Nathaniel and Russo, Vincent and Sikora, Jamie},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1622},
  month = feb,
  year = {2025}
}

► References

[1] Carlton M. Caves, Christopher A. Fuchs, and Rüdiger Schack. ``Conditions for compatibility of quantum-state assignments''. Physical Review A 66, 062111 (2002).
https://doi.org/10.1103/PhysRevA.66.062111

[2] Matthew Saul Leifer. ``Is the quantum state real? An extended review of $\psi$-ontology theorems'' (2014).

[3] Teiko Heinosaari and Oskari Kerppo. ``Antidistinguishability of pure quantum states''. Journal of Physics A: Mathematical and Theoretical 51, 365303 (2018).
https://doi.org/10.1088/1751-8121/aad1fc

[4] Matthew F. Pusey, Jonathan Barrett, and Terry Rudolph. ``On the reality of the quantum state''. Nature Physics 8, 475–478 (2012).
https://doi.org/10.1038/nphys2309

[5] Somshubhro Bandyopadhyay, Rahul Jain, Jonathan Oppenheim, and Christopher Perry. ``Conclusive exclusion of quantum states''. Physical Review A 89, 022336 (2014).
https://doi.org/10.1103/PhysRevA.89.022336

[6] Christopher Perry, Rahul Jain, and Jonathan Oppenheim. ``Communication tasks with infinite quantum-classical separation''. Physical Review Letters 115, 030504 (2015).
https://doi.org/10.1103/PhysRevLett.115.030504

[7] Teiko Heinosaari and Oskari Kerppo. ``Communication of partial ignorance with qubits''. Journal of Physics A: Mathematical and Theoretical 52, 395301 (2019).
https://doi.org/10.1088/1751-8121/ab3ae4

[8] Vojtvech Havlívcek and Jonathan Barrett. ``Simple communication complexity separation from quantum state antidistinguishability''. Physical Review Research 2, 013326 (2020).
https://doi.org/10.1103/PhysRevResearch.2.013326

[9] Vedran Dunjko, Petros Wallden, and Erika Andersson. ``Quantum digital signatures without quantum memory''. Physical Review Letters 112, 040502 (2014).
https://doi.org/10.1103/PhysRevLett.112.040502

[10] Ryan Amiri, Robert Stárek, David Reichmuth, Ittoop V. Puthoor, Michal Mičuda, Jr. Mišta, Ladislav, Miloslav Dušek, Petros Wallden, and Erika Andersson. ``Imperfect 1-Out-of-2 Quantum Oblivious Transfer: Bounds, a Protocol, and its Experimental Implementation''. PRX Quantum 2, 010335 (2021).
https://doi.org/10.1103/PRXQuantum.2.010335

[11] Charles H. Bennett, David P. DiVincenzo, Christopher A. Fuchs, Tal Mor, Eric Rains, Peter W. Shor, John A. Smolin, and William K. Wootters. ``Quantum nonlocality without entanglement''. Physical Review A 59, 1070 (1999).
https://doi.org/10.1103/PhysRevA.59.1070

[12] Anthony Chefles. ``Quantum state discrimination''. Contemporary Physics 41, 401–424 (2000).
https://doi.org/10.1080/00107510010002599

[13] Jonathan Walgate, Anthony J. Short, Lucien Hardy, and Vlatko Vedral. ``Local distinguishability of multipartite orthogonal quantum states''. Physical Review Letters 85, 4972 (2000).
https://doi.org/10.1103/PhysRevLett.85.4972

[14] Sibasish Ghosh, Guruprasad Kar, Anirban Roy, Aditi Sen, and Ujjwal Sen. ``Distinguishability of Bell states''. Physical Review Letters 87, 277902 (2001).
https://doi.org/10.1103/PhysRevLett.87.277902

[15] Shashank Virmani, Massimiliano F. Sacchi, Martin B. Plenio, and Damian Markham. ``Optimal local discrimination of two multipartite pure states''. Physics Letters A 288, 62–68 (2001).
https://doi.org/10.1016/S0375-9601(01)00484-4

[16] Jonathan Walgate and Lucien Hardy. ``Nonlocality, asymmetry, and distinguishing bipartite states''. Physical Review Letters 89, 147901 (2002).
https://doi.org/10.1103/PhysRevLett.89.147901

[17] Michał Horodecki, Aditi Sen, Ujjwal Sen, and Karol Horodecki. ``Local indistinguishability: More nonlocality with less entanglement''. Physical Review Letters 90, 047902 (2003).
https://doi.org/10.1103/PhysRevLett.90.047902

[18] John Watrous. ``Bipartite subspaces having no bases distinguishable by local operations and classical communication''. Physical Review Letters 95, 080505 (2005).
https://doi.org/10.1103/PhysRevLett.95.080505

[19] Stephen M. Barnett and Sarah Croke. ``Quantum state discrimination''. Advances in Optics and Photonics 1, 238–278 (2009).
https://doi.org/10.1364/AOP.1.000238

[20] János A. Bergou. ``Discrimination of quantum states''. Journal of Modern Optics 57, 160–180 (2010).
https://doi.org/10.1080/09500340903477756

[21] Daowen Qiu and Lvjun Li. ``Minimum-error discrimination of quantum states: Bounds and comparisons''. Physical Review A 81, 042329 (2010).
https://doi.org/10.1103/PhysRevA.81.042329

[22] Joonwoo Bae and Leong-Chuan Kwek. ``Quantum state discrimination and its applications''. Journal of Physics A: Mathematical and Theoretical 48, 083001 (2015).
https://doi.org/10.1088/1751-8113/48/8/083001

[23] Hemant K. Mishra, Michael Nussbaum, and Mark M. Wilde. ``On the optimal error exponents for classical and quantum antidistinguishability'' (2023).

[24] Matthew Leifer and Cristhiano Duarte. ``Noncontextuality inequalities from antidistinguishability''. Phys. Rev. A 101, 062113 (2020).
https://doi.org/10.1103/PhysRevA.101.062113

[25] Pierre-Emmanuel Emeriau, Mark Howard, and Shane Mansfield. ``Quantum advantage in information retrieval''. PRX Quantum 3, 020307 (2022).
https://doi.org/10.1103/PRXQuantum.3.020307

[26] Alberto Montina and Stefan Wolf. ``Lower bounds on the communication complexity of two-party (quantum) processes''. In 2014 IEEE International Symposium on Information Theory. Pages 1484–1488. IEEE (2014).
https://doi.org/10.1109/ISIT.2014.6875080

[27] Alberto Montina and Stefan Wolf. ``Necessary and sufficient optimality conditions for classical simulations of quantum communication processes''. Physical Review A 90, 012309 (2014).
https://doi.org/10.1103/PhysRevA.90.012309

[28] Vincent Russo and Jamie Sikora. ``Inner products of pure states and their antidistinguishability''. Physical Review A 107, L030202 (2023).
https://doi.org/10.1103/PhysRevA.107.L030202

[29] Gael Sentís, Emilio Bagan, John Calsamiglia, Giulio Chiribella, and Ramon Munoz-Tapia. ``Quantum change point''. Physical Review Letters 117, 150502 (2016).
https://doi.org/10.1103/PhysRevLett.117.150502

[30] Gael Sentís, John Calsamiglia, and Ramon Munoz-Tapia. ``Exact identification of a quantum change point''. Physical Review Letters 119, 140506 (2017).
https://doi.org/10.1103/PhysRevLett.119.140506

[31] Martin Ringbauer, Thomas R. Bromley, Marco Cianciaruso, Ludovico Lami, W. Y. Sarah Lau, Gerardo Adesso, Andrew G. White, Alessando Fedrizzi, and Marco Piani. ``Certification and quantification of multilevel quantum coherence''. Physical Review X 8, 041007 (2018).
https://doi.org/10.1103/PhysRevX.8.041007

[32] Zi-Wen Liu, Kaifeng Bu, and Ryuji Takagi. ``One-shot operational quantum resource theory''. Physical Review Letters 123, 020401 (2019).
https://doi.org/10.1103/PhysRevLett.123.020401

[33] Jun-Wei Liu, Shu-Qian Shen, Ming Li, and Lei Li. ``Lower bounds for the robustness of multilevel coherence''. International Journal of Theoretical Physics 60, 1712–1719 (2021).
https://doi.org/10.1007/s10773-021-04793-1

[34] Federico Levi and Florian Mintert. ``A quantitative theory of coherent delocalization''. New Journal of Physics 16, 033007 (2014).
https://doi.org/10.1088/1367-2630/16/3/033007

[35] LiMei Zhang, Ting Gao, and FengLi Yan. ``Transformations of multilevel coherent states under coherence-preserving operations''. Science China Physics, Mechanics & Astronomy 64, 1–6 (2021).
https://doi.org/10.1007/s11433-021-1696-y

[36] Nathaniel Johnston, Shirin Moein, Rajesh Pereira, and Sarah Plosker. ``Absolutely k-incoherent quantum states and spectral inequalities for factor width of a matrix''. Physical Review A 106, 052417 (2022).
https://doi.org/10.1103/PhysRevA.106.052417

[37] Michael A. Nielsen and Isaac L. Chuang. ``Quantum Computation and Quantum Information''. Cambridge University Press. (2000).
https://doi.org/10.1017/CBO9780511976667

[38] John Watrous. ``The Theory of Quantum Information''. Cambridge University Press. (2018).
https://doi.org/10.1017/9781316848142

[39] Graeme Weir. ``Optimal discrimination of quantum states''. PhD thesis. University of Glasgow. (2018).

[40] Nathaniel Johnston. ``Advanced linear and matrix algebra''. Springer. (2021).
https://doi.org/10.1007/978-3-030-52815-7

[41] Philip J. Davis. ``Circulant matrices''. Monographs and textbooks in pure and applied mathematics. Wiley. (1979).

[42] Vedran Dunjko and Erika Andersson. ``Transformations between symmetric sets of quantum states''. Journal of Physics A: Mathematical and Theoretical 45, 365304 (2012).
https://doi.org/10.1088/1751-8113/45/36/365304

[43] Mark Howard and Jiri Vala. ``Qudit versions of the qubit $\pi$/8 gate''. Physical Review A—Atomic, Molecular, and Optical Physics 86, 022316 (2012).
https://doi.org/10.1103/PhysRevA.86.022316

[44] Nicola Dalla Pozza and Gianfranco Pierobon. ``Optimality of square-root measurements in quantum state discrimination''. Physical Review A 91, 042334 (2015).
https://doi.org/10.1103/PhysRevA.91.042334

[45] Louis Deaett and Seth A. Meyer. ``The minimum rank problem for circulants''. Linear Algebra and its Applications 491, 386–418 (2016).
https://doi.org/10.1016/j.laa.2015.10.033

[46] Jan Sperling and Werner Vogel. ``Convex ordering and quantification of quantumness''. Physica Scripta 90, 074024 (2015).
https://doi.org/10.1088/0031-8949/90/7/074024

[47] Erik G. Boman, Doron Chen, Ojas Parekh, and Sivan Toledo. ``On factor width and symmetric H-matrices''. Linear Algebra and its Applications 405, 239–248 (2005).
https://doi.org/10.1016/j.laa.2005.03.029

[48] Grigoriy Blekherman, Santanu S Dey, Kevin Shu, and Shengding Sun. ``Hyperbolic relaxation of k-locally positive semidefinite matrices''. SIAM Journal on Optimization 32, 470–490 (2022).
https://doi.org/10.1137/20M1387407

[49] Stephen Boyd and Lieven Vandenberghe. ``Convex optimization''. Cambridge University Press. (2004).
https://doi.org/10.1017/CBO9780511804441

[50] Yuriy Zinchenko. ``On hyperbolicity cones associated with elementary symmetric polynomials''. Optimization Letters 2, 389–402 (2008).
https://doi.org/10.1007/s11590-007-0067-0

[51] Nathaniel Johnston, Vincent Russo, and Jamie Sikora. ``circulant_antidist: A Python toolkit for studying the antidistinguishability of circulant pure states''. https://github.com/vprusso/circulant_antidist (2023).
https://github.com/vprusso/circulant_antidist

[52] Vincent Russo. ``toqito – Theory of quantum information toolkit: A Python package for studying quantum information''. Journal of Open Source Software 6, 3082 (2021).
https://doi.org/10.21105/joss.03082

[53] Guillaume Sagnol and Maximilian Stahlberg. ``PICOS: A Python interface to conic optimization solvers''. Journal of Open Source Software 7, 3915 (2022).
https://doi.org/10.21105/joss.03915

[54] Martin Andersen, Joachim Dahl, and Lieven Vandenberghe. ``CVXOPT: Convex Optimization''. Astrophysics Source Code LibraryPage ascl:2008.017 (2020). url: https://ui.adsabs.harvard.edu/abs/2020ascl.soft08017A.
https://ui.adsabs.harvard.edu/abs/2020ascl.soft08017A

Cited by

[1] Mark Hillery, Erika Andersson, and Ittoop V Puthoor, "A group-theoretic approach to elimination measurements of qubit sequences", Journal of Physics A: Mathematical and Theoretical 58 42, 425301 (2025).

[2] Satyaki Manna, Sneha Suresh, Manan Singh Kachhawaha, and Debashis Saha, "Single-shot distinguishability and antidistinguishability of quantum measurements", Physical Review A 111 2, 022221 (2025).

[3] Ankush Pandit, Soumyabrata Hazra, Satyaki Manna, Anubhav Chaturvedi, and Debashis Saha, "Limits of classical correlations and quantum advantages under (anti-)distinguishability constraints in multipartite communication", Physical Review A 113 3, 032433 (2026).

[4] Ian George, Christoph Hirche, Theshani Nuradha, and Mark M. Wilde, "Quantum Doeblin Coefficients: Interpretations and Applications", Quantum 10, 2115 (2026).

[5] Satyaki Manna and Anandamay Das Bhowmik, "Single-shot antidistinguishability of unitary operations", Physical Review A 113 2, 022218 (2026).

[6] Maiyuren Srikumar, Stephen D. Bartlett, and Angela Karanjai, "How Contextuality and Antidistinguishability Are Related", Physical Review Letters 136 8, 080203 (2026).

[7] Kaiyuan Ji, Hemant K. Mishra, Milán Mosonyi, and Mark M. Wilde, "Barycentric Bounds on the Error Exponents of Quantum Hypothesis Exclusion", IEEE Transactions on Information Theory 72 4, 2391 (2026).

[8] Joonwoo Bae, Kieran Flatt, Teiko Heinosaari, Oskari Kerppo, Karthik Mohan, Andrés Muñoz-Moller, and Ashutosh Rai, "Random exclusion codes: Quantum advantages of single-shot communication", Physical Review Research 8 1, 013171 (2026).

[9] Anubhav Chaturvedi, Marcin Pawłowski, and Debashis Saha, "Epistemic incompleteness of quantum theory", Physical Review A 113 4, 042445 (2026).

[10] Sagnik Ray, Visweshwaran R, and Debashis Saha, "Failure of epistemic models to explain the antidistinguishability of quantum mixed preparations", Physical Review A 113 6, 062203 (2026).

[11] Rabha W. Ibrahim, Dumitru Baleanu, and Soheil Salahshour, "Weighted Deformed Gram Matrices for Quantum‐Inspired Learning With Applications to Biomedical Signal Analysis", Engineering Reports 8 6, e70855 (2026).

[12] A. Diebra, S. Llorens, E. Bagan, G. Sentís, and R. Muñoz-Tapia, "Quantum state exclusion for group-generated ensembles of pure states", Physical Review Research 8 1, L012001 (2026).

[13] Guo Zheng, Wenhao He, Gideon Lee, and Liang Jiang, "Near-Optimal Performance of Quantum Error Correction Codes", Physical Review Letters 132 25, 250602 (2024).

[14] Kaiyuan Ji, Hemant K. Mishra, Milán Mosonyi, and Mark M. Wilde, "Barycentric bounds on the error exponents of quantum hypothesis exclusion", arXiv:2407.13728, (2024).

[15] Benjamin Stratton, Chung-Yun Hsieh, and Paul Skrzypczyk, "Operational interpretation of the Choi rank through exclusion tasks", Physical Review A 110 5, L050601 (2024).

[16] Sagnik Ray, Visweshwaran R, and Debashis Saha, "Failure of epistemic models to explain the antidistinguishability of quantum mixed preparations", arXiv:2401.17980, (2024).

[17] Caleb McIrvin, Ankith Mohan, and Jamie Sikora, "Quantum state exclusion through offset measurement", Physical Review A 110 4, 042211 (2024).

[18] Ankith Mohan, Jamie Sikora, and Sarvagya Upadhyay, "A hybrid quantum-classical algorithm for Bayes-optimal quantum state discrimination using the source code", arXiv:2312.04023, (2023).

[19] Martin J. Renner, Edwin Peter Lobo, Arturo Konderak, Remigiusz Augusiak, and Antonio Acín, "All pure entangled states can lead to fully nonlocal correlations", arXiv:2604.26605, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-08 04:01:23) and SAO/NASA ADS (last updated successfully 2026-08-08 04:01:24). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.