Connect with us

Quantum

The Journey to Define Dimension

Published

on

The notion of dimension at first seems intuitive. Glancing out the window we might see a crow sitting atop a cramped flagpole experiencing zero dimensions, a robin on a telephone wire constrained to one, a pigeon on the ground free to move in two and an eagle in the air enjoying three.

But as we’ll see, finding an explicit definition for the concept of dimension and pushing its boundaries has proved exceptionally difficult for mathematicians. It’s taken hundreds of years of thought experiments and imaginative comparisons to arrive at our current rigorous understanding of the concept.

The ancients knew that we live in three dimensions. Aristotle wrote, “Of magnitude that which (extends) one way is a line, that which (extends) two ways is a plane, and that which (extends) three ways a body. And there is no magnitude besides these, because the dimensions are all that there are.”

Yet mathematicians, among others, have enjoyed the mental exercise of imagining more dimensions. What would a fourth dimension — somehow perpendicular to our three — look like?

One popular approach: Suppose our knowable universe is a two-dimensional plane in three-dimensional space. A solid ball hovering above the plane is invisible to us. But if it falls and contacts the plane, a dot appears. As it continues through the plane, a circular disk grows until it reaches its maximum size. It then shrinks and disappears. It is through these cross sections that we see three dimensional shapes.

Similarly, in our familiar three-dimensional universe, if a four-dimensional ball were to pass through it would appear as a point, grow into a solid ball, eventually reach its full radius, then shrink and disappear. This gives us a sense of the four-dimensional shape, but there are other ways of thinking about such figures.

For example, let’s try visualizing the four-dimensional equivalent of a cube, known as a tesseract, by building up to it. If we begin with a point, we can sweep it in one direction to obtain a line segment. When we sweep the segment in a perpendicular direction, we obtain a square. Dragging this square in a third perpendicular direction yields a cube. Likewise, we obtain a tesseract by sweeping the cube in a fourth direction.

Alternatively, just as we can unfold the faces of a cube into six squares, we can unfold the three-dimensional boundary of a tesseract to obtain eight cubes, as Salvador Dalí showcased in his 1954 painting Crucifixion (Corpus Hypercubus).

This all adds up to an intuitive understanding that an abstract space is n-dimensional if there are n degrees of freedom within it (as those birds had), or if it requires n coordinates to describe the location of a point. Yet, as we shall see, mathematicians discovered that dimension is more complex than these simplistic descriptions imply.

The formal study of higher dimensions emerged in the 19th century and became quite sophisticated within decades: A 1911 bibliography contained 1,832 references to the geometry of n dimensions. Perhaps as a consequence, in the late 19th and early 20th centuries, the public became infatuated with the fourth dimension. In 1884, Edwin Abbott wrote the popular satirical novel Flatland, which used two-dimensional beings encountering a character from the third dimension as an analogy to help readers comprehend the fourth dimension. A 1909 Scientific American essay contest entitled “What Is the Fourth Dimension?” received 245 submissions vying for a $500 prize. And many artists, like Pablo Picasso and Marcel Duchamp, incorporated ideas of the fourth dimension into their work.

But during this time, mathematicians realized that the lack of a formal definition for dimension was actually a problem.

Georg Cantor is best known for his discovery that infinity comes in different sizes, or cardinalities. At first Cantor believed that the set of dots in a line segment, a square and a cube must have different cardinalities, just as a line of 10 dots, a 10 × 10 grid of dots and a 10 × 10 × 10 cube of dots have different numbers of dots. However, in 1877 he discovered a one-to-one correspondence between points in a line segment and points in a square (and likewise cubes of all dimensions), showing that they have the same cardinality. Intuitively, he proved that lines, squares and cubes all have the same number of infinitesimally small points, despite their different dimensions. Cantor wrote to Richard Dedekind, “I see it, but I do not believe it.”

