Connect with us


Policies for elementary links in a quantum network



Sumeet Khatri

Hearne Institute for Theoretical Physics, Department of Physics and Astronomy, and Center for Computation and Technology, Louisiana State University, Baton Rouge, Louisiana, 70803, USA

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


Distributing entanglement over long distances is one of the central tasks in quantum networks. An important problem, especially for near-term quantum networks, is to develop optimal entanglement distribution protocols that take into account the limitations of current and near-term hardware, such as quantum memories with limited coherence time. We address this problem by initiating the study of quantum network protocols for entanglement distribution using the theory of decision processes, such that optimal protocols (referred to as $policies$ in the context of decision processes) can be found using dynamic programming or reinforcement learning algorithms. As a first step, in this work we focus exclusively on the elementary link level. We start by defining a quantum decision process for elementary links, along with figures of merit for evaluating policies. We then provide two algorithms for determining policies, one of which we prove to be optimal (with respect to fidelity and success probability) among all policies. Then we show that the previously-studied memory-cutoff protocol can be phrased as a policy within our decision process framework, allowing us to obtain several new fundamental results about it. The conceptual developments and results of this work pave the way for the systematic study of the fundamental limitations of near-term quantum networks, and the requirements for physically realizing them.

The quantum internet is one of the frontiers of quantum information science. It has the potential to revolutionize the way we communicate and do other tasks, and it will allow for tasks that are not possible using the current, classical internet alone, such as quantum teleportation and quantum key distribution. Realizing the quantum internet is a major task, both from the theoretical perspective and from the practical perspective. Understanding the performance of quantum network protocols, particularly with noisy, imperfect near-term devices, is crucial in order to begin realizing small-scale quantum networks. This work sets out on the task of quantifying the performance of quantum network protocols, in particular determining optimal protocols, using the theory of decision processes. As a first step, in this work we focus on the elementary link level. We establish a theoretical framework based on decision processes that allows us to determine an optimal protocol for an elementary link in the presence of device imperfections. This theoretical framework also allows us to determine several new and fundamental results about a well known and heavily studied protocol, which we refer to here as the “memory-cutoff protocol”. The developments of this work pave the way for a complete theory of practical quantum network protocols, which we expect will help drive the physical realization of small-scale quantum networks, and eventually lead to the realization of a global-scale quantum internet.

► BibTeX data

► References

[1] H. J. Kimble “The quantum internet” Nature 453 (2008).

[2] Christoph Simon “Towards a global quantum network” Nature Photonics 11, 678–680 (2017).

[3] Davide Castelvecchi “The quantum internet has arrived (and it hasn’t)” Nature 554, 289–292 (2018).

[4] Stephanie Wehner, David Elkouss, and Ronald Hanson, “Quantum internet: A vision for the road ahead” Science 362 (2018).

[5] Jonathan Dowling “Schrödinger’s Web: Race to Build the Quantum Internet” Taylor & Francis (2020).

[6] Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K. Wootters, “Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels” Physical Review Letters 70, 1895–1899 (1993).

[7] Lev Vaidman “Teleportation of quantum states” Physical Review A 49, 1473–1476 (1994).

[8] Samuel L. Braunstein, Christopher A. Fuchs, and H. J. Kimble, “Criteria for continuous-variable quantum teleportation” Journal of Modern Optics 47, 267–278 (2000).

[9] Charles H. Bennett and Gilles Brassard “Quantum cryptography: Public key distribution and coin tossing” International Conference on Computer System and Signal Processing, IEEE 175–179 (1984).

[10] Artur K. Ekert “Quantum cryptography based on Bell’s theorem” Physical Review Letters 67, 661–663 (1991).

[11] Nicolas Gisin, Grégoire Ribordy, Wolfgang Tittel, and Hugo Zbinden, “Quantum cryptography” Reviews of Modern Physics 74, 145–195 (2002).

[12] Valerio Scarani, Helle Bechmann-Pasquinucci, Nicolas J. Cerf, Miloslav Dušek, Norbert Lütkenhaus, and Momtchil Peev, “The security of practical quantum key distribution” Reviews of Modern Physics 81, 1301–1350 (2009).

[13] Richard Jozsa, Daniel S. Abrams, Jonathan P. Dowling, and Colin P. Williams, “Quantum Clock Synchronization Based on Shared Prior Entanglement” Physical Review Letters 85, 2010–2013 (2000).

[14] John Preskill “Quantum clock synchronization and quantum error correction” arXiv:quant-ph/​0010098 (2000).

[15] Ulvi Yurtsever and Jonathan P. Dowling “Lorentz-invariant look at quantum clock-synchronization protocols based on distributed entanglement” Physical Review A 65, 052317 (2002).

[16] Ebubechukwu O. Ilo-Okeke, Louis Tessler, Jonathan P. Dowling, and Tim Byrnes, “Remote quantum clock synchronization without synchronized clocks” npj Quantum Information 4, 40 (2018).

[17] J. I. Cirac, A. K. Ekert, S. F. Huelga, and C. Macchiavello, “Distributed quantum computation over noisy channels” Physical Review A 59, 4249–4254 (1999).

[18] P. Kómár, E. M. Kessler, M. Bishof, L. Jiang, A. S. Sørensen, J. Ye, and M. D. Lukin, “A quantum network of clocks” Nature Physics 10, 582 (2014).

[19] C. L. Degen, F. Reinhard, and P. Cappellaro, “Quantum sensing” Reviews of Modern Physics 89, 035002 (2017).

[20] Quntao Zhuang, Zheshen Zhang, and Jeffrey H. Shapiro, “Distributed quantum sensing using continuous-variable multipartite entanglement” Physical Review A 97, 032329 (2018).

[21] Zachary Eldredge, Michael Foss-Feig, Jonathan A. Gross, S. L. Rolston, and Alexey V. Gorshkov, “Optimal and secure measurement protocols for quantum sensor networks” Physical Review A 97, 042337 (2018).

[22] Timothy J. Proctor, Paul A. Knott, and Jacob A. Dunningham, “Multiparameter Estimation in Networked Quantum Sensors” Physical Review Letters 120, 080501 (2018).

[23] Yi Xia, Quntao Zhuang, William Clark, and Zheshen Zhang, “Repeater-enhanced distributed quantum sensing based on continuous-variable multipartite entanglement” Physical Review A 99, 012328 (2019).

[24] D. L. Moehring, P. Maunz, S. Olmschenk, K. C. Younge, D. N. Matsukevich, L.-M. Duan, and C. Monroe, “Entanglement of single-atom quantum bits at a distance” Nature 449, 68 (2007).

[25] P. Maunz, S. Olmschenk, D. Hayes, D. N. Matsukevich, L.-M. Duan, and C. Monroe, “Heralded Quantum Gate between Remote Quantum Memories” Physical Review Letters 102, 250502 (2009).

[26] M. Peev, C. Pacher, R. Alléaume, and C. Barreiro, “The SECOQC quantum key distribution network in Vienna” New Journal of Physics 11, 075001 (2009).

[27] Teng-Yun Chen, Jian Wang, Hao Liang, and Wei-Yue Liu, “Metropolitan all-pass and inter-city quantum communication network” Optics Express 18, 27217–27225 (2010).

[28] Abdul Mirza and Francesco Petruccione “Realizing long-term quantum cryptography” Journal of the Optical Society of America B 27, A185–A188 (2010).

[29] D. Stucki, M. Legré, F. Buntschu, and B. Clausen, “Long-term performance of the SwissQuantum quantum key distribution network in a field environment” New Journal of Physics 13, 123001 (2011).

[30] M. Sasaki, M. Fujiwara, H. Ishizuka, and W. Klaus, “Field test of quantum key distribution in the Tokyo QKD Network” Optics Express 19, 10387–10409 (2011).

[31] Stephan Ritter, Christian Nölleke, Carolin Hahn, and Andreas Reiserer, “An elementary quantum network of single atoms in optical cavities” Nature 484, 195 (2012).

[32] Julian Hofmann, Michael Krug, Norbert Ortegel, Lea Gérard, Markus Weber, Wenjamin Rosenfeld, and Harald Weinfurter, “Heralded Entanglement Between Widely Separated Atoms” Science 337, 72–75 (2012).

[33] H. Bernien, B. Hensen, W. Pfaff, G. Koolstra, M. S. Blok, L. Robledo, T. H. Taminiau, M. Markham, D. J. Twitchen, L. Childress, and R. Hanson, “Heralded entanglement between solid-state qubits separated by three metres” Nature 497, 86–90 (2013).

[34] Shuang Wang, Wei Chen, Zhen-Qiang Yin, and Hong-Wei Li, “Field and long-term demonstration of a wide area quantum key distribution network” Optics Express 22, 21739–21756 (2014).

[35] Aymeric Delteil, Zhe Sun, Wei-bo Gao, Emre Togan, Stefan Faelt, and Ataç Imamoǧlu, “Generation of heralded entanglement between distant hole spins” Nature Physics 12, 218–223 (2016).

[36] R. Stockill, M. J. Stanley, L. Huthmacher, E. Clarke, M. Hugues, A. J. Miller, C. Matthiesen, C. Le Gall, and M. Atatüre, “Phase-Tuned Entangled State Generation between Distant Spin Qubits” Physical Review Letters 119, 010503 (2017).

[37] Norbert Kalb, Andreas A. Reiserer, Peter C. Humphreys, and Jacob J. W. Bakermans, “Entanglement distillation between solid-state quantum network nodes” Science 356, 928–932 (2017).

[38] Juan Yin, Yuan Cao, Yu-Huai Li, Sheng-Kai Liao, Liang Zhang, Ji-Gang Ren, Wen-Qi Cai, Wei-Yue Liu, Bo Li, Hui Dai, Guang-Bing Li, Qi-Ming Lu, Yun-Hong Gong, Yu Xu, Shuang-Lin Li, Feng-Zhi Li, Ya-Yun Yin, Zi-Qing Jiang, Ming Li, Jian-Jun Jia, Ge Ren, Dong He, Yi-Lin Zhou, Xiao-Xiang Zhang, Na Wang, Xiang Chang, Zhen-Cai Zhu, Nai-Le Liu, Yu-Ao Chen, Chao-Yang Lu, Rong Shu, Cheng-Zhi Peng, Jian-Yu Wang, and Jian-Wei Pan, “Satellite-based entanglement distribution over 1200 kilometers” Science 356, 1140–1144 (2017).

