Connect with us


Biologists Rethink the Logic Behind Cells’ Molecular Signals



Back in 2000, when Michael Elowitz of the California Institute of Technology was still a grad student at Princeton University, he accomplished a remarkable feat in the young field of synthetic biology: He became one of the first to design and demonstrate a kind of functioning “circuit” in living cells. He and his mentor, Stanislas Leibler, inserted a suite of genes into Escherichia coli bacteria that induced controlled swings in the cells’ production of a fluorescent protein, like an oscillator in electronic circuitry.

It was a brilliant illustration of what the biologist and Nobel laureate François Jacob called the “logic of life”: a tightly controlled flow of information from genes to the traits that cells and other organisms exhibit.

But this lucid vision of circuit-like logic, which worked so elegantly in bacteria, too often fails in more complex cells. “In bacteria, single proteins regulate things,” said Angela DePace, a systems biologist at Harvard Medical School. “But in more complex organisms, you get many proteins involved in a more analog fashion.”

Recently, by looking closely at the protein interactions within one key developmental pathway that shapes the embryos of humans and other complex animals, Elowitz and his co-workers have caught a glimpse of what the logic of complex life is really like. This pathway is a riot of molecular promiscuity that would make a libertine blush, where the component molecules can unite in many different combinations. It might seem futile to hope that this chaotic dance could convey any coherent signal to direct the fate of a cell. Yet this sort of helter-skelter coupling among biomolecules may be the norm, not some weird exception. In fact, it may be why multicellular life works at all.

“Biological cell-cell communication circuits, with their families of promiscuously interacting ligands and receptors, look like a mess and use an architecture that is the opposite of what we synthetic biologists might have designed,” Elowitz said.

Yet this apparent chaos of interacting components is really a sophisticated signal-processing system that can extract information reliably and efficiently from complicated cocktails of signaling molecules. “Understanding cells’ natural combinatorial language could allow us to control [them] with much greater specificity than we have now,” he said.

The emerging picture does more than reconfigure our view of what biomolecules in our cells are up to as they build an organism — what logic they follow to create complex life. It might also help us understand why living things are able to survive at all in the face of an unpredictable environment, and why that randomness permits evolution rather than frustrating it. And it could explain why molecular medicine is often so hard: why many candidate drugs don’t do what we hoped, and how we might make ones that do.

Messengers, Not the Messages

If you were designing a machine or an electronic circuit, it would be folly to model it after a cell. The components of cells are for the most part not carefully arranged and assembled, but are instead just floating and mixing inside the cell membrane like an unruly, jostling crowd. Yet somehow, it works.

The tidy, traditional explanation is that although the protein molecules that make up most of a cell’s working parts are constantly bumping into one another, they treat nearly all of these encounters with indifference. Only when a protein meets another molecule that meshes exactly with an exquisitely sculpted part of its surface do the two lock together and interact. These processes of precise molecular recognition maintain clear lines of communication within cells and keep them running.

The only problem with this story is that it is wrong. Although many proteins do exhibit selective molecular recognition, some of the ones most central to the workings of our eukaryotic cells are far less picky.

Take the growth factor proteins called BMPs, which regulate how cells proliferate and differentiate into various tissues by directing them to turn sets of genes on and off. Their name comes from “bone morphogenetic protein,” because the first-known gene for one was originally thought to encode a protein involved in bone formation.

But although it is indeed involved in that — malfunctions in BMP production are implicated in bone-growth diseases — the idea that bone growth is the function of BMP proteins has long since proved illusory. One type of BMP is involved in the developmental process called gastrulation, which happens around 14 days after fertilization in human embryos, when cells start to specialize into different tissue types and the embryo changes from a clump of cells into a far more complex structure. Later, BMPs are also expressed in cartilage, the kidneys, the eyes and the early brain, and they guide the development of those tissues.

The reality is that the function of BMPs cannot be defined by their effects on the phenotype (that is, on traits). They mediate communications between cells, but what that communication triggers can be totally different in different types of cells, or in the same cell type at a different stage of development. BMPs are messengers, not the messages.