Cantor realized this discovery threatened the intuitive idea that n-dimensional space requires n coordinates, because each point in an n-dimensional cube can be uniquely identified by one number from an interval, so that, in a sense, these high-dimensional cubes are equivalent to a one-dimensional line segment. However, as Dedekind pointed out, Cantor’s function was highly discontinuous — it essentially broke apart a line segment into infinitely many parts and reassembled them to form a cube. This is not the behavior we would want for a coordinate system; it would be too disordered to be helpful, like giving buildings in Manhattan unique addresses but assigning them at random.

Then, in 1890, Giuseppe Peano discovered that it is possible to wrap a one-dimensional curve so tightly — and continuously — that it fills every point in a two-dimensional square. This was the first space-filling curve. But Peano’s example was also not a good basis for a coordinate system because the curve intersected itself infinitely many times; returning to the Manhattan analogy, it was like giving some buildings multiple addresses.

These and other surprising examples made it clear that mathematicians needed to prove that dimension is a real notion and that, for instance, n- and m-dimension Euclidean spaces are different in some fundamental way when n ≠ m. This objective became known as the “invariance of dimension” problem.

Finally, in 1912, almost half a century after Cantor’s discovery, and after many failed attempts to prove the invariance of dimension, L.E.J. Brouwer succeeded by employing some methods of his own creation. In essence, he proved that it is impossible to put a higher-dimensional object inside one of smaller dimension, or to place one of smaller dimension into one of larger dimension and fill the entire space, without breaking the object into many pieces, as Cantor did, or allowing it to intersect itself, as Peano did. Moreover, around this time Brouwer and others gave a variety of rigorous definitions, which, for example, could assign dimension inductively based on the fact that the boundaries of balls in n-dimensional space are (n − 1)-dimensional.

Although Brouwer’s work put the notion of dimension on strong mathematical footing, it did not help with our intuition regarding higher-dimensional spaces: Our familiarity with three-dimensional space too easily leads us astray. As Thomas Banchoff wrote, “All of us are slaves to the prejudices of our own dimension.”

Suppose, for instance, we place 2n spheres of radius 1 inside an n-dimensional cube with side length 4, and then put another one in the center tangent to them all. As n grows, so does the size of the central sphere — it has a radius of $latex sqrt{n}$ − 1. Thus, shockingly, when n ≥ 10 this sphere protrudes beyond the sides of the cube.

The surprising realities of high-dimensional space cause problems in statistics and data analysis, known collectively as the “curse of dimensionality.” The number of sample points required for many statistical techniques goes up exponentially with the dimension. Also, as dimensions increase, points will cluster together less often. Thus, it’s often important to find ways to reduce the dimension of high-dimensional data.

The story of dimension didn’t end with Brouwer. Just a few years afterward, Felix Hausdorff developed a definition of dimension that — generations later — proved essential for modern math. An intuitive way to think about Hausdorff dimension is that if we scale, or magnify, a d-dimensional object uniformly by a factor of k, the size of the object increases by a factor of kd. Suppose we scale a point, a line segment, a square and a cube by a factor of 3. The point does not change size (30 = 1), the segment becomes three times as large (31 = 3), the square becomes nine times as large (32 = 9) and the cube becomes 27 times as large (33 = 27).

One surprising consequence of Hausdorff’s definition is that objects could have non-integer dimensions. Decades later, this turned out to be just what Benoit B. Mandelbrot needed when he asked, “How long is the coast of Britain?” A coastline can be so jagged that it cannot be measured precisely with any ruler — the shorter the ruler, the larger and more precise the measurement. Mandelbrot argued that the Hausdorff dimension provides a way to quantify this jaggedness, and in 1975 he coined the term “fractal” to describe such infinitely complex shapes.

To understand what a non-integer dimension might look like, let’s consider the Koch curve, which is produced iteratively. We begin with a line segment. At each stage we remove the middle third of each segment and replace it with two segments equal in length to the removed segment. Repeat this procedure indefinitely to obtain the Koch curve. Study it closely, and you’ll see it contains four sections that are identical to the whole curve but are one-third the size. So if we scale this curve by a factor of 3, we obtain four copies of the original. This means its Hausdorff dimension, d, satisfies 3d = 4. So, d = log3(4) ≈ 1.26. The curve isn’t entirely space-filling, like Peano’s, so it isn’t quite two-dimensional, but it is more than a single one-dimensional line.