[39] Peter C. Humphreys, Norbert Kalb, Jaco P. J. Morits, Raymond N. Schouten, Raymond F. L. Vermeulen, Daniel J. Twitchen, Matthew Markham, and Ronald Hanson, “Deterministic delivery of remote entanglement on a quantum network” Nature 558, 268 (2018).

[40] Darius Bunandar, Anthony Lentine, Catherine Lee, and Hong Cai, “Metropolitan Quantum Key Distribution with Silicon Photonics” Physical Review X 8, 021009 (2018).

[41] Qiang Zhang, Feihu Xu, Yu-Ao Chen, Cheng-Zhi Peng, and Jian-Wei Pan, “Large scale quantum key distribution: challenges and solutions” Optics Express 26, 24260–24273 (2018).

[42] L. J. Stephenson, D. P. Nadlinger, B. C. Nichol, S. An, P. Drmota, T. G. Ballance, K. Thirumalai, J. F. Goodwin, D. M. Lucas, and C. J. Ballance, “High-Rate, High-Fidelity Entanglement of Qubits Across an Elementary Quantum Network” Physical Review Letters 124, 110501 (2020).

[43] Matteo Pompili, Sophie L. N. Hermans, Simon Baier, Hans K. C. Beukers, Peter C. Humphreys, Raymond N. Schouten, Raymond F. L. Vermeulen, Marijn J. Tiggelman, Laura dos Santos Martins, Bas Dirkse, Stephanie Wehner, and Ronald Hanson, “Realization of a multi-node quantum network of remote solid-state qubits” arXiv:2102.04471 (2021).

[44] L. O. Mailloux, J. D. Morris, M. R. Grimaila, D. D. Hodson, D. R. Jacques, J. M. Colombi, C. V. Mclaughlin, and J. A. Holes, “A Modeling Framework for Studying Quantum Key Distribution System Implementation Nonidealities” IEEE Access 3, 110–130 (2015).

[45] Axel Dahlberg and Stephanie Wehner “SimulaQron—a simulator for developing quantum internet software” Quantum Science and Technology 4, 015001 (2018).

[46] Ben Bartlett “A distributed simulation framework for quantum networks and channels” arXiv:1808.07047 (2018).

[47] Takaaki Matsuo “Simulation of a Dynamic, RuleSet-based Quantum Network” arXiv:1908.10758 (2019).

[48] Stephen DiAdamo, Janis Nötzel, Benjamin Zanger, and Mehmet Mert Beşe, “QuNetSim: A Software Framework for Quantum Networks” arXiv:2003.06397 (2020).

[49] Xiaoliang Wu, Alexander Kolar, Joaquin Chung, Dong Jin, Tian Zhong, Rajkumar Kettimuthu, and Martin Suchara, “SeQUeNCe: A Customizable Discrete-Event Simulator of Quantum Networks” arXiv:2009.12000 (2020).

[50] Tim Coopmans, Robert Knegjens, Axel Dahlberg, David Maier, Loek Nijsten, Julio Oliveira, Martijn Papendrecht, Julian Rabbie, Filip Rozpędek, Matthew Skrzypczyk, Leon Wubben, Walter de Jong, Damian Podareanu, Ariana Torres Knoop, David Elkouss, and Stephanie Wehner, “NetSquid, a NETwork Simulator for QUantum Information using Discrete events” Communications Physics 4, 164 (2021).

[51] M. L. Puterman “Markov Decision Processes: Discrete Stochastic Dynamic Programming” Wiley (2014).

[52] Richard S. Suttonand Andrew G. Barto “Reinforcement Learning: An Introduction” MIT Press (2018).

[53] Stuart Russell and Peter Norvig “Artificial Intelligence: A Modern Approach” Pearson (2009).

[54] Julius Wallnöfer, Alexey A. Melnikov, Wolfgang Dür, and Hans J. Briegel, “Machine Learning for Long-Distance Quantum Communication” PRX Quantum 1, 010301 (2020).

[55] Liang Jiang, Jacob M. Taylor, Navin Khaneja, and Mikhail D. Lukin, “Optimal approach to quantum communication using dynamic programming” Proceedings of the National Academy of Sciences 104, 17291–17296 (2007).

[56] Eddie Schoute, Laura Mancinska, Tanvirul Islam, Iordanis Kerenidis, and Stephanie Wehner, “Shortcuts to quantum network routing” arXiv:1610.05238 (2016).

[57] Kaushik Chakraborty, Filip Rozpędek, Axel Dahlberg, and Stephanie Wehner, “Distributed Routing in a Quantum Internet” arXiv:1907.11630 (2019).

[58] O. A. Collins, S. D. Jenkins, A. Kuzmich, and T. A. B. Kennedy, “Multiplexed Memory-Insensitive Quantum Repeaters” Physical Review Letters 98, 060502 (2007).

[59] Christoph Simon, Hugues de Riedmatten, Mikael Afzelius, Nicolas Sangouard, Hugo Zbinden, and Nicolas Gisin, “Quantum Repeaters with Photon Pair Sources and Multimode Memories” Physical Review Letters 98, 190503 (2007).

[60] Nicolas Sangouard, Christoph Simon, Jiří Minář, Hugo Zbinden, Hugues de Riedmatten, and Nicolas Gisin, “Long-distance entanglement distribution with single-photon sources” Physical Review A 76, 050301 (2007).

[61] Nadja K. Bernardes, Ludmiła Praxmeyer, and Peter van Loock, “Rate analysis for a hybrid quantum repeater” Physical Review A 83, 012323 (2011).

[62] Cody Jones, Danny Kim, Matthew T. Rakher, Paul G. Kwiat, and Thaddeus D. Ladd, “Design and analysis of communication protocols for quantum repeater networks” New Journal of Physics 18, 083015 (2016).

[63] Suzanne B. van Dam, Peter C. Humphreys, Filip Rozpędek, Stephanie Wehner, and Ronald Hanson, “Multiplexed entanglement generation over quantum networks using multi-qubit nodes” Quantum Science and Technology 2, 034002 (2017).

[64] Filip Rozpędek, Raja Yehia, Kenneth Goodenough, Maximilian Ruf, Peter C. Humphreys, Ronald Hanson, Stephanie Wehner, and David Elkouss, “Near-term quantum-repeater experiments with nitrogen-vacancy centers: Overcoming the limitations of direct transmission” Physical Review A 99, 052330 (2019).

[65] E. Shchukin, F. Schmidt, and P. van Loock, “Waiting time in quantum repeaters with probabilistic entanglement swapping” Physical Review A 100, 032322 (2019).

[66] Sumeet Khatri, Corey T. Matyas, Aliza U. Siddiqui, and Jonathan P. Dowling, “Practical figures of merit and thresholds for entanglement distribution in quantum networks” Physical Review Research 1, 023032 (2019).

[67] Siddhartha Santra, Liang Jiang, and Vladimir S. Malinovsky, “Quantum repeater architecture with hierarchically optimized memory buffer times” Quantum Science and Technology 4, 025010 (2019).

[68] Boxi Li, Tim Coopmans, and David Elkouss, “Efficient optimization of cut-offs in quantum repeater chains” arXiv:2005.04946 (2020).

[69] Koji Azuma, Kiyoshi Tamaki, and Hoi-Kwong Lo, “All-photonic quantum repeaters” Nature Communications 6 (2015).

[70] K. Boone, J.-P. Bourgoin, E. Meyer-Scott, K. Heshami, T. Jennewein, and C. Simon, “Entanglement over global distances via quantum repeaters with satellite links” Physical Review A 91, 052325 (2015).

[71] Sumeet Khatri, Anthony J. Brady, Renée A. Desporte, Manon P. Bart, and Jonathan P. Dowling, “Spooky action at a global distance: analysis of space-based entanglement distribution for the quantum internet” npj Quantum Information 7, 4 (2021).

[72] Carlo Liorni, Hermann Kampermann, and Dagmar Bruß, “Quantum repeaters in space” New Journal of Physics 23, 053021 (2021).

[73] Mustafa Gündoǧan, Jasminder S. Sidhu, Victoria Henderson, Luca Mazzarella, Janik Wolters, Daniel K.L. Oi, and Markus Krutzik, “Space-borne quantum memories for global quantum communication” arXiv:2006.10636 (2020).

[74] Mateusz Polnik, Luca Mazzarella, Marilena Di Carlo, Daniel KL Oi, Annalisa Riccardi, and Ashwin Arulselvan, “Scheduling of space to ground quantum key distribution” EPJ Quantum Technology 7, 3 (2020).

[75] Sumeet Khatri “Towards a General Framework for Practical Quantum Network Protocols” thesis (2021) https:/​/​​gradschool_dissertations/​5456/​.

[76] Luciano Aparicio, Rodney Van Meter, and Hiroshi Esaki, “Protocol Design for Quantum Repeater Networks” Proceedings of the 7th Asian Internet Engineering Conference 73–80 (2011).

[77] R. V. Meter and J. Touch “Designing quantum repeater networks” IEEE Communications Magazine 51, 64–71 (2013).

[78] A. Pirker, J. Wallnöfer, and W. Dür, “Modular architectures for quantum networks” New Journal of Physics 20, 053054 (2018).

[79] A. Pirker and W. Dür “A quantum network stack and protocols for reliable entanglement-based networks” New Journal of Physics 21, 033003 (2019).

[80] Gayane Vardoyan, Saikat Guha, Philippe Nain, and Don Towsley, “On the exact analysis of an idealized quantum switch” Performance Evaluation 144, 102141 (2020).

[81] Philippe Nain, Gayane Vardoyan, Saikat Guha, and Don Towsley, “On the Analysis of a Multipartite Entanglement Distribution Switch” Proc. ACM Meas. Anal. Comput. Syst. 4 (2020).

[82] Gayane Vardoyan, Saikat Guha, Philippe Nain, and Don Towsley, “On the Stochastic Analysis of a Quantum Entanglement Distribution Switch” IEEE Transactions on Quantum Engineering 2, 1–16 (2021).

[83] Gayane Vardoyan, Saikat Guha, Philippe Nain, and Don Towsley, “On the Capacity Region of Bipartite and Tripartite Entanglement Switching” SIGMETRICS Perform. Eval. Rev. 48, 45–50 (2021).