What Elowitz and others are now bringing to light is how BMPs pull off this trick of being so mercurial while also behaving predictably enough for organisms to stake their lives on them. These qualities seem to emerge from the layers upon layers of complexity in the composition of the BMP system, and the flexible, variable affinities of those elements for one another. Paradoxically, the complexity makes the system both more precise and more reliable.

Mammals have genes that encode 11 or more distinct BMP proteins, each with a slightly different structure. BMPs act in bound pairs, or dimers, of the same or different proteins, and in some cases these dimers pair up too, further multiplying the variations. The family of BMP proteins sticks to an associated family of receptor proteins — and those receptors are also made from subunits that fit together in small groups, typically four at a time. It’s this whole cluster of molecules that activates the transcription factors turning genes on and off and triggering a downstream effect on the host cell.

It’s not simply the case, however, that each BMP dimer has designated receptors to which it binds like a lock and key. In fact, these molecules aren’t terribly choosy: Each BMP dimer may stick to several different pairs of receptor subunits with varying degrees of avidity. It’s a combinatorial system, in which the components can be assembled in many ways: less like locks and keys, more like Lego bricks.

The possible permutations are exhausting to contemplate. How can the BMP pathway ever deliver a specific directive to guide a cell’s fate? With so much complexity, “it took a little unconventional thought to approach the problem,” said James Linton, a research scientist in Elowitz’s group.

The Caltech team, along with Yaron Antebi, a former postdoc with Elowitz who is now at the Weizmann Institute of Science in Israel, undertook experimental and computational studies to characterize the binding propensities between 10 major mammalian forms of BMPs and seven receptor subunits in two types of mouse cells. That involved studying a lot of combinations, but an automated robotic system for carrying out the reactions in cell cultures made it possible.

The interactions, although promiscuous, were far from “anything goes.” Certain BMPs had nearly interchangeable effects, but others did not. In some cases, one BMP plus two receptor subunits worked as well as an assembly of three different components. An assembly might work as well with one BMP swapped for another, but only if the receptor stayed the same. Sometimes two swapped components had independent effects, and their combined effect was a simple sum. Sometimes the effects mutually reinforced one another or canceled each other out.

In general, the BMPs could be sorted into groups of equivalents. “We classified two BMPs as equivalent if they have the same pattern of interactions with all other BMPs,” said Elowitz. But those equivalence relationships weren’t fixed — they varied with the cell types and the configuration of receptors that the cells expressed. A pair of BMPs might substitute for each other in one type of cell but not in another. This finding tallied with the observations of other researchers that, for example, the BMP9 protein can substitute for BMP10 in the pathway for blood vessel formation but not in the pathway for heart development.

More Specificity From Fewer Signals

Why does BMP signaling work in a way that seems so unnecessarily complicated? The Caltech team speculates that it might give organisms more for less. Mathematical modeling by members of the group — Christina Su at Caltech, Antebi in Israel and Arvind Murugan at the University of Chicago — showed that a promiscuous system of interactions offers a range of potential advantages over one-to-one molecular interactions.

In particular, in systems where ligands bind uniquely to receptors, the number of types of ligands limits how many different cell types or targets can be uniquely addressed. In a combinatorial system, different pairings between a small number of ligands and receptors can specify a much larger number of targets. The differences between the pairings also permit graded effects rather than an all-or-nothing response.

“Our working hypothesis is that these ligand-receptor combinations have the potential to be more cell-type-specific than individual molecules,” said Elowitz.

A combinatorial system therefore offers more options for addressing cells and can produce more complex cell patterning. This versatility matters for building organisms containing many cell types in precise configurations. Even with a small repertoire of signaling molecules, one group of cells in the embryo can be instructed to become cartilage, say, while another group becomes bone, and others get other fates.