Lastly, some readers may be thinking, “Isn’t time the fourth dimension?” Indeed, as the inventor said in H.G. Wells’ 1895 novel The Time Machine, “There is no difference between Time and any of the three dimensions of Space except that our consciousness moves along it.” Time as the fourth dimension exploded in the public imagination in 1919, when a solar eclipse allowed scientists to confirm Albert Einstein’s general theory of relativity and the curvature of Hermann Minkowski’s flat four-dimensional space-time. As Minkowski foretold in a 1908 lecture, “Henceforth space by itself, and time by itself, are doomed to fade away into mere shadows, and only a kind of union of the two will preserve independent reality.”

Today, mathematicians and others routinely stray outside our comfortable three dimensions. Sometimes this work involves additional physical dimensions, such as those required by string theory, but more often we work abstractly and do not envision actual space. Some investigations are geometric, such as Maryna Viazovska’s 2016 discovery of the most efficient ways of packing spheres in dimensions eight and 24. Sometimes they require non-integer dimensions when fractals are studied in diverse fields such as physics, biology, engineering, finance and image processing. And in this era of “big data,” scientists, governments and corporations build high-dimensional profiles of people, places and things.

Luckily, dimensions don’t need to be fully understood to be enjoyed, by bird and mathematician alike.

PlatoAi. Web3 Reimagined. Data Intelligence Amplified.

Click here to access.

Source: https://www.quantamagazine.org/a-mathematicians-guided-tour-through-high-dimensions-20210913/

Quantum

Trapping Sets of Quantum LDPC Codes

Published

on


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.

Abstract

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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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:/​/​arxiv.org/​abs/​2012.04068.
arXiv: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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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:/​/​web.stanford.edu/​class/​ee388/​papers/​ErrorFloors.pdf.
https:/​/​web.stanford.edu/​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:/​/​arxiv.org/​abs/​1904.02703.
arXiv: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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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:/​/​arxiv.org/​abs/​quant-ph/​9705052.
https:/​/​doi.org/​10.7907/​rzr7-dt72
arXiv:quant-ph/9705052

[27] M. M. Wilde. Logical operators of quantum codes. Phys. Rev. A, 79: 062322, Jun. 2009. 10.1103/​PhysRevA.79.062322.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.

Source: https://quantum-journal.org/papers/q-2021-10-14-562/

Continue Reading

Quantum

Entangled symmetric states and copositive matrices

Published

on


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.

Abstract

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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​10.1145/​780542.780545

[4] Asher Peres. Separability criterion for density matrices. Physical Review Letters, 77 (8): 1413, 1996. 10.1103/​PhysRevLett.77.1413.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.

Source: https://quantum-journal.org/papers/q-2021-10-07-561/

Continue Reading

Quantum

The Quantum Supremacy Tsirelson Inequality

Published

on

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.

Abstract

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:/​/​simons.berkeley.edu/​talks/​tbd-124.
https:/​/​simons.berkeley.edu/​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:/​/​drops.dagstuhl.de/​opus/​volltexte/​2017/​7527.
https:/​/​doi.org/​10.4230/​LIPIcs.CCC.2017.22
http:/​/​drops.dagstuhl.de/​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:/​/​www.theoryofcomputing.org/​articles/​v016a011.
https:/​/​doi.org/​10.4086/​toc.2020.v016a011
http:/​/​www.theoryofcomputing.org/​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:/​/​drops.dagstuhl.de/​opus/​volltexte/​2020/​12559.
https:/​/​doi.org/​10.4230/​LIPIcs.CCC.2020.7
https:/​/​drops.dagstuhl.de/​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:/​/​doi.org/​10.1145/​276698.276708.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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:/​/​doi.org/​10.1109/​CCC.2011.24.
https:/​/​doi.org/​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:/​/​doi.org/​10.1109/​FOCS.2014.57.
https:/​/​doi.org/​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:/​/​drops.dagstuhl.de/​opus/​volltexte/​2020/​12069.
https:/​/​doi.org/​10.4230/​LIPIcs.TQC.2020.10
https:/​/​drops.dagstuhl.de/​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:/​/​doi.org/​10.1038/​s41586-019-1666-5.
https:/​/​doi.org/​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:/​/​doi.org/​10.1145/​502090.502097.
https:/​/​doi.org/​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:/​/​link.aps.org/​doi/​10.1103/​PhysicsPhysiqueFizika.1.195.
https:/​/​doi.org/​10.1103/​PhysicsPhysiqueFizika.1.195

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

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