[84] Thomas A Caswell, Michael Droettboom, Antony Lee, Elliott Sales de Andrade, John Hunter, Tim Hoffmann, Eric Firing, Jody Klymak, David Stansby, Nelle Varoquaux, Jens Hedegaard Nielsen, Benjamin Root, Ryan May, Phil Elson, Jouni K. Seppänen, Darren Dale, Jae-Joon Lee, Damon McDougall, Andrew Straw, Paul Hobson, Christoph Gohlke, Tony S. Yu, Eric Ma, hannah, Adrien F. Vincent, Steven Silvester, Charlie Moad, Nikita Kniazev, Elan Ernest, and Paul Ivanov, “matplotlib” (2021).

[85] Koji Azuma, Akihiro Mizutani, and Hoi-Kwong Lo, “Fundamental rate-loss trade-off for the quantum internet” Nature Communications 7, 13523 (2016).

[86] Koji Azuma and Go Kato “Aggregating quantum repeaters for the quantum internet” Physical Review A 96, 032332 (2017).

[87] Stefan Bäuml and Koji Azuma “Fundamental limitation on quantum broadcast networks” Quantum Science and Technology 2, 024004 (2017).

[88] Luca Rigovacca, Go Kato, Stefan Bäuml, M. S. Kim, W. J. Munro, and Koji Azuma, “Versatile relative entropy bounds for quantum networks” New Journal of Physics 20, 013033 (2018).

[89] Stefano Pirandola “End-to-end capacities of a quantum communication network” Communications Physics 2, 51 (2019).

[90] Stefano Pirandola “Bounds for multi-end communication over quantum networks” Quantum Science and Technology 4, 045006 (2019).

[91] Siddhartha Das, Stefan Bäuml, Marek Winczewski, and Karol Horodecki, “Universal limitations on quantum key distribution over a network” arXiv:1912.03646 (2019).

[92] H.-J. Briegel, W. Dür, J. I. Cirac, and P. Zoller, “Quantum Repeaters: The Role of Imperfect Local Operations in Quantum Communication” Physical Review Letters 81, 5932–5935 (1998).

[93] W. Dür, H.-J. Briegel, J. I. Cirac, and P. Zoller, “Quantum repeaters based on entanglement purification” Physical Review A 59, 169–181 (1999).

[94] L.-M. Duan, M. D. Lukin, J. I. Cirac, and P. Zoller, “Long-distance quantum communication with atomic ensembles and linear optics” Nature 414 (2001).

[95] Robert M. Gingrich, Pieter Kok, Hwang Lee, Farrokh Vatan, and Jonathan P. Dowling, “All Linear Optical Quantum Memory Based on Quantum Error Correction” Physical Review Letters 91, 217901 (2003).

[96] T. C. Ralph, A. J. F. Hayes, and Alexei Gilchrist, “Loss-Tolerant Optical Qubits” Physical Review Letters 95, 100501 (2005).

[97] Liang Jiang, J. M. Taylor, Kae Nemoto, W. J. Munro, Rodney Van Meter, and M. D. Lukin, “Quantum repeater with encoding” Physical Review A 79, 032325 (2009).

[98] Austin G. Fowler, David S. Wang, Charles D. Hill, Thaddeus D. Ladd, Rodney Van Meter, and Lloyd C. L. Hollenberg, “Surface Code Quantum Communication” Physical Review Letters 104, 180503 (2010).

[99] M. Zwerger, W. Dür, and H. J. Briegel, “Measurement-based quantum repeaters” Physical Review A 85, 062326 (2012).

[100] W. J. Munro, A. M. Stephens, S. J. Devitt, K. A. Harrison, and Kae Nemoto, “Quantum communication without the necessity of quantum memories” Nature Photonics 6, 777 (2012).

[101] Sreraman Muralidharan, Jungsang Kim, Norbert Lütkenhaus, Mikhail D. Lukin, and Liang Jiang, “Ultrafast and Fault-Tolerant Quantum Communication across Long Distances” Physical Review Letters 112, 250501 (2014).

[102] M. Zwerger, H. J. Briegel, and W. Dür, “Measurement-based quantum communication” Applied Physics B 122, 50 (2016).

[103] Michael Epping, Hermann Kampermann, and Dagmar Bruß, “Large-scale quantum networks based on graphs” New Journal of Physics 18, 053036 (2016).

[104] Ryo Namiki, Liang Jiang, Jungsang Kim, and Norbert Lütkenhaus, “Role of syndrome information on a one-way quantum repeater using teleportation-based error correction” Physical Review A 94, 052304 (2016).

[105] Sreraman Muralidharan, Linshu Li, Jungsang Kim, Norbert Lütkenhaus, Mikhail D. Lukin, and Liang Jiang, “Optimal architectures for long distance quantum communication” Scientific Reports 6, 20463 (2016).

[106] Filippo M. Miatto, Michael Epping, and Norbert Lütkenhaus, “Hamiltonians for one-way quantum repeaters” Quantum 2, 75 (2018).

[107] Xiao Liu, Zong-Quan Zhou, Yi-Lin Hua, Chuan-Feng Li, and Guang-Can Guo, “Semihierarchical quantum repeaters based on moderate lifetime quantum memories” Physical Review A 95, 012319 (2017).

[108] Scott E. Vinay and Pieter Kok “Practical repeaters for ultralong-distance quantum communication” Physical Review A 95, 052336 (2017).

[109] F. Rozpędek, K. Goodenough, J. Ribeiro, N. Kalb, V. Caprara Vivoli, A. Reiserer, R. Hanson, S. Wehner, and D. Elkouss, “Parameter regimes for a single sequential quantum repeater” Quantum Science and Technology 3, 034002 (2018).

[110] Paul Hilaire, Edwin Barnes, and Sophia E. Economou, “Resource requirements for efficient quantum communication using all-photonic graph states generated from a few matter qubits” Quantum 5, 397 (2021).

[111] Nicolas Sangouard, Christoph Simon, Hugues de Riedmatten, and Nicolas Gisin, “Quantum repeaters based on atomic ensembles and linear optics” Reviews of Modern Physics 83, 33–80 (2011).

[112] W. J. Munro, K. Azuma, K. Tamaki, and K. Nemoto, “Inside Quantum Repeaters” IEEE Journal of Selected Topics in Quantum Electronics 21, 78–90 (2015).

[113] Rodney Van Meter “Quantum Networking” John Wiley & Sons, Ltd (2014).

[114] J. Wallnöfer, M. Zwerger, C. Muschik, N. Sangouard, and W. Dür, “Two-dimensional quantum repeaters” Physical Review A 94, 052307 (2016).

[115] M. Zwerger, A. Pirker, V. Dunjko, H. J. Briegel, and W. Dür, “Long-Range Big Quantum-Data Transmission” Physical Review Letters 120, 030503 (2018).

[116] Siddhartha Das, Sumeet Khatri, and Jonathan P. Dowling, “Robust quantum network architectures and topologies for entanglement distribution” Physical Review A 97, 012335 (2018).

[117] J. Wallnöfer, A. Pirker, M. Zwerger, and W. Dür, “Multipartite state generation in quantum networks with optimal scaling” Scientific Reports 9, 314 (2019).

[118] Axel Dahlberg, Matthew Skrzypczyk, Tim Coopmans, Leon Wubben, Filip Rozpędek, Matteo Pompili, Arian Stolk, Przemysław Pawełczak, Robert Knegjens, Julio de Oliveira Filho, Ronald Hanson, and Stephanie Wehner, “A Link Layer Protocol for Quantum Networks” Proceedings of the ACM Special Interest Group on Data Communication 159–173 (2019).

[119] Clément Meignant, Damian Markham, and Frédéric Grosshans, “Distributing graph states over arbitrary quantum networks” Physical Review A 100, 052333 (2019).

[120] Kaushik Chakraborty, David Elkouss, Bruno Rijsman, and Stephanie Wehner, “Entanglement Distribution in a Quantum Network, a Multi-Commodity Flow-Based Approach” arXiv:2005.14304 (2020).

[121] Kenneth Goodenough, David Elkouss, and Stephanie Wehner, “Optimising repeater schemes for the quantum internet” arXiv:2006.12221 (2020).

[122] Francisco Ferreira da Silva, Ariana Torres-Knoop, Tim Coopmans, David Maier, and Stephanie Wehner, “Optimizing Entanglement Generation and Distribution Using Genetic Algorithms” arXiv:2010.16373 (2020).

[123] W. Dai, T. Peng, and M. Z. Win, “Optimal Remote Entanglement Distribution” IEEE Journal on Selected Areas in Communications 38, 540–556 (2020).

[124] Mihir Pant, Hari Krovi, Don Towsley, Leandros Tassiulas, Liang Jiang, Prithwish Basu, Dirk Englund, and Saikat Guha, “Routing entanglement in the quantum internet” npj Quantum Information 5, 25 (2019).

[125] F. Hahn, A. Pappa, and J. Eisert, “Quantum network routing and local complementation” npj Quantum Information 5, 76 (2019).

[126] Changhao Li, Tianyi Li, Yi-Xiang Liu, and Paola Cappellaro, “Effective routing design for remote entanglement generation on quantum networks” arXiv:2001.02204 (2020).

[127] Yuan Lee, Eric Bersin, Axel Dahlberg, Stephanie Wehner, and Dirk Englund, “A Quantum Router Architecture for High-Fidelity Entanglement Flows in Multi-User Quantum Networks” arXiv:2005.01852 (2020).

[128] R. Van Meter, T. D. Ladd, W. J. Munro, and K. Nemoto, “System Design for a Long-Line Quantum Repeater” IEEE/​ACM Transactions on Networking 17, 1002–1013 (2009).

[129] Takaaki Matsuo, Clément Durand, and Rodney Van Meter, “Quantum link bootstrapping using a RuleSet-based communication protocol” Physical Review A 100, 052320 (2019).

[130] M. Razavi, K. Thompson, H. Farmanbar, Ma. Piani, and N. Lütkenhaus, “Physical and architectural considerations in quantum repeaters” Quantum Communications Realized II 7236, 18–30 (2009).

[131] Scott E. Vinay and Pieter Kok “Statistical analysis of quantum-entangled-network generation” Physical Review A 99, 042313 (2019).

[132] S. Brand, T. Coopmans, and D. Elkouss, “Efficient Computation of the Waiting Time and Fidelity in Quantum Repeater Chains” IEEE Journal on Selected Areas in Communications 38, 619–639 (2020).

[133] L. Hartmann, B. Kraus, H.-J. Briegel, and W. Dür, “Role of memory errors in quantum repeaters” Physical Review A 75, 032310 (2007).