The many possible combinations might create some fuzziness at boundaries between regions, but Linton speculates that these might be sharpened by operating in conjunction with other signaling systems. A pathway involving the family of proteins called Wnt, for example, often seems to operate alongside BMP signaling. “If you find BMP at work somewhere, it’s very likely that you’ll find Wnt,” Linton said. Sometimes the pathways are mutually antagonistic and sometimes they enhance each other. If the Wnt pathway follows similar combinatorial rules — a possibility that still needs to be explored experimentally, Elowitz stresses — then BMP and Wnt might help to refine each other’s signaling.

Elowitz and his colleagues think that in this way, these kinds of combinatorial rules could represent a widespread “design principle” of the molecular wiring of cells.

The systems biologist Galit Lahav of Harvard Medical School agrees that such a system makes a lot of sense. She wonders if something similar might apply to the gene p53, which is central to controlling cells’ cycles of replication and division and is often implicated in cancers. The p53 protein plays several different roles in cell signaling, and it binds to many other molecules.

The combinatorial principle might also extend to situations beyond cell growth and development. Linton sees a loose parallel with what seems to happen in the olfactory system: Humans have around 400 types of receptor proteins lining the membranes of the olfactory bulb in the nose, and these receptors can collectively discriminate vast numbers of odors. That wouldn’t be possible if each odorant molecule had to be uniquely recognized by its own dedicated receptor. Instead, the receptors seem to bind promiscuously to odorants with different affinities, and the output signal sent to the brain’s smell center is then determined by combinatorial rules.

Using Noise to Their Advantage

The evidence that interactions of proteins, RNA molecules and DNA genomic sequences involved in cell regulation are flexible and promiscuous has become ever more prevalent in the past decade or so. They turn up in a wide range of systems throughout biology. “Given that promiscuity did not have to exist, but is ubiquitous, the simplest and most reasonable assumption is that it is providing some functional capability,” Elowitz said.

He thinks that capability is, at root, information processing. “Just as neurons wired together through axons and dendrites can perform complex information processing, so too can proteins wired together through biochemical interactions,” he said. It’s an insight that other scientists have also drawn from their studies of biochemical networks.

Heidi Klumpe, a member of Elowitz’s group who conducted much of the experimental work on the BMP system, compares it to the way neural networks work: not by assigning fixed roles to given components of the network, but by letting the roles emerge from many connections. “We think the cells are doing a more complex computation than previously thought,” she said.

“What we are trying to do now is figure out precisely what kinds of functions these systems actually compute,” Elowitz said, “and what higher-level capabilities these computations then enable.”

The evolutionary biologist Andreas Wagner of the University of Zurich agrees that the idea that a promiscuous system like this has been selected because it confers some advantage is “right on the mark.” That this benefit may lie in its versatility is “an intriguing possibility that has probably crossed the mind of anybody who seriously thought about this problem,” he said.

But he adds that “there is another, more mundane possibility”: Perhaps this is the only way a complicated system like the cells of multicellular organisms can work at all. “Cellular systems are highly noisy,” Wagner said; molecular encounters in the crowded, jostling environment inside cells are unpredictable, and the amounts of proteins produced from moment to moment fluctuate randomly. A cell in which each component is wired specifically to another would be highly vulnerable to those uncontrollable variations. It would behave as though circuit elements kept dropping randomly in and out of the network.

Moreover, every time a cell divides, there’s no guarantee that circuits will get exactly reproduced because of random copying errors in DNA replication. “A system like that might be exquisitely sensitive to mutations that alter its properties,” Wagner said. “Taken together, all these costs might well be prohibitive.”

Consequently, cells may have evolved adaptations that use noise to their advantage, and Elowitz’s model of the combinatorial logic of regulatory networks “may be one example of such adaptation,” Wagner said. “Cells may have sloppy systems whose power emerges from the right kind of combinatorics.”

“Biological systems are generally much more robust than we imagine,” said Meng Zhu, a developmental biologist at Harvard Medical School. Researchers often find that when they experimentally disable a gene that appears critical to survival, the organism barely seems to notice: It readjusts the interactions and pathways in its gene and protein networks to compensate. The redundancy and the compensatory function of related proteins, as seen in the BMP system, might be a key part of that ability, she says.