[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:/​/​doi.org/​10.1007/​s00220-016-2706-8.
https:/​/​doi.org/​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:/​/​doi.org/​10.1145/​261342.261346.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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:/​/​doi.org/​10.1016/​j.ic.2014.12.003.
https:/​/​doi.org/​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:/​/​doi.org/​10.1007/​BF00417500.
https:/​/​doi.org/​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:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.23.880.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
arXiv:1809.06957

[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:/​/​doi.org/​10.1038/​s41534-017-0013-7.
https:/​/​doi.org/​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:/​/​drops.dagstuhl.de/​opus/​volltexte/​2021/​13552.
https:/​/​doi.org/​10.4230/​LIPIcs.ITCS.2021.13
https:/​/​drops.dagstuhl.de/​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:/​/​doi.org/​10.1109/​FOCS.2011.75.
https:/​/​doi.org/​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:/​/​drops.dagstuhl.de/​opus/​volltexte/​2020/​11744.
https:/​/​doi.org/​10.4230/​LIPIcs.ITCS.2020.59
https:/​/​drops.dagstuhl.de/​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:/​/​doi.org/​10.1145/​1250790.1250874.
https:/​/​doi.org/​10.1145/​1250790.1250874

[29] Ryan O’Donnell. Analysis of Boolean Functions. Cambridge University Press, USA, 2014. ISBN 1107038324. 10.1017/​CBO9781139814782.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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.
https:/​/​doi.org/​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:/​/​doi.org/​10.1007/​BF02127580.
https:/​/​doi.org/​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.

Source: https://quantum-journal.org/papers/q-2021-10-07-560/

Continue Reading

Quantum

Mathematicians Prove Melting Ice Stays Smooth

Published

on

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.

Source: https://www.quantamagazine.org/mathematicians-prove-melting-ice-stays-smooth-20211006/

Continue Reading
Esports5 days ago

The best teams in Hearthstone Mercenaries

Fintech3 days ago

PNC cuts nearly 600 apps for BBVA conversion

Aviation4 days ago

Vaccine passports for overseas travel to be rolled out this week

Esports2 days ago

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

Esports5 days ago

How Many Chapters are in the Demon Slayer Game?

Cyber Security3 days ago

Spotify Web Player

AI4 days ago

When to Contact an Attorney After a Car Accident

Payments3 days ago

Everyone is building a wallet

Esports3 days ago

How TFT Set 6 Hextech Augments work: full list and updates

Automotive3 days ago

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

AI5 days ago

5 Ways to Attract Clients with Law Firm SEO

Esports5 days ago

Demon Slayer: Kimetsu no Yaiba – The Hinokami Chronicles Character Tier List

Esports4 days ago

The 10 Legends of Runeterra characters most likely to turn into League champions

Blockchain6 hours ago

The Most Profitable Cryptocurrencies on the Market

Low_Car33ElfynEvansScott-Martin.jpg
Automotive3 days ago

Evans and TOYOTA GAZOO Racing Seal Second in Spain

Cleantech4 days ago

US & Denmark Unveil Big Plans For Wind Power

Supply Chain4 days ago

Top 10 hydraulic cylinder manufacturers in China

Esports3 days ago

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

Energy2 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

Esports5 days ago

Only 6,900 pick’ems remain perfect after group B’s second round-robin at the 2021 World Championship

Trending