[134] M. Razavi, M. Piani, and N. Lütkenhaus, “Quantum repeaters with imperfect memories: Cost and scalability” Physical Review A 80, 032301 (2009).

[135] Saikat Guha, Hari Krovi, Christopher A. Fuchs, Zachary Dutton, Joshua A. Slater, Christoph Simon, and Wolfgang Tittel, “Rate-loss analysis of an efficient quantum repeater architecture” Physical Review A 92, 022357 (2015).

[136] Hari Krovi, Saikat Guha, Zachary Dutton, Joshua A. Slater, Christoph Simon, and Wolfgang Tittel, “Practical quantum repeaters with parametric down-conversion sources” Applied Physics B 122, 52 (2016).

[137] V. V. Kuzmin, D. V. Vasilyev, N. Sangouard, W. Dür, and C. A. Muschik, “Scalable repeater architectures for multi-party states” npj Quantum Information 5, 115 (2019).

[138] Jennifer Barry, Daniel T. Barry, and Scott Aaronson, “Quantum partially observable Markov decision processes” Physical Review A 90, 032311 (2014).

[139] Guillermo Andres Cidre “Planning in a Quantum System” thesis (2016) https:/​/​​user/​gcidre/​.

[140] Shenggang Ying and Mingsheng Ying “Reachability analysis of quantum Markov decision processes” Information and Computation 263, 31–51 (2018).

[141] V. Dunjko, J. M. Taylor, and H. M. Briegel, “Framework for learning agents in quantum environments” arXiv:1507.08482 (2015).

[142] Vedran Dunjko, Jacob M. Taylor, and Hans J. Briegel, “Quantum-Enhanced Machine Learning” Physical Review Letters 117, 130501 (2016).

[143] Gus Gutoski and John Watrous “Toward a General Theory of Quantum Games” Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing 565–574 (2007) arXiv:quant-ph/​0611234.

[144] G. Chiribella, G. M. D’Ariano, and P. Perinotti, “Quantum Circuit Architecture” Physical Review Letters 101, 060401 (2008).

[145] Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti, “Theoretical framework for quantum networks” Physical Review A 80, 022339 (2009).

[146] Thomas Vidick and John Watrous “Quantum Proofs” Foundations and Trends® in Theoretical Computer Science 11, 1–215 (2016).

[147] Lieven Vandenberghe and Stephen Boyd “Semidefinite Programming” SIAM Review 38, 49–95 (1996).

[148] Mislav Cvitković, Ana-Sunčana Smith, and Jayant Pande, “Asymptotic expansions of the hypergeometric function with two large parameters—application to the partition function of a lattice gas in a field of traps” Journal of Physics A: Mathematical and Theoretical 50, 265206 (2017).

Cited by

[1] Koji Azuma, Stefan Bäuml, Tim Coopmans, David Elkouss, and Boxi Li, “Tools for quantum network design”, AVS Quantum Science 3 1, 014101 (2021).

[2] Laszlo Gyongyosi, “Objective function estimation for solving optimization problems in gate-model quantum computers”, Scientific Reports 10, 14220 (2020).

[3] Laszlo Gyongyosi, “Decoherence dynamics estimation for superconducting gate-model quantum computers”, Quantum Information Processing 19 10, 369 (2020).

[4] Laszlo Gyongyosi and Sandor Imre, “Scalable distributed gate-model quantum computers”, Scientific Reports 11, 5172 (2021).

[5] Laszlo Gyongyosi and Sandor Imre, “Resource prioritization and balancing for the quantum internet”, Scientific Reports 10, 22390 (2020).

The above citations are from SAO/NASA ADS (last updated successfully 2021-09-07 14:09:42). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2021-09-07 14:09:39: Could not fetch cited-by data for 10.22331/q-2021-09-07-537 from Crossref. This is normal if the DOI was registered recently.

PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.



Trapping Sets of Quantum LDPC Codes



Nithin Raveendran and Bane Vasić

Department of Electrical and Computer Engineering, University of Arizona, Tucson, AZ 85721, USA

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


Iterative decoders for finite length quantum low-density parity-check (QLDPC) codes are attractive because their hardware complexity scales only linearly with the number of physical qubits. However, they are impacted by short cycles, detrimental graphical configurations known as trapping sets (TSs) present in a code graph as well as symmetric degeneracy of errors. These factors significantly degrade the decoder decoding probability performance and cause so-called error floor. In this paper, we establish a systematic methodology by which one can identify and classify quantum trapping sets (QTSs) according to their topological structure and decoder used. The conventional definition of a TS from classical error correction is generalized to address the syndrome decoding scenario for QLDPC codes. We show that the knowledge of QTSs can be used to design better QLDPC codes and decoders. Frame error rate improvements of two orders of magnitude in the error floor regime are demonstrated for some practical finite-length QLDPC codes without requiring any post-processing.

Quantum low-density parity-check (QLDPC) codes have recently gained popularity as an important class of quantum error correction codes due to their ability to realize scalable fault-tolerant quantum computers with constant overhead and are decodable using efficient iterative decoders. However, QLDPC code’s decoding performance is impacted by short cycles and detrimental graphical configurations present in their code graph. Such a performance degradation at low noise values – referred to as error floor effect will be severe especially in the case of practically useful finite length QLDPC codes. In classical LDPC coding literature, these harmful configurations classified as $textit{trapping sets}$ (TSs) have been well studied and have aided to develop low-complexity iterative decoders that surpass the conventional belief propagation decoder. However, TSs have never been formally studied in the context of QLDPC codes and their decoding. In this work, we introduce the concept of $textit{Quantum Trapping Sets}$ (QTSs) by investigating the failure configurations for syndrome-based iterative decoders. We establish a systematic methodology by which one can identify and classify QTSs according to their topological structure and decoder used. The conventional definition of a TS from classical error correction is generalized to address the syndrome decoding scenario for QLDPC codes. As a summary, we observe two types of QTSs – one is similar to classical TSs and the other is referred to as symmetric stabilizer TSs – these are unique to QLDPC codes. The properties of symmetric stabilizer TSs are distinct and specific to the QLDPC decoding problem and hence, will be instrumental in exploiting the degeneracy of QLDPC codes to the decoder’s advantage. Furthermore, we demonstrate the two advantages of studying QTSs – (1) Design better QLDPC codes – ability to construct QLDPC codes devoid of harmful QTSs, (2) Design better decoders without post-processing steps – ability to devise new decoding algorithms that escape from harmful QTSs and have low error floors.

► BibTeX data

► References

[1] N. Raveendran and B. Vasić. Trapping set analysis of finite-length quantum LDPC codes. In IEEE Int. Symp. on Inform. Theory, pages 1564–1569, 2021. 10.1109/​ISIT45174.2021.9518154.

[2] D. J. C. MacKay, G. Mitchison, and P. L. McFadden. Sparse-graph codes for quantum error correction. IEEE Trans. on Inform. Theory, 50 (10): 2315–2330, Oct. 2004. 10.1109/​TIT.2004.834737.

[3] P. W. Shor. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A, 52: R2493–R2496, Oct. 1995. 10.1103/​PhysRevA.52.R2493.

[4] D. Gottesman. Fault-tolerant quantum computation with constant overhead. Quantum Inform. and Computation, 14 (15–16): 1338–1372, Nov. 2014. 10.26421/​QIC14.15-16-5.

[5] A. A. Kovalev and L. P. Pryadko. Fault tolerance of quantum low-density parity check codes with sublinear distance scaling. Phys. Rev. A, 87: 020304, Feb. 2013a. 10.1103/​PhysRevA.87.020304.

[6] Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo. The road from classical to quantum codes: A hashing bound approaching design procedure. IEEE Access, 3: 146–176, 2015a. 10.1109/​ACCESS.2015.2405533.

[7] Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo. Fifteen years of quantum LDPC coding and improved decoding strategies. IEEE Access, 3: 2492–2519, 2015b. 10.1109/​ACCESS.2015.2503267.

[8] J.-P. Tillich and G. Zémor. Quantum LDPC codes with positive rate and minimum distance proportional to $n^{1/​2}$. Proc. IEEE Int. Symp. on Inform. Theory, pages 799–803, Jul. 2009. 10.1109/​ISIT.2009.5205648.

[9] A. Leverrier, J.-P. Tillich, and G. Zémor. Quantum expander codes. In Proc. IEEE 56th Ann. Symp. on Foundations of Computer Science, pages 810–824, Berkeley, CA, USA, Oct. 2015. 10.1109/​FOCS.2015.55.

[10] P. Panteleev and G. Kalachev. Quantum LDPC codes with almost linear minimum distance. arXiv preprint:2012.04068, 2020. URL https:/​/​​abs/​2012.04068.

[11] K.-Y. Kuo and C.-Y. Lai. Refined belief propagation decoding of sparse-graph quantum codes. IEEE Journal on Selected Areas in Information Theory, 1 (2): 487–498, 2020. 10.1109/​jsait.2020.3011758.

[12] C.-Y. Lai and K.-Y. Kuo. Log-domain decoding of quantum LDPC codes over binary finite fields. IEEE Trans. on Quantum Engineering, 2021. 10.1109/​TQE.2021.3113936.

[13] D. Poulin and Y. Chung. On the iterative decoding of sparse quantum codes. Quantum Inform. and Computation, 8 (10): 987–1000, Nov. 2008. 10.26421/​QIC8.10-8.

[14] T. J. Richardson. Error floors of LDPC codes. In Proc. 41st Ann. Allerton Conf. Commun., Contr. and Comp., pages 1426–1435, Monticello, IL, USA, Sept. 2003. URL https:/​/​​class/​ee388/​papers/​ErrorFloors.pdf.

[15] P. Panteleev and G. Kalachev. Degenerate quantum LDPC codes with good finite length performance. arXiv preprint:1904.02703, 2019. URL https:/​/​​abs/​1904.02703.

[16] B. Vasić, D. V. Nguyen, and S. K. Chilappagari. Chapter 6 – failures and error floors of iterative decoders. In Channel Coding: Theory, Algorithms, and Applications: Academic Press Library in Mobile and Wireless Commun., pages 299–341, Oxford, 2014. Academic Press. 10.1016/​B978-0-12-396499-1.00006-6.

[17] J. Roffe, D. R. White, S. Burton, and E. Campbell. Decoding across the quantum low-density parity-check code landscape. Phys. Rev. Research, 2: 043423, Dec. 2020. 10.1103/​PhysRevResearch.2.043423.