Zhu thinks that promiscuous, highly interconnected protein networks might also promote the ability of organisms to acquire useful new capacities through evolution. “A system that has higher connectivity tends to evolve new functions more easily,” she said, because it can better tolerate deleterious mutations in its component parts.

Conversely, if all the interactions between the molecular components are very finely tuned, “it’s very hard to do something new,” said Ard Louis, a physicist who works on problems of biological complexity at the University of Oxford. Any change in those components, even one that seems advantageous, is likely to disrupt some existing, possibly vital function.

Promiscuous binding that allows one protein to substitute for another might therefore enable the network to acquire new functions without losing the old ones. Wagner, working with Joshua Payne at the Swiss Federal Institute of Technology Zurich, has found support for this idea: They have shown that the promiscuous binding of transcription factors can promote both robustness to mutations and the ability to evolve new functions.

So it could be that a combinatorial system of ligand binding both creates more options for cells and gives organisms more evolvability and robustness against noise. Evolution may have organized much of the cell’s biochemistry to be far less sensitive to the details than researchers thought.

“I think noisy, evolved biological systems are full of details, but a lot of them are irrelevant,” Klumpe said. “Moreover, it may not be a specific detail that matters, but rather the conservation of some higher-level function” — such as the requirement that transcription factors bind with some level of strength to turn on gene expression.

Circuitry Is Too Simple

This kind of “sloppiness” in biomolecular networks may have important consequences for drug development. “One of the challenges in ordinary medicine is that drugs can be very specific for a target protein, but that target protein may be nonspecific in terms of the cell types in which it is expressed,” Elowitz said. You might be able to hit a protein target very accurately but still not know what effect that will have in different tissues — if any. The work of Elowitz’s team suggests that drugs may need to be more than single-molecule “magic bullets”: They might have to hit different combinations of tissue-specific targets to induce the desired response.

Whatever the reason for its combinatorial principles, the BMP signaling system shows that cells are not like the machines we humans make. “And it might be that that’s true for many biological systems,” Linton said. “If you make simple analogies to electronics, you’re going to come up short.”

This makes it challenging not just to talk about biological systems but to understand and engineer them. Electronic analogies might be appropriate for relatively simple systems such as the bacteria that Elowitz and Leibler worked on 20 years ago, but when living organisms get more complicated — and in particular when they become multicellular, with genetically identical cells that work together in diverse, specialized states — different rules may apply.

The operating principle exemplified by the BMP system might be “something that emerged in nature as a way to give rise to multicellularity and more complex tissues,” Linton said. It’s even possible, he suggests, that “this was the innovation that allowed organisms such as us to emerge.”

Perhaps, then, the most useful analogies for how cells work are themselves biological, such as olfaction or cognition. Maybe the only way to truly understand life is with reference to itself.

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
Automotive4 days ago

Evans and TOYOTA GAZOO Racing Seal Second in Spain

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

Automotive1 day ago

7 Secrets That Automakers Wish You Don’t Know

Blockchain1 day ago

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

Blockchain9 hours 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

Cyber Security4 days ago

Spotify Web Player

Aviation5 days ago

Vaccine passports for overseas travel to be rolled out this week

IOT1 day ago

The Benefits of Using IoT SIM Card Technology

Gaming1 day ago

New Steam Games You Might Have Missed In August 2021

Blockchain1 day ago

The Most Profitable Cryptocurrencies on the Market

Esports4 days ago

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

Gaming1 day ago

How do casinos without an account work?

Esports5 days ago

New World Animal Instincts Quest Details

Startups9 hours ago

The 12 TikTok facts you should know

Esports4 days ago

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

Energy4 days ago

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

Blockchain1 day ago

What does swapping crypto mean?

Payments4 days ago

Everyone is building a wallet

Gaming1 day ago

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