[18] M. P. C. Fossorier and S. Lin. Soft-decision decoding of linear block codes based on ordered statistics. IEEE Trans. on Inform. Theory, 41: 1379 – 1396, 10 1995. 10.1109/​18.412683.

[19] M. Baldi, N. Maturo, E. Paolini, and F. Chiaraluce. On the use of ordered statistics decoders for low-density parity-check codes in space telecommand links. EURASIP J. Wirel. Commun. Netw., 2016 (272): 1– 15, 2016. 10.1186/​s13638-016-0769-z.

[20] A. Rigby, J. C. Olivier, and P. Jarvis. Modified belief propagation decoders for quantum low-density parity-check codes. Phys. Rev. A, 100: 012330, Jul. 2019. 10.1103/​physreva.100.012330.

[21] J. X. Li and P. O. Vontobel. Pseudocodeword-based decoding of quantum stabilizer codes. In Proc. IEEE Int. Symp. on Inform. Theory, pages 2888–2892, 2019. 10.1109/​ISIT.2019.8849833.

[22] N. Raveendran, D. Declercq, and B. Vasić. A sub-graph expansion-contraction method for error floor computation. IEEE Trans. on Commun., 68 (7): 3984–3995, 2020. 10.1109/​TCOMM.2020.2988676.

[23] S. K. Planjery, D. Declercq, L. Danjean, and B. Vasić. Finite alphabet iterative decoders, Part I: Decoding beyond belief propagation on the binary symmetric channel. IEEE Trans. on Commun., 61 (10): 4033–4045, Nov. 2013. 10.1109/​TCOMM.2013.090513.120443.

[24] A. R. Calderbank and P. W. Shor. Good quantum error-correcting codes exist. Physical Review A, 54 (2): 1098–1105, Aug. 1996. ISSN 1094-1622. 10.1103/​physreva.54.1098.

[25] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, New York, NY, USA, 10th edition, 2011. 10.1017/​CBO9780511976667.

[26] D. Gottesman. Stabilizer codes and quantum error correction. Ph.D. Dissertation, California Institute of Technology, 1997. 10.7907/​rzr7-dt72. URL https:/​/​​abs/​quant-ph/​9705052.

[27] M. M. Wilde. Logical operators of quantum codes. Phys. Rev. A, 79: 062322, Jun. 2009. 10.1103/​PhysRevA.79.062322.

[28] N. Raveendran, P. J. Nadkarni, S. S. Garani, and B. Vasić. Stochastic resonance decoding for quantum LDPC codes. In Proc. IEEE Int. Conf. on Commun., pages 1–6, May 2017. 10.1109/​ICC.2017.7996747.

[29] M. Karimi and A. H. Banihashemi. Efficient algorithm for finding dominant trapping sets of LDPC codes. IEEE Trans. on Inform. Theory, 58 (11): 6942–6958, Nov. 2012. 10.1109/​TIT.2012.2205663.

[30] D. V. Nguyen, S. K. Chilappagari, M. W. Marcellin, and B. Vasić. On the construction of structured LDPC codes free of small trapping sets. IEEE Trans. on Inform. Theory, 58 (4): 2280–2302, Apr. 2012. 10.1109/​TIT.2011.2173733.

[31] S. M. Khatami, L. Danjean, D. V. Nguyen, and B. Vasić. An efficient exhaustive low-weight codeword search for structured LDPC codes. In Proc. Inform. Theory and Applications Workshop, pages 1 – 10, San Diego, CA, USA, Feb. 10–15 2013. 10.1109/​ITA.2013.6502981.

[32] Z. Babar, P. Botsinis, D. Alanis, S. X. Ng, and L. Hanzo. Construction of quantum LDPC codes from classical row-circulant QC-LDPCs. IEEE Commun. Letters, 20 (1): 9–12, Jan. 2016. 10.1109/​LCOMM.2015.2494020.

[33] M. Hagiwara and H. Imai. Quantum quasi-cyclic LDPC codes. In Proc. IEEE Int. Symp. on Inform. Theory, pages 806–810, Jun. 2007. 10.1109/​ISIT.2007.4557323.

[34] Y. Xie and J. Yuan. Reliable quantum LDPC codes over GF(4). In Proc. IEEE Globecom Workshops, pages 1–5, Dec. 2016. 10.1109/​GLOCOMW.2016.7849021.

[35] A. A. Kovalev and L. P. Pryadko. Quantum kronecker sum-product low-density parity-check codes with finite rate. Phys. Rev. A, 88: 012311, Jul. 2013b. 10.1103/​PhysRevA.88.012311.

[36] A. A. Kovalev and L. P. Pryadko. Improved quantum hypergraph-product LDPC codes. In Proc. IEEE Int. Symp. on Inform. Theory, pages 348–352, Jul. 2012. 10.1109/​ISIT.2012.6284206.

[37] M. P. C. Fossorier. Quasi-cyclic low-density parity-check codes from circulant permutation matrices. IEEE Trans. on Inform. Theory, 50 (8): 1788–1793, Aug. 2004. 10.1109/​TIT.2004.831841.

[38] D. E. Hocevar. A reduced complexity decoder architecture via layered decoding of LDPC codes. In Proc. IEEE Workshop on Signal Processing Systems, pages 107–112, 2004. 10.1109/​SIPS.2004.1363033.

[39] E. Sharon, S. Litsyn, and J. Goldberger. Efficient serial message-passing schedules for LDPC decoding. IEEE Trans. on Inform. Theory, 53 (11): 4076–4091, 2007. 10.1109/​TIT.2007.907507.

[40] N. Raveendran and B. Vasić. Trapping set analysis of horizontal layered decoder. In Proc. IEEE Int. Conf. on Commun., pages 1–6, May 2018. 10.1109/​ICC.2018.8422965.

[41] Y.-J. Wang, B. C. Sanders, B.-M. Bai, and X.-M. Wang. Enhanced feedback iterative decoding of sparse quantum codes. IEEE Trans. on Inform. Theory, 58 (2): 1231–1241, Feb. 2012. 10.1109/​TIT.2011.2169534.

Cited by

[1] Kao-Yueh Kuo and Ching-Yi Lai, “Exploiting Degeneracy in Belief Propagation Decoding of Quantum Codes”, arXiv:2104.13659.

[2] Kao-Yueh Kuo, I-Chun Chern, and Ching-Yi Lai, “Decoding of Quantum Data-Syndrome Codes via Belief Propagation”, arXiv:2102.01984.

[3] Ching-Yi Lai and Kao-Yueh Kuo, “Log-domain decoding of quantum LDPC codes over binary finite fields”, arXiv:2104.00304.

[4] Patricio Fuentes, Josu Etxezarreta Martinez, Pedro M. Crespo, and Javier Garcia-Frias, “On the logical error rate of sparse quantum codes”, arXiv:2108.10645.

The above citations are from SAO/NASA ADS (last updated successfully 2021-10-14 18:26:04). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2021-10-14 18:26:02: Could not fetch cited-by data for 10.22331/q-2021-10-14-562 from Crossref. This is normal if the DOI was registered recently.

PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.


Continue Reading


Entangled symmetric states and copositive matrices



Carlo Marconi1, Albert Aloy2, Jordi Tura3,4, and Anna Sanpera1,5

1Física Teòrica: Informació i Fenòmens Quàntics. Departament de Física, Universitat Autònoma de Barcelona, 08193 Bellaterra, Spain
2ICFO – Institut de Ciències Fotòniques, The Barcelona Institute of Science and Technology, 08860 Castelldefels (Barcelona), Spain
3Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Str. 1, 85748 Garching, Germany
4Instituut-Lorentz, Universiteit Leiden, P.O. Box 9506, 2300 RA Leiden, The Netherlands
5ICREA, Pg. Lluís Companys 23, 08010 Barcelona, Spain

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


Entanglement in symmetric quantum states and the theory of copositive matrices are intimately related concepts. For the simplest symmetric states, i.e., the diagonal symmetric (DS) states, it has been shown that there exists a correspondence between exceptional (non-exceptional) copositive matrices and non-decomposable (decomposable) Entanglement Witnesses (EWs). Here we show that EWs of symmetric, but not DS, states can also be constructed from extended copositive matrices, providing new examples of bound entangled symmetric states, together with their corresponding EWs, in arbitrary odd dimensions.

Entanglement is one of the most intriguing phenomena in quantum physics whose implications have profound consequences not only from a theoretical point of view but also in light of some computational tasks that would be otherwise unfeasible with classical systems.
For this reason, deciding whether a quantum state is entangled or not, is a problem of paramount importance whose solution, unfortunately, is known to be NP-hard in the general scenario.
In some cases, however, symmetries provide a useful framework to recast the separability problem in a simpler way, thus reducing the original complexity of this task.
In this work we focus on symmetric states, i.e., states that are invariant under permutations of the parties, showing how, in the case of the qudits, the characterization of the entanglement can be accomplished by means of a class of matrices known as copositive. In particular, we establish a connection between entanglement witnesses, i.e., hermitian operators that are able to detect entanglement, and copositive matrices, showing how only a subset of them, dubbed as exceptional, can be used to assess PPT-entanglement in any dimension, with the PPT-entangled edge states detected by the so-called extremal matrices.
Finally we illustrate our findings discussing some examples of families of PPT-entangled states in 3-level and 4-level systems, along with the entanglement witnesses that detect them.
We conjecture that any PPT-entangled state of two qudits can be detected by means of an entanglement witness of the form that we propose.

► BibTeX data

► References

[1] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki. Quantum entanglement. Reviews of modern physics, 81 (2): 865, 2009. 10.1103/​RevModPhys.81.865.

[2] Charles H Bennett, Herbert J Bernstein, Sandu Popescu, and Benjamin Schumacher. Concentrating partial entanglement by local operations. Physical Review A, 53 (4): 2046, 1996. 10.1103/​PhysRevA.53.2046.

[3] Leonid Gurvits. Classical deterministic complexity of edmonds’ problem and quantum entanglement. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 10–19, 2003. 10.1145/​780542.780545.

[4] Asher Peres. Separability criterion for density matrices. Physical Review Letters, 77 (8): 1413, 1996. 10.1103/​PhysRevLett.77.1413.

[5] Barbara M Terhal and Karl Gerd H Vollbrecht. Entanglement of formation for isotropic states. Physical Review Letters, 85 (12): 2625, 2000. 10.1103/​PhysRevLett.85.2625.

[6] Maciej Lewenstein, Barabara Kraus, J Ignacio Cirac, and P Horodecki. Optimization of entanglement witnesses. Physical Review A, 62 (5): 052310, 2000. 10.1103/​PhysRevA.62.052310.

[7] Dariusz Chruściński and Gniewomir Sarbicki. Entanglement witnesses: construction, analysis and classification. Journal of Physics A: Mathematical and Theoretical, 47 (48): 483001, 2014. 10.1088/​1751-8113/​47/​48/​483001.

[8] Maciej Lewenstein, B Kraus, P Horodecki, and JI Cirac. Characterization of separable states and entanglement witnesses. Physical Review A, 63 (4): 044304, 2001. 10.1103/​PhysRevA.63.044304.

[9] Fernando GSL Brandao. Quantifying entanglement with witness operators. Physical Review A, 72 (2): 022310, 2005. 10.1103/​physreva.72.022310.

[10] Karl Gerd H Vollbrecht and Reinhard F Werner. Entanglement measures under symmetry. Physical Review A, 64 (6): 062307, 2001. 10.1103/​PhysRevA.64.062307.

[11] Géza Tóth and Otfried Gühne. Separability criteria and entanglement witnesses for symmetric quantum states. Applied Physics B, 98 (4): 617–622, 2010. 10.1007/​s00340-009-3839-7.

[12] Tilo Eggeling and Reinhard F Werner. Separability properties of tripartite states with u $otimes$ u $otimes$ u $otimes$ symmetry. Physical Review A, 63 (4): 042111, 2001. 10.1103/​physreva.63.042111.

[13] Jordi Tura, Albert Aloy, Ruben Quesada, Maciej Lewenstein, and Anna Sanpera. Separability of diagonal symmetric states: a quadratic conic optimization problem. Quantum, 2: 45, 2018. 10.22331/​q-2018-01-12-45.

[14] Anna Sanpera, Dagmar Bruß, and Maciej Lewenstein. Schmidt-number witnesses and bound entanglement. Physical Review A, 63 (5): 050301, 2001. 10.1103/​PhysRevA.63.050301.

[15] Lieven Clarisse. Construction of bound entangled edge states with special ranks. Physics Letters A, 359 (6): 603–607, 2006. 10.1016/​j.physleta.2006.07.045.

[16] Seung-Hyeok Kye and Hiroyuki Osaka. Classification of bi-qutrit positive partial transpose entangled edge states by their ranks. Journal of mathematical physics, 53 (5): 052201, 2012. 10.1063/​1.4712302.

[17] Lin Chen and Dragomir Ž Ðoković. Description of rank four entangled states of two qutrits having positive partial transpose. Journal of mathematical physics, 52 (12): 122203, 2011. 10.1063/​1.3663837.

[18] Jon Magne Leinaas, Jan Myrheim, and Per Øyvind Sollid. Low-rank extremal positive-partial-transpose states and unextendible product bases. Phys. Rev. A, 81: 062330, Jun 2010. 10.1103/​PhysRevA.81.062330.

[19] Nengkun Yu. Separability of a mixture of dicke states. Physical Review A, 94 (6): 060101, 2016. 10.1103/​PhysRevA.94.060101.

[20] Katta G. Murty and Santosh N. Kabadi. Some np-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39: 117–129, 1987. 10.1007/​BF02592948.

[21] Li Ping and Feng Yu Yu. Criteria for copositive matrices of order four. Linear algebra and its applications, 194: 109–124, 1993. 10.1016/​0024-3795(93)90116-6.

[22] J-B Hiriart-Urruty and Alberto Seeger. A variational approach to copositive matrices. SIAM review, 52 (4): 593–629, 2010. 10.1137/​090750391.

[23] Palahenedi Hewage Diananda. On non-negative forms in real variables some or all of which are non-negative. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 58, pages 17–25. Cambridge University Press, 1962. 10.1017/​s0305004100036185.

[24] Marshall Hall and Morris Newman. Copositive and completely positive quadratic forms. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 59, pages 329–339. Cambridge University Press, 1963. 10.1017/​s0305004100036951.

[25] Charles Johnson and Robert Reams. Constructing copositive matrices from interior matrices. The Electronic Journal of Linear Algebra, 17: 9–20, 2008. 10.13001/​1081-3810.1245.

[26] Alan J Hoffman and Francisco Pereira. On copositive matrices with- 1, 0, 1 entries. Journal of Combinatorial Theory, Series A, 14 (3): 302–309, 1973. 10.1016/​0097-3165(73)90006-x.

[27] Dariusz Chruściński and Andrzej Kossakowski. Circulant states with positive partial transpose. Phys. Rev. A, 76: 032308, Sep 2007. 10.1103/​PhysRevA.76.032308.

[28] Andrew C Doherty, Pablo A Parrilo, and Federico M Spedalieri. Complete family of separability criteria. Physical Review A, 69 (2): 022308, 2004. 10.1103/​PhysRevA.69.022308.

[29] Andrew C Doherty, Pablo A Parrilo, and Federico M Spedalieri. Distinguishing separable and entangled states. Physical Review Letters, 88 (18): 187904, 2002. 10.1103/​physrevlett.88.187904.

Cited by

[1] Adam Burchardt, Jakub Czartowski, and Karol Życzkowski, “Entanglement in highly symmetric multipartite quantum states”, Physical Review A 104 2, 022426 (2021).

[2] Hari krishnan S V, Ashish Ranjan, and Manik Banik, “State space structure of tripartite quantum systems”, Physical Review A 104 2, 022437 (2021).

[3] Joonwoo Bae, Anindita Bera, Dariusz Chruściński, Beatrix C. Hiesmayr, and Daniel McNulty, “How many measurements are needed to detect bound entangled states?”, arXiv:2108.01109.

[4] Beatrix C. Hiesmayr, “Free versus Bound Entanglement: Machine learning tackling a NP-hard problem”, arXiv:2106.03977.

The above citations are from SAO/NASA ADS (last updated successfully 2021-10-07 15:38:09). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2021-10-07 15:38:08: Could not fetch cited-by data for 10.22331/q-2021-10-07-561 from Crossref. This is normal if the DOI was registered recently.

PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.


Continue Reading


The Quantum Supremacy Tsirelson Inequality



William Kretschmer

Department of Computer Science, The University of Texas at Austin, Austin, TX 78712, USA

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


A leading proposal for verifying near-term quantum supremacy experiments on noisy random quantum circuits is linear cross-entropy benchmarking. For a quantum circuit $C$ on $n$ qubits and a sample $z in {0,1}^n$, the benchmark involves computing $|langle z|C|0^n rangle|^2$, i.e. the probability of measuring $z$ from the output distribution of $C$ on the all zeros input. Under a strong conjecture about the classical hardness of estimating output probabilities of quantum circuits, no polynomial-time classical algorithm given $C$ can output a string $z$ such that $|langle z|C|0^nrangle|^2$ is substantially larger than $frac{1}{2^n}$ (Aaronson and Gunn, 2019). On the other hand, for a random quantum circuit $C$, sampling $z$ from the output distribution of $C$ achieves $|langle z|C|0^nrangle|^2 approx frac{2}{2^n}$ on average (Arute et al., 2019).
In analogy with the Tsirelson inequality from quantum nonlocal correlations, we ask: can a polynomial-time quantum algorithm do substantially better than $frac{2}{2^n}$? We study this question in the query (or black box) model, where the quantum algorithm is given oracle access to $C$. We show that, for any $varepsilon ge frac{1}{mathrm{poly}(n)}$, outputting a sample $z$ such that $|langle z|C|0^nrangle|^2 ge frac{2 + varepsilon}{2^n}$ on average requires at least $Omegaleft(frac{2^{n/4}}{mathrm{poly}(n)}right)$ queries to $C$, but not more than $Oleft(2^{n/3}right)$ queries to $C$, if $C$ is either a Haar-random $n$-qubit unitary, or a canonical state preparation oracle for a Haar-random $n$-qubit state. We also show that when $C$ samples from the Fourier distribution of a random Boolean function, the naive algorithm that samples from $C$ is the optimal 1-query algorithm for maximizing $|langle z|C|0^nrangle|^2$ on average.

Recent quantum supremacy experiments were verified using a statistical test called the “Linear Cross-Entropy Benchmark” (or Linear XEB). This benchmark was chosen because of complexity-theoretic evidence that an efficient quantum algorithm can achieve a higher Linear XEB score than any possible efficient classical algorithm.

We argue that this upper bound on the power of classical algorithms for the Linear XEB is analogous to the Bell inequality in nonlocal correlations: both capture inherent limits on the power of classical information and computation that may be violated in the quantum setting. Motivated by this connection, we ask: what is the quantum supremacy analogue of the Tsirelson inequality? That is, what is the highest Linear XEB score achievable by an efficient quantum algorithm? We give evidence that the naive quantum algorithm for passing the benchmark is essentially optimal in this regard.

► BibTeX data

► References

[1] Scott Aaronson. Random circuit sampling: Thoughts and open problems. The Quantum Wave in Computing, 2020. URL https:/​/​​talks/​tbd-124.

[2] Scott Aaronson and Lijie Chen. Complexity-Theoretic Foundations of Quantum Supremacy Experiments. In Ryan O’Donnell, editor, 32nd Computational Complexity Conference (CCC 2017), volume 79 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1–22:67, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-040-8. 10.4230/​LIPIcs.CCC.2017.22. URL http:/​/​​opus/​volltexte/​2017/​7527.

[3] Scott Aaronson and Sam Gunn. On the classical hardness of spoofing linear cross-entropy benchmarking. Theory of Computing, 16 (11): 1–8, 2020. 10.4086/​toc.2020.v016a011. URL http:/​/​​articles/​v016a011.

[4] Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler. Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. In Shubhangi Saraf, editor, 35th Computational Complexity Conference (CCC 2020), volume 169 of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1–7:47, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. ISBN 978-3-95977-156-6. 10.4230/​LIPIcs.CCC.2020.7. URL https:/​/​​opus/​volltexte/​2020/​12559.

[5] Dorit Aharonov, Alexei Kitaev, and Noam Nisan. Quantum circuits with mixed states. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC ’98, page 20–30, New York, NY, USA, 1998. Association for Computing Machinery. ISBN 0897919629. 10.1145/​276698.276708. URL https:/​/​​10.1145/​276698.276708.

[6] Andris Ambainis. Understanding quantum algorithms via query complexity. In Proceedings of the 2018 International Congress of Mathematicians, volume 3, pages 3249–3270, 2018. 10.1142/​9789813272880_0181.

[7] Andris Ambainis, Loïck Magnin, Martin Roetteler, and Jeremie Roland. Symmetry-assisted adversaries for quantum state generation. In Proceedings of the 2011 IEEE 26th Annual Conference on Computational Complexity, CCC ’11, page 167–177, USA, 2011. IEEE Computer Society. ISBN 9780769544113. 10.1109/​CCC.2011.24. URL https:/​/​​10.1109/​CCC.2011.24.

[8] Andris Ambainis, Ansis Rosmanis, and Dominique Unruh. Quantum attacks on classical proof systems: The hardness of quantum rewinding. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, FOCS ’14, page 474–483, USA, 2014. IEEE Computer Society. ISBN 9781479965175. 10.1109/​FOCS.2014.57. URL https:/​/​​10.1109/​FOCS.2014.57.

[9] Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf. Quantum Coupon Collector. In Steven T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. ISBN 978-3-95977-146-7. 10.4230/​LIPIcs.TQC.2020.10. URL https:/​/​​opus/​volltexte/​2020/​12069.

[10] Frank Arute, Kunal Arya, Ryan Babbush, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779): 505–510, 2019. 10.1038/​s41586-019-1666-5. URL https:/​/​​10.1038/​s41586-019-1666-5.

[11] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. J. ACM, 48 (4): 778–797, July 2001. ISSN 0004-5411. 10.1145/​502090.502097. URL https:/​/​​10.1145/​502090.502097.

[12] John Bell. On the Einstein-Podolsky-Rosen paradox. Physics, 1: 195–200, Nov 1964. 10.1103/​PhysicsPhysiqueFizika.1.195. URL https:/​/​​doi/​10.1103/​PhysicsPhysiqueFizika.1.195.

[13] Aleksandrs Belovs. Variations on quantum adversary, 2015.

[14] Aleksandrs Belovs and Ansis Rosmanis. Tight quantum lower bound for approximate counting with quantum states, 2020.

[15] Fernando G. S. L. Brandão, Aram W. Harrow, and Michał Horodecki. Local random quantum circuits are approximate polynomial-designs. Communications in Mathematical Physics, 346 (2): 397–434, 2016. 10.1007/​s00220-016-2706-8. URL https:/​/​​10.1007/​s00220-016-2706-8.

[16] Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum cryptanalysis of hash and claw-free functions. SIGACT News, 28 (2): 14–19, June 1997. ISSN 0163-5700. 10.1145/​261342.261346. URL https:/​/​​10.1145/​261342.261346.

[17] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information, volume 305 of Contemporary Mathematics, pages 53–74. American Mathematical Society, 2002. ISBN 9780821821404. 10.1090/​conm/​305.

[18] Mark Bun and Justin Thaler. Dual lower bounds for approximate degree and Markov-Bernstein inequalities. Inf. Comput., 243 (C): 2–25, August 2015. ISSN 0890-5401. 10.1016/​j.ic.2014.12.003. URL https:/​/​​10.1016/​j.ic.2014.12.003.

[19] Boris Cirel’son (Tsirelson). Quantum generalizations of Bell’s inequality. Letters in Mathematical Physics, 4 (2): 93–100, 1980. 10.1007/​BF00417500. URL https:/​/​​10.1007/​BF00417500.

[20] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett., 23: 880–884, Oct 1969. 10.1103/​PhysRevLett.23.880. URL https:/​/​​doi/​10.1103/​PhysRevLett.23.880.

[21] Richard Cleve, Peter Høyer, Benjamin Toner, and John Watrous. Consequences and limits of nonlocal strategies. In Proceedings of the 19th IEEE Annual Conference on Computational Complexity, CCC ’04, page 236–249, USA, 2004. IEEE Computer Society. ISBN 0769521207. 10.1109/​CCC.2004.1313847.

[22] Aram Harrow and Saeed Mehraban. Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates, 2018.

[23] Norman L. Johnson and Samuel Kotz. Urn models and their application: an approach to modern discrete probability theory. Wiley, 1977. ISBN 9780471446309.

[24] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols, and Theodore J. Yoder. Hamiltonian simulation with optimal sample complexity. npj Quantum Information, 3 (1): 13, 2017. 10.1038/​s41534-017-0013-7. URL https:/​/​​10.1038/​s41534-017-0013-7.

[25] William Kretschmer. The Quantum Supremacy Tsirelson Inequality. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1–13:13, Dagstuhl, Germany, 2021. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. ISBN 978-3-95977-177-1. 10.4230/​LIPIcs.ITCS.2021.13. URL https:/​/​​opus/​volltexte/​2021/​13552.

[26] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy. Quantum query complexity of state conversion. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS ’11, page 344–353, USA, 2011. IEEE Computer Society. ISBN 9780769545714. 10.1109/​FOCS.2011.75. URL https:/​/​​10.1109/​FOCS.2011.75.

[27] Nathan Lindzey and Ansis Rosmanis. A Tight Lower Bound For Non-Coherent Index Erasure. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 59:1–59:37, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-134-4. 10.4230/​LIPIcs.ITCS.2020.59. URL https:/​/​​opus/​volltexte/​2020/​11744.

[28] Frederic Magniez, Ashwin Nayak, Jeremie Roland, and Miklos Santha. Search via quantum walk. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07, page 575–584, New York, NY, USA, 2007. Association for Computing Machinery. ISBN 9781595936318. 10.1145/​1250790.1250874. URL https:/​/​​10.1145/​1250790.1250874.

[29] Ryan O’Donnell. Analysis of Boolean Functions. Cambridge University Press, USA, 2014. ISBN 1107038324. 10.1017/​CBO9781139814782.

[30] Martin Raab and Angelika Steger. “Balls into bins” – a simple and tight analysis. In Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM ’98, pages 159–170, Berlin, Heidelberg, 1998. Springer-Verlag. ISBN 354065142X. 10.1007/​3-540-49543-6_13.

[31] Ben W. Reichardt. Reflections for quantum query algorithms. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’11, page 560–569, USA, 2011. Society for Industrial and Applied Mathematics. 10.1137/​1.9781611973082.44.

[32] Alfréd Rényi. On the theory of order statistics. Acta Mathematica Academiae Scientiarum Hungarica, 4 (3): 191–231, 1953. 10.1007/​BF02127580. URL https:/​/​​10.1007/​BF02127580.

Cited by

[1] Daniel Stilck França and Raul Garcia-Patron, “A game of quantum advantage: linking verification and simulation”, arXiv:2011.12173.

[2] Nicholas LaRacuente, “Quantum Oracle Separations from Complex but Easily Specified States”, arXiv:2104.07247.

[3] Scott Aaronson, “Open Problems Related to Quantum Query Complexity”, arXiv:2109.06917.

The above citations are from SAO/NASA ADS (last updated successfully 2021-10-07 11:15:15). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2021-10-07 11:15:13: Could not fetch cited-by data for 10.22331/q-2021-10-07-560 from Crossref. This is normal if the DOI was registered recently.

PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.


Continue Reading


Mathematicians Prove Melting Ice Stays Smooth



Drop an ice cube into a glass of water. You can probably picture the way it starts to melt. You also know that no matter what shape it takes, you’ll never see it melt into something like a snowflake, composed everywhere of sharp edges and fine cusps.

Mathematicians model this melting process with equations. The equations work well, but it’s taken 130 years to prove that they conform to obvious facts about reality. Now, in a paper posted in March, Alessio Figalli and Joaquim Serra of the Swiss Federal Institute of Technology Zurich and Xavier Ros-Oton of the University of Barcelona have established that the equations really do match intuition. Snowflakes in the model may not be impossible, but they are extremely rare and entirely fleeting.

“These results open a new perspective on the field,” said Maria Colombo of the Swiss Federal Institute of Technology Lausanne. “There was no such deep and precise understanding of this phenomenon previously.”

The question of how ice melts in water is called the Stefan problem, named after the physicist Josef Stefan, who posed it in 1889. It is the most important example of a “free boundary” problem, where mathematicians consider how a process like the diffusion of heat makes a boundary move. In this case, the boundary is between ice and water.

For many years, mathematicians have tried to understand the complicated models of these evolving boundaries. To make progress, the new work draws inspiration from previous studies on a different type of physical system: soap films. It builds on them to prove that along the evolving boundary between ice and water, sharp spots like cusps or edges rarely form, and even when they do, they immediately disappear.

These sharp spots are called singularities, and, it turns out, they are as ephemeral in the free boundaries of mathematics as they are in the physical world.

Melting Hourglasses

Consider, again, an ice cube in a glass of water. The two substances are made of the same water molecules, but the water is in two different phases: solid and liquid. A boundary exists where the two phases meet. But as heat from the water transfers into the ice, the ice melts and the boundary moves. Eventually, the ice — and the boundary along with it — disappear.

Intuition might tell us that this melting boundary always remains smooth. After all, you do not cut yourself on sharp edges when you pull a piece of ice from a glass of water. But with a little imagination, it is easy to conceive of scenarios where sharp spots emerge.

Take a piece of ice in the shape of an hourglass and submerge it. As the ice melts, the waist of the hourglass becomes thinner and thinner until the liquid eats all the way through. At the moment this happens, what was once a smooth waist becomes two pointy cusps, or singularities.

“This is one of those problems that naturally exhibits singularities,” said Giuseppe Mingione of the University of Parma. “It’s the physical reality that tells you that.

Yet reality also tells us that the singularities are controlled. We know that cusps should not last long, because the warm water should rapidly melt them down. Perhaps if you started with a huge ice block built entirely out of hourglasses, a snowflake might form. But it still wouldn’t last more than an instant.

In 1889 Stefan subjected the problem to mathematical scrutiny, spelling out two equations that describe melting ice. One describes the diffusion of heat from the warm water into the cool ice, which shrinks the ice while causing the region of water to expand. A second equation tracks the changing interface between ice and water as the melting process proceeds. (In fact, the equations can also describe the situation where the ice is so cold that it causes the surrounding water to freeze — but in the present work, the researchers ignore that possibility.)

“The important thing is to understand where the two phases decide to switch from one to the other,” said Colombo.

It took almost 100 years until, in the 1970s, mathematicians proved that these equations have a solid foundation. Given some starting conditions — a description of the initial temperature of the water and the initial shape of the ice — it’s possible to run the model indefinitely to describe exactly how the temperature (or a closely related quantity called the cumulative temperature) changes with time.

But they found nothing to preclude the model from arriving at scenarios that are improbably weird. The equations might describe an ice-water boundary that forms into a forest of cusps, for example, or a sharp snowflake that stays perfectly still. In other words, they couldn’t rule out the possibility that the model might output nonsense. The Stefan problem became a problem of showing that the singularities in these situations are actually well controlled.

Otherwise, it would mean that the ice melting model was a spectacular failure — one that had fooled generations of mathematicians into believing it was more solid than it is.

Soapy Inspiration

In the decade before mathematicians began to understand the ice melting equations, they made tremendous progress on the mathematics of soap films.

If you dip two wire rings in a soapy solution and then separate them, a soap film forms between them. Surface tension will pull the film as taut as possible, forming it into a shape called a catenoid — a kind of caved-in cylinder. This shape forms because it bridges the two rings with the least amount of surface area, making it an example of what mathematicians call a minimal surface.

Soap films are modeled by their own unique set of equations. By the 1960s, mathematicians had made progress in understanding them, but they didn’t know how weird their solutions could be. Just as in the Stefan problem, the solutions might be unacceptably strange, describing soap films with countless singularities that are nothing like the smooth films we expect.

In 1961 and 1962, Ennio De Giorgi, Wendell Fleming and others invented an elegant process for determining whether the situation with singularities was as bad as feared.

Suppose you have a solution to the soap film equations that describes the shape of the film between two boundary surfaces, like the set of two rings. Focus in on an arbitrary point on the film’s surface. What does the geometry near this point look like? Before we know anything about it, it could have any kind of feature imaginable — anything from a sharp cusp to a smooth hill. Mathematicians devised a method for zooming in on the point, as though they had a microscope with infinite power. They proved that as you zoom in, all you see is a flat plane.

“Always. That’s it,” said Ros-Oton.

This flatness implied that the geometry near that point could not be singular. If the point were located on a cusp, mathematicians would see something more like a wedge, not a plane. And since they chose the point randomly, they could conclude that all points on the film must look like a smooth plane when you peer at them up close. Their work established that the entire film must be smooth — unplagued by singularities.

Mathematicians wanted to use the same methods to deal with the Stefan problem, but they soon realized that with ice, things were not as simple. Unlike soap films, which always look smooth, melting ice really does exhibit singularities. And while a soap film stays put, the line between ice and water is always in motion. This posed an additional challenge that another mathematician would tackle later.

From Films to Ice

In 1977, Luis Caffarelli reinvented a mathematical magnifying glass for the Stefan problem. Rather than zooming in on a soap film, he figured out how to zoom in on the boundary between ice and water.

“This was his great intuition,” said Mingione. “He was able to transport these methods from the minimal surface theory of de Giorgi to this more general setting.”

When mathematicians zoomed in on solutions to the soap film equations, they saw only flatness. But when Caffarelli zoomed in on the frozen boundary between ice and water, he sometimes saw something totally different: frozen spots surrounded almost entirely by warmer water. These points corresponded to icy cusps — singularities — which become stranded by the retreat of the melting boundary.

Caffarelli proved singularities exist in the mathematics of melting ice. He also devised a way of estimating how many there are. At the exact spot of an icy singularity, the temperature is always zero degrees Celsius, because the singularity is made out of ice. That is a simple fact. But remarkably, Caffarelli found that as you move away from the singularity, the temperature increases in a clear pattern: If you move one unit in distance away from a singularity and into the water, the temperature rises by approximately one unit of temperature. If you move two units away, the temperature rises by approximately four.

This is called a parabolic relationship, because if you graph temperature as a function of distance, you get approximately the shape of a parabola. But because space is three-dimensional, you can graph the temperature in three different directions leading away from the singularity, not just one. The temperature therefore looks like a three-dimensional parabola, a shape called a paraboloid.

Altogether, Caffarelli’s insight provided a clear way of sizing up singularities along the ice-water boundary. Singularities are defined as points where the temperature is zero degrees Celsius and paraboloids describe the temperature at and around the singularity. Therefore, anywhere the paraboloid equals zero you have a singularity.

So how many places are there where a paraboloid can equal zero? Imagine a paraboloid composed of a sequence of parabolas stacked side by side. Paraboloids like these can take a minimum value — a value of zero — along an entire line. This means that each of the singularities Caffarelli observed could actually be the size of a line, an infinitely thin icy edge, rather than just a single icy point. And since many lines can be put together to form a surface, his work left open the possibility that a set of singularities could fill the entire boundary surface. If this was true, it would mean that the singularities in the Stefan problem were completely out of control.

“It would be a disaster for the model. Complete chaos,” said Figalli, who won the Fields Medal, math’s highest honor, in 2018.

However, Caffarelli’s result was only a worst-case scenario. It established the maximum size of the potential singularities, but it said nothing about how often singularities actually occur in the equations, or how long they last. By 2019, Figalli, Ros-Oton and Serra had figured out a remarkable way to find out more.

Imperfect Patterns

To solve the Stefan problem, Figalli, Ros-Oton and Serra needed to prove that singularities that crop up in the equations are controlled: There aren’t a lot of them and they don’t last long. To do that, they needed a comprehensive understanding of all the different types of singularities that could possibly form.

Caffarelli had made progress on understanding how singularities develop as ice melts, but there was a feature of the process he didn’t know how to address. He recognized that the water temperature around a singularity follows a paraboloid ­­pattern. He also recognized that it doesn’t quite follow this pattern exactly — there’s a small deviation between a perfect paraboloid and the actual way the water temperature looks.

Figalli, Ros-Oton and Serra shifted the microscope onto this deviation from the paraboloid pattern. When they zoomed in on this small imperfection — a whisper of coolness waving off of the boundary — they discovered that it had its own kinds of patterns which gave rise to different types of singularities.

“They go beyond the parabolic scaling,” said Sandro Salsa of the Polytechnic University of Milan. “Which is amazing.”

They were able to show that all of these new types of singularities disappeared rapidly — just as they do in nature —  except for two that were particularly enigmatic. Their last challenge was to prove that these two types also vanish as soon as they appear, foreclosing the possibility that anything like a snowflake might endure.

Vanishing Cusps

The first type of singularity had come up before, in 2000. A mathematician named Frederick Almgren had investigated it in an intimidating 1,000-page paper about soap films, which was only published by his wife, Jean Taylor — another expert on soap films — after he died.

While mathematicians had shown that soap films are always smooth in three dimensions, Almgren proved that in four dimensions, a new kind of “branching” singularity can appear, making the soap films sharp in strange ways. These singularities are profoundly abstract and impossible to visualize neatly. Yet Figalli, Ros-Oton and Serra realized that very similar singularities form along the melting boundary between ice and water.

“The connection is a bit mysterious,” Serra said. “Sometimes in mathematics, things develop in unexpected ways.”

They used Almgren’s work to show that the ice around one of these branching singularities must have a conical pattern that looks the same as you keep zooming in. And unlike the paraboloid pattern for the temperature, which implies that a singularity might exist along a whole line, a conical pattern can only have a sharp singularity at a single point. Using this fact, they showed that these singularities are isolated in space and time. As soon as they form, they are gone.

The second kind of singularity was even more mysterious. To get a sense of it, imagine submerging a thin sheet of ice into water. It will shrink and shrink and suddenly disappear all at once. But just before that moment, it will form a sheetlike singularity, a two-dimensional wall as sharp as a razor.

At certain points, the researchers managed to zoom in to find an analogous scenario: two fronts of ice collapsing toward the point as if it were situated inside a thin sheet of ice. These points were not exactly singularities, but locations where a singularity was about to form. The question was whether the two fronts near these points collapsed at the same time. If that happened, a sheetlike singularity would form for only one perfect moment before it vanished. In the end, they proved this is in fact how the scenario plays out in the equations.

“This somehow confirms the intuition,” said Daniela De Silva of Barnard College.

Having shown that the exotic branching and sheetlike singularities were both rare, the researchers could make the general statement that all singularities for the Stefan problem are rare.

“If you choose randomly a time, then the probability of seeing a singular point is zero,” Ros-Oton said.

The mathematicians say that the technical details of the work will take time to digest. But they are confident that the results will lay the groundwork for advances on numerous other problems. The Stefan problem is a foundational example for an entire subfield of math where boundaries move. But as for the Stefan problem itself, and the mathematics of how ice cubes melt in water?

“This is closed,” Salsa said.

PlatoAi. Web3 Reimagined. Data Intelligence Amplified.

Click here to access.


Continue Reading
Blockchain1 day ago

People’s payment attitude: Why cash Remains the most Common Means of Payment & How Technology and Crypto have more Advantages as a Means of payment

Fintech4 days ago

PNC cuts nearly 600 apps for BBVA conversion

Automotive4 days ago

This Toyota Mirai 1:10 Scale RC Car Actually Runs On Hydrogen

Automotive2 days ago

7 Secrets That Automakers Wish You Don’t Know

Blockchain2 days ago

What Is the Best Crypto IRA for Me? Use These 6 Pieces of Criteria to Find Out More

Startups1 day ago

The 12 TikTok facts you should know

Gaming2 days ago

New Steam Games You Might Have Missed In August 2021

IOT2 days ago

The Benefits of Using IoT SIM Card Technology

Blockchain2 days ago

The Most Profitable Cryptocurrencies on the Market

Esports4 days ago

New World team share details of upcoming server transfers in Q&A

Gaming2 days ago

How do casinos without an account work?

Energy4 days ago

Segunda Conferência Ministerial de Energia da Rota e Cinturão é realizada em Qingdao

Gaming2 days ago

Norway will crack down on the unlicensed iGaming market with a new gaming law

Blockchain2 days ago

What does swapping crypto mean?

Gaming2 days ago

Norway will crack down on the unlicensed iGaming market with a new gaming law

Supply Chain21 hours ago

LPG tubes – what to think about

Energy4 days ago

People’s Daily Online: uma pesquisa do Instituto de Zoologia de Kumming mostrou um aumento estável da população de pavões verdes, uma espécie ameaçada de extinção

Esports4 days ago

How to play Scream Deathmatch Game Mode in Call of Duty: Black Ops Cold War

AR/VR2 days ago

Preview: Little Cities – Delightful City Building on Quest

AR/VR4 days ago

Build Your Own Spacefolk City on Oculus Quest This Week