Connect with us


Exact and approximate continuous-variable gate decompositions




Timjan Kalajdzievski and Nicolás Quesada

Xanadu, Toronto, ON, M5G 2C8, Canada

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


We gather and examine in detail gate decomposition techniques for continuous-variable quantum computers and also introduce some new techniques which expand on these methods. Both exact and approximate decomposition methods are studied and gate counts are compared for some common operations. While each having distinct advantages, we find that exact decompositions have lower gate counts whereas approximate techniques can cover decompositions for all continuous-variable operations but require significant circuit depth for a modest precision.

► BibTeX data

► References

[1] Hoi-Kwan Lau, Raphael Pooser, George Siopsis, and Christian Weedbrook. Quantum machine learning over infinite dimensions. Phys. Rev. Lett, 118: 080501, 2017. 10.1103/​PhysRevLett.118.080501.

[2] Timjan Kalajdzievski, Christian Weedbrook, and Patrick Rebentrost. Continuous-variable gate decomposition for the Bose-Hubbard model. Phys. Rev. A, 97 (6): 062311, 2018. 10.1103/​PhysRevA.97.062311.

[3] Juan Miguel Arrazola, Timjan Kalajdzievski, Christian Weedbrook, and Seth Lloyd. Quantum algorithm for non-homogeneous linear partial differential equations. Phys. Rev. A, 100: 032306, 201908. 10.1103/​PhysRevA.100.032306.

[4] Seckin Sefi, Vishal Vaibhav, and Peter van Loock. A measurement-induced optical kerr interaction. Phys. Rev. A, 88: 012303, 2013. 10.1103/​PhysRevA.88.012303.

[5] Christopher M. Dawson and Michael A. Nielsen. The Solovay-Kitaev algorithm. Quantum Inf. Comput., 6: 1, 2006. 10.5555/​2011679.2011685.

[6] Matthew Amy, Dmitri Maslov, Michele Mosca, and Martin Roetteler. A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 32 (6): 818–830, 2013. 10.1109/​TCAD.2013.2244643.

[7] Seth Lloyd. Almost any quantum logic gate is universal. Phys. Rev. Lett., 75 (2): 346, 1995. 10.1103/​PhysRevLett.75.346.

[8] David P DiVincenzo. Two-bit gates are universal for quantum computation. Phys. Rev. A, 51 (2): 1015, 1995. 10.1103/​PhysRevA.51.1015.

[9] Adriano Barenco, Charles H Bennett, Richard Cleve, David P DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Phys. Rev. A, 52 (5): 3457, 1995. 10.1103/​PhysRevA.52.3457.

[10] Seth Lloyd. Universal quantum simulators. Science, 23: 1073, 1996. 10.1126/​science.273.5278.1073.

[11] Seth Lloyd and Samuel L. Braunstein. Quantum computation over continuous variables. Phys. Rev. Lett, 82: 1784, 1999. 10.1103/​PhysRevLett.82.1784.

[12] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Phys. Rev. A, 71 (2): 022316, 2005. 10.1103/​PhysRevA.71.022316.

[13] Seckin Sefi and Peter van Loock. How to decompose arbitrary continuous-variable quantum operations. Phys. Rev. Lett., 107: 170501, 2011. 10.1103/​PhysRevLett.107.170501.

[14] Timjan Kalajdzievski and Juan Miguel Arrazola. Exact gate decompositions for photonic quantum computing. Phys. Rev. A, 99: 022341, 2019. 10.1103/​PhysRevA.99.022341.

[15] A Yu Kitaev. Quantum computations: algorithms and error correction. Russ. Math. Surv., 52 (6): 1191–1249, 1997. 10.1070/​RM1997v052n06ABEH002155.

[16] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits. Phys. Rev. Lett., 110 (19): 190502, 2013. 10.1103/​PhysRevLett.110.190502.

[17] Vadym Kliuchnikov, Alex Bocharov, and Krysta M Svore. Asymptotically optimal topological quantum compiling. Phys. Rev. Lett., 112 (14): 140504, 2014. 10.1103/​PhysRevLett.112.140504.

[18] Vadym Kliuchnikov and Jon Yard. A framework for exact synthesis. arXiv:1504.04350, 2015.

[19] Alex Bocharov, Martin Roetteler, and Krysta M Svore. Efficient synthesis of universal repeat-until-success quantum circuits. Phys. Rev. Lett., 114 (8): 080502, 2015. 10.1103/​PhysRevLett.114.080502.

[20] Nicolas C. Menicucci, Peter van Loock, Mile Gu, Christian Weedbrook, Timothy C. Ralph, and Michael A. Nielsen. niversal quantum computation with continuous-variable cluster states. Phys. Rev. Lett, 97: 110501, 2006. 10.1103/​PhysRevLett.97.110501.

[21] Mile Gu, Christian Weedbrook, Nicolas C. Menicucci, Timothy C. Ralph, and Peter van Loock. Quantum computing with continuous-variable clusters. Phys. Rev. A, 79: 062318, 2009a. 10.1103/​PhysRevA.79.062318.

[22] Christian Weedbrook, Stefano Pirandola, Raúl García-Patrón, Nicolas J. Cerf, Timothy C. Ralph, Jeffrey H. Shapiro, and Seth Lloyd. Gaussian quantum information. Rev. Mod. Phys., 84: 621, 2012. 10.1103/​RevModPhys.84.621.

[23] Tomasz Sowinski, Omjyoti Dutta, Philipp Hauke, Luca Tagliacozzo, and Maciej Lewenstein. Dipolar molecules in optical lattices. Phys. Rev. Lett., 108: 115301, 2012. 10.1103/​PhysRevLett.108.115301.

[24] CR Myers and TC Ralph. Coherent state topological cluster state production. New J. Phys., 13 (11): 115015, 2011. 10.1088/​1367-2630/​13/​11/​115015.

[25] Timothy C Ralph, Alexei Gilchrist, Gerard J Milburn, William J Munro, and Scott Glancy. Quantum computation with optical coherent states. Phys. Rev. A, 68 (4): 042319, 2003. 10.1103/​PhysRevA.68.042319.

[26] Giacomo Pantaleoni, Ben Q Baragiola, and Nicolas C Menicucci. Modular bosonic subsystem codes. Phys. Rev. Lett., 125 (4): 040501, 2020. 10.1103/​PhysRevLett.125.040501.

[27] Daniel Gottesman, Alexei Kitaev, and John Preskill. Encoding a qubit in an oscillator. Phys. Rev. A, 64 (1): 012310, 2001. 10.1103/​PhysRevA.64.012310.

[28] Naomichi Hatano and Masuo Suzuki. Finding exponential product formulas of higher orders. In A. Das and B.K. Chakrabarti, editors, Quantum Annealing and Other Optimization Methods, pages 37–68. Springer, Berlin, 2005. 10.1007/​11526216_2.

[29] Nathan Wiebe, Dominic W. Berry, Peter Hoyer, and Barry C. Sanders. Higher order decompositions of ordered operator exponentials. J. Phys. A: Math. Theor., 43: 065203, 2010. 10.1088/​1751-8113/​43/​6/​065203.

[30] Samuel L Braunstein. Squeezing as an irreducible resource. Phys. Rev. A, 71 (5): 055801, 2005. 10.1103/​PhysRevA.71.055801.

[31] Biswadeb Dutta, N Mukunda, R Simon, et al. The real symplectic groups in quantum mechanics and optics. Pramana, 45 (6): 471–497, 1995. 10.1007/​BF02848172.

[32] Timjan Kalajdzievski. Exact Gate Decompositions For Photonic Quantum Computers. PhD thesis, York University, 2020. URL https:/​/​​xmlui/​handle/​10315/​37435.

[33] Ryotatsu Yanagimoto, Tatsuhiro Onodera, Edwin Ng, Logan G. Wright, Peter L. McMahon, and Hideo Mabuchi. Engineering a Kerr-based deterministic cubic phase gate via gaussian operation. Phys. Rev. Lett., 124: 240503, 2020. 10.1103/​PhysRevLett.124.240503.

[34] Mitsuyoshi Yukawa, Kazunori Miyata, Hidehiro Yonezawa, Petr Marek, Radim Filip, and Akira Furusawa. Emulating quantum cubic nonlinearity. Phys. Rev. A, 88 (5): 053816, 2013. 10.1103/​PhysRevA.88.053816.

[35] Mile Gu, Christian Weedbrook, Nicolas C Menicucci, Timothy C Ralph, and Peter van Loock. Quantum computing with continuous-variable clusters. Phys. Rev. A, 79 (6): 062318, 2009b. 10.1103/​PhysRevA.79.062318.

[36] Kevin Marshall, Raphael Pooser, George Siopsis, and Christian Weedbrook. Repeat-until-success cubic phase gate for universal continuous-variable quantum computation. Phys. Rev. A, 91 (3): 032321, 2015. 10.1103/​PhysRevA.91.032321.

[37] Krishna Kumar Sabapathy and Christian Weedbrook. ON states as resource units for universal quantum computation with photonic architectures. Phys. Rev. A, 97 (6): 062315, 2018. 10.1103/​PhysRevA.97.062315.

[38] Krishna Kumar Sabapathy, Haoyu Qi, Josh Izaac, and Christian Weedbrook. Production of photonic universal quantum gates enhanced by machine learning. Phys. Rev. A, 100 (1): 012326, 2019. 10.1103/​PhysRevA.100.012326.

[39] Petr Marek, Radim Filip, Hisashi Ogawa, Atsushi Sakaguchi, Shuntaro Takeda, Jun ichi Yoshikawa, and Akira Furusawa. General implementation of arbitrary nonlinear quadrature phase gates. Phys. Rev. A, 97: 022329, 2018. 10.1103/​PhysRevA.97.022329.

[40] Timo Hillmann, Fernando Quijandría, Göran Johansson, Alessandro Ferraro, Simone Gasparinetti, and Giulia Ferrini. Universal gate set for continuous-variable quantum computation with microwave circuits. Phys. Rev. Lett., 125 (16): 160501, 2020. 10.1103/​PhysRevLett.125.160501.

[41] Yaakov S. Weinstein, Seth Lloyd, and David G. Cory. Implementation of the quantum Fourier transform. Phys. Rev. Lett., 86: 1889, 2001. 10.1103/​PhysRevLett.86.1889.

[42] Manas K. Patra and Samuel L. Braunstein. Quantum Fourier transform, heisenberg groups and quasiprobability distributions. New J. Phys., 13: 063013, 2011. 10.1088/​1367-2630/​13/​6/​063013.

[43] Wilhelm Magnus. On the exponential solution of differential equations for a linear operator. Commun. Pure Appl. Math., 7 (4): 649–673, 1954. 10.1002/​cpa.3160070404.

[44] Hale F Trotter. On the product of semi-groups of operators. Proc. Am. Math. Soc., 10 (4): 545–551, 1959. 10.2307/​2033649.

[45] Masuo Suzuki. Generalized Trotter’s formula and systematic approximants of exponential operators and inner derivations with applications to many-body problems. Commun. Math. Phys., 51: 183, 1976. 10.1007/​BF01609348.

[46] Andrew M Childs, Dmitri Maslov, Yunseong Nam, Neil J Ross, and Yuan Su. Toward the first quantum simulation with quantum speedup. Proc. Natl. Acad. Sci. U.S.A., 115: 9456–9461, 2018. 10.1073/​pnas.1801723115.

[47] Stephen Barnett and Paul M Radmore. Methods in theoretical quantum optics, volume 15. Oxford University Press, 2002.

[48] Michael Reck, Anton Zeilinger, Herbert J Bernstein, and Philip Bertani. Experimental realization of any discrete unitary operator. Phys. Rev. Lett., 73 (1): 58, 1994. 10.1103/​PhysRevLett.73.58.

[49] William R Clements, Peter C Humphreys, Benjamin J Metcalf, W Steven Kolthammer, and Ian A Walmsley. Optimal design for universal multiport interferometers. Optica, 3 (12): 1460–1465, 2016. 10.1364/​OPTICA.3.001460.

[50] Hubert de Guise, Olivia Di Matteo, and Luis L Sánchez-Soto. Simple factorization of unitary transformations. Phys. Rev. A, 97 (2): 022328, 2018. 10.1103/​PhysRevA.97.022328.

[51] Daiqin Su, Ish Dhand, Lukas G Helt, Zachary Vernon, and Kamil Brádler. Hybrid spatiotemporal architectures for universal linear optics. Phys. Rev. A, 99 (6): 062301, 2019. 10.1103/​PhysRevA.99.062301.

[52] Alessio Serafini. Quantum continuous variables: a primer of theoretical methods. CRC press, 2017.

[53] Jaromír Fiurášek. Unitary-gate synthesis for continuous-variable systems. Phys. Rev. A, 68 (2): 022304, 2003. 10.1103/​PhysRevA.68.022304.

[54] Chris Sparrow, Enrique Martín-López, Nicola Maraviglia, Alex Neville, Christopher Harrold, Jacques Carolan, Yogesh N Joglekar, Toshikazu Hashimoto, Nobuyuki Matsuda, Jeremy L O’Brien, et al. Simulating the vibrational quantum dynamics of molecules using photonics. Nature, 557 (7707): 660, 2018. 10.1038/​s41586-018-0152-9.

[55] Patrick Rebentrost, Brajesh Gupt, and Thomas R. Bromley. Photonic quantum algorithm for Monte Carlo integration. arXiv:1809.02579, 2018.

[56] Raymond Kan. From moments of sum to moments of product. J. Multivar. Anal., 99: 542, 2008. 10.1016/​j.jmva.2007.01.013.

[57] Nathan Killoran, Josh Izaac, Nicolás Quesada, Ville Bergholm, Matthew Amy, and Christian Weedbrook. Strawberry fields: A software platform for photonic quantum computing. Quantum, 3: 129, 2019. 10.22331/​q-2019-03-11-129.

Cited by



A Computer Scientist Who Tackles Inequality Through Algorithms




When Rediet Abebe arrived at Harvard University as an undergraduate in 2009, she planned to study mathematics. But her experiences with the Cambridge public schools soon changed her plans.

Abebe, 29, is from Addis Ababa, Ethiopia’s capital and largest city. When residents there didn’t have the resources they needed, she attributed it to community-level scarcity. But she found that argument unconvincing when she learned about educational inequality in Cambridge’s public schools, which she observed struggling in an environment of abundance.

To learn more, Abebe started attending Cambridge school board meetings. The more she discovered about the schools, the more eager she became to help. But she wasn’t sure how that desire aligned with her goal of becoming a research mathematician.

“I thought of these interests as different,” said Abebe, a junior fellow of the Harvard Society of Fellows and an assistant professor at the University of California, Berkeley. “At some point, I actually thought I had to choose, and I was like, ‘OK, I guess I’ll choose math and the other stuff will be my hobby.’”

After college Abebe was accepted into a doctoral program in mathematics, but she ended up deferring to attend an intensive one-year math program at the University of Cambridge. While there, she decided to switch her focus to computer science, which allowed her to combine her talent for mathematical thinking with her strong desire to address social problems related to discrimination, inequity and access to opportunity. She ended up getting a doctorate in computer science at Cornell University.

Today, Abebe uses the tools of theoretical computer science to help design algorithms and artificial intelligence systems that address real-world problems. She has modeled the role played by income shocks, like losing a job or government benefits, in leading people into poverty, and she’s looked at ways of optimizing the allocation of government financial assistance. She’s also working with the Ethiopian government to better account for the needs of a diverse population by improving the algorithm the country uses to match high school students with colleges. 

Abebe is a co-founder of the organizations Black in AI — a community of Black researchers working in artificial intelligence — and Mechanism Design for Social Good, which brings together researchers from different disciplines to address social problems.

Quanta Magazine spoke with Abebe recently about her childhood fear that she’d be forced to become a medical doctor, the social costs of bad algorithmic design, and how her background in math sharpens her work. This interview is based on multiple phone interviews and has been condensed and edited for clarity.

You’re currently involved in a project to reform the Ethiopian national educational system. The work was born in part from your own negative experiences with it. What happened?

In the Ethiopian national system, when you finished 12th grade, you’d take this big national exam and submit your preferences for the 40-plus public universities across the country. There was a centralized assignment process that determined what university you were going to and what major you would have. I was so panicked about this.


I realized I was a high-scoring student when I was in middle school. And the highest-scoring students tended to be assigned to medicine. I was like 12 and super panicked that I might have to be a medical doctor instead of studying math, which is what I really wanted to do.

What did you end up doing?

I thought, “I may have to go abroad.” I learned that in the U.S., you can get full financial aid if you do really well and get into the top schools.

So you went to Harvard as an undergraduate and planned to become a research mathematician. But then you had an experience that changed your plans. What happened?

I was excited to study math at Harvard. At the same time, I was interested in what was going on in the city of Cambridge. There was a massive achievement gap in elementary schools in Cambridge. A lot of students who were Black, Latinx, low-income or students with disabilities, or immigrant students, were performing two to four grades below their peers in the same classroom. I was really interested in why this was happening.

You eventually switched focus from math to computer science. What about computer science made you think that it was a place you could work on social issues that you care about?

It’s an inherently outward-looking field. Let’s take a government organization that has income subsidies it can give out. And it has to do so under budget constraints. You have some objective you’re trying to optimize for and some constraints around fairness or efficiency. So you have to formalize that.

From there, you can design algorithms and prove things about them. So you can say, “I can guarantee that the algorithm does this; I can guarantee that it gives you the optimal solution or at least it’s this close to the optimal solution.”

Does your math background still help?

Math and theoretical computer science force you to be precise. Ambiguity is a bug in mathematics. If I give you a proof and it’s vague, then it’s not complete. On the algorithmic side of things, it forces you to be very explicit about what your goals are and what the input is.

Within computer science, what would you say is your research community?

I’m one of the co-founders and an organizer for Mechanism Design for Social Good. We started in 2016 as a small online reading group that was interested in understanding how we can use techniques from theoretical computer science, economics and operations research communities to improve access to opportunity. We were inspired by how algorithmic and mechanism design techniques have been used in problems like improving kidney exchange and the way students are assigned to schools. We wanted to explore where else these techniques, combined with insights from the social sciences and humanistic studies, can be used.

The group grew steadily. Now it’s massive and spans over 50 countries and multiple disciplines, including computer science, economics, operations research, sociology, public policy and social work.

The term “mechanism design” may not be immediately familiar to a lot of people. What does it mean?

Mechanism design is like if you had an algorithm designed, but you were aware that the input data is something that could be strategically manipulated. So you’re trying to create something that’s robust to that.

When you see a social problem that you want to work on, what’s your process for getting started?

Let’s say I’m interested in income shocks and what impact those have on people’s economic welfare. First I go and learn from people from other disciplines. I talk to social workers, policymakers and nonprofits. I try to absorb as much information as I can and understand as best I can what other experts find useful.

And I let this very bottom-up process determine what types of questions I should tackle. So sometimes that ends up being like, there’s some really interesting data set and people are like, “Here’s what we’ve done with it, but maybe you can do more.” Or it ends up being a modeling question, where there’s some phenomenon that the algorithmic side of my work allows us to capture and model, and then I ask questions around some sort of intervention.

Does your work address any issues tied to the COVID-19 pandemic?

My income-shocks work is extremely timely. If you’re losing a job, or a lot of people are getting sick, those are shocks. Medical expenses are a shock. There’s been this massive global disruption that we all have to deal with. But certain people have to deal with more of it and different types of it than others.

How did you start to dig into this as a research topic?

We were first interested in how to best model welfare when we know individuals are experiencing income shocks. We wanted to see whether we could provide a model of welfare that captures people’s income and wealth, as well as the frequency with which they may experience income shocks and the severity of those shocks.

Once we created a model, we were then able to ask questions around how to provide assistance, such as income subsidies.

And what did you find?

We find, for example, that if the assistance is a wealth subsidy, which gives people a one-time, upfront subsidy, rather than an income subsidy, which is a month-to-month commitment, then the set of individuals you should target can be completely different from one another.

These types of qualitative insights have been useful in discussions with individuals working in policy and nonprofit organizations. Often in discussions around poverty-alleviation programs, we hear statements like, “This program would like to assist the most number of people,” but we ignore that there are a lot of decisions that have to be made to translate such a statement into a concrete allocation scheme.

You also published a paper exploring how different types of big, adverse life events relate to poverty. What did you find?

Predicting what factors lead someone into poverty is very hard. But we can still get qualitative insights about what things help you predict poverty better than others. We find that for male respondents, interactions with the criminal justice system, like being stopped by the police or being a victim of a crime, seem to be very predictive of experiencing poverty in the future. Whereas for female respondents, we find that financial shocks like income decreases, major expenses, benefit decreases and so on seem to hold a lot more predictive power.

You are also the co-founder of the Equity and Access in Algorithms, Mechanisms, and Optimization conference, which is being held for the first time later this year and which engages lots of the types of questions we’ve been talking about. What is its focus?

We are providing an international venue for researchers and practitioners to come together to discuss problems that impact marginalized communities, like housing instability and homelessness, equitable access to education and health care, and digital and data rights. It is inspiring to see the investment folks make to identify the right questions, provide holistic solutions, think critically about unintended consequences, and iterate many times over as needed.

You also have that ongoing work with Ethiopia’s government on its national education system. How are you trying to change the way this assignment process works?

I’m working with the Ethiopian Ministry of Education to understand and inform the matching process of seniors in high school to public universities. We’re still in the beginning stages of this.

Ethiopia has over 80 different ethnic groups and an incredibly diverse people. There are diversity considerations. You have different genders, different ethnic groups and different regions that they came from.

You might say, “We’re still going to try to make sure that everyone gets one of their top three choices.” But we want to make sure that you don’t end up in a school that has everyone from the same region or everyone is one gender.

What are the costs of getting the matching process wrong?

I mean, in any of the social problems that I work on, the cost of getting something wrong is super high. With this matching case, once you match to something, that’s probably where you’re going to go because the outside options might not be good. And so I’m deciding whether you end up close to home versus really, really far away from home. I’m deciding whether you end up in a region or in a school that has studies, classes and research that align with your work or not. It really, really matters.

Coinsmart. Beste Bitcoin-Börse in Europa

Continue Reading


Cells Form Into ‘Xenobots’ on Their Own




Early last year, the biologist Michael Levin and his colleagues offered a glimpse of how versatile living matter can be. Levin and Douglas Blackiston, a member of his laboratory at the Allen Discovery Center of Tufts University, brought together nascent skin and muscle cells from a frog embryo and shaped the multicelled assemblies by hand. This sculpting process was guided by an algorithm developed by the computer scientists Josh Bongard and Sam Kriegman of the University of Vermont, which searched for simulated arrangements of the two cell types capable of organized movement. One design, for example, had two twitching leglike stumps on the bottom for pushing itself along.

The researchers let the cell clusters assemble in the right proportions and then used micro-manipulation tools to move or eliminate cells — essentially poking and carving them into shapes like those recommended by the algorithm. The resulting cell clusters showed the predicted ability to move over a surface in a nonrandom way.

The team dubbed these structures xenobots. While the prefix was derived from the Latin name of the African clawed frogs (Xenopus laevis) that supplied the cells, it also seemed fitting because of its relation to xenos, the ancient Greek for “strange.” These were indeed strange living robots: tiny masterpieces of cell craft fashioned by human design. And they hinted at how cells might be persuaded to develop new collective goals and assume shapes totally unlike those that normally develop from an embryo.

But that only scratched the surface of the problem for Levin, who wanted to know what might happen if embryonic frog cells were “liberated” from the constraints of both an embryonic body and researchers’ manipulations. “If we give them the opportunity to re-envision multicellularity,” Levin said, then his question was, “What is it that they will build?”

Some of those answers are now being unveiled in work appearing today in Science Robotics. It describes a new generation of xenobots — ones that took shape on their own, entirely without human guidance or assistance.

At a glance, these xenobots might be mistaken for other microscopic aquatic animals — amoebas or plankton or Giardia parasites — swimming here and there with apparent agency. Some move in orbit around particles in the water, while others patrol back and forth as though on the lookout for something. Collections of them in a petri dish act like a community, responding to one another’s presence and participating in collective activities.

When he shows movies of these spontaneously grown xenobots to other biologists and asks them to guess what they are, Levin said that “People say, ‘It’s an animal you found in a pond somewhere.’” They are astounded when he reveals that “it’s 100% Xenopus laevis.” These microscopic entities are utterly unlike any stage in the normal development of a frog.

The xenobots are turning some conventional views in developmental biology upside down. They suggest that the frog genome doesn’t uniquely instruct cells about how to proliferate, differentiate and arrange themselves into a frog body. Rather, that’s just one possible outcome of the process that the genomic programming permits.

For the evolutionary biologist Eva Jablonka of Tel Aviv University, who was not involved in the work, xenobots are nothing less than a new type of creature — one “defined by what it does rather than to what it belongs developmentally and evolutionarily.” She suspects the findings might illuminate the very origins of multicellular life.

Levin believes that his cell-bots disclose something profound about how cells and development work. The results seem to imply that individual cells have a kind of decision-making capacity that creates a palette of possible bodies they could build — constrained and guided by the genome but not defined by it. Rules operating above the level of genes appear to specify biological form, and the way we see them embodied in xenobots can tell us something about how they operate. Ricard Solé, a complex systems theorist at Pompeu Fabra University in Spain, said that the new experiments “open a whole new window to interrogate development — and more generally, novel forms of complex life.”

It’s certainly not just about frogs. “If the organization we see in xenobots is the basic state of multicellular animal organization,” said Jablonka, then she anticipates that human cells will behave in the same way. Someday, if we can learn and guide the effect of these rules, Levin thinks, we might be able to achieve things that our cells don’t seem able to manage on their own, such as the regeneration of limbs.

Cells Find Their Own Solutions

The experiments described in the paper published today were remarkably simple. The same team of researchers, along with Emma Lederer of Levin’s lab, removed cells from developing frog embryos that had already specialized into epithelial cells and left them to develop in clusters on their own without the rest of the embryo, which normally provides the signals that guide cells to become the “right” type in the “right” place.

What the cells did first was unremarkable: They gathered into a ball, composed of dozens of cells or a few hundred. That kind of behavior was already well known and reflects the tendency of skin cells to make their surface area as small as possible after tissue damage, which helps wounds to heal.

Then things got weird. Frog skin is generally covered with a protective layer of mucus that keeps it moist; to ensure that the mucus covers the skin evenly, the skin cells have little hairlike protrusions called cilia, which can move and beat. We have them, too, on the lining of our lungs and respiratory tract, where their beating motion helps sweep away dirt in the mucus.

But the frog skin cell clusters quickly began to use their cilia for a different purpose: to swim around by beating in coordinated waves. A midline formed on the cluster, “and the cells on one side row to the left and those on the other side row to the right, and this thing takes off. It starts zooming around,” Levin said

How does the xenobot decide where to draw the midline? And what even “tells” it that doing this would be useful? That’s not yet clear.

But these entities don’t just move; they seem responsive to their environment. “They’ll sometimes go straight, sometimes in circles,” Levin said. “If there’s a particle in the water, they’ll circle it. They will do mazes — they can take corners without bumping into anything.”

He added, “I’m quite certain they do a lot of things we don’t even recognize yet.”

Jablonka thinks that most animal developmental biologists won’t be surprised by the outcome of experiments like this — but will kick themselves for not having looked for it. “They would probably say, ‘Yes, of course! Why did we not do this simple experiment before?’” she said. Solé suspects others might have accidently stumbled on similar observations, but “thought it was a mistake, or simply impossible.”

Or it might have just been overlooked — because most developmental research only aims to reveal how whole organisms or parts of them grow under normal or mildly manipulated conditions, Jablonka said. But Levin’s work has a new goal, she says: “Constructing an autonomous creature that has nothing to do with the specific form of the [original] organism.”

Xenobots normally live for about a week, subsisting on the nutrients passed down from the fertilized egg they came from. But in rare cases, by “feeding” them with the right nutrients, Levin’s team has been able to keep xenobots active for more than 90 days. The longer-lived ones don’t stay the same but begin to change, as though they are on a new developmental path — destination unknown. None of their incarnations look anything like a frog as it grows from an embryo to a tadpole.

Channels of Communication

Media reports of the earlier handmade xenobots both reveled in and worried about the idea of miniature robots made from living matter. Might they breed and develop minds of their own? In truth, neither possibility was remotely likely: The cells could survive in a nutrient medium, but they couldn’t replicate into new xenobots. And they didn’t have any nerve cells that might act like a mind.

But even though xenobots have no nervous system, that doesn’t mean the cells can’t communicate with one another.  One cell might release a chemical that sticks to surface proteins on another cell, triggering a biochemical process within the recipient. This type of cell signaling happens constantly during embryonic development, and it’s one way that neighboring cells control one another’s fate — the type of tissue each cell ultimately becomes. Adhesive proteins enable cells to attach to one another and to sense mechanical forces and deformations. In developing embryos, mechanical cues like this may also guide to become the right tissue type.

Levin thinks that cells also commonly communicate electrically — that this isn’t just a property of nerve cells, although they may have specialized to make good use of it. In a xenobot, “there’s a network of calcium signaling,” Levin said — an exchange of calcium ions like that seen between neurons. “These skin cells are using the same electrical properties that you would find in the neural network of a brain.”

For example, if three xenobots are set spaced apart in a row, and one of them is activated by being pinched, it will emit a pulse of calcium that, within seconds, shows up in the other two — “a chemical signal that goes through the water saying that someone just got attacked,” Levin said.

He thinks that intercellular communications create a sort of code that imprints a form, and that cells can sometimes decide how to arrange themselves more or less independently of their genes. In other words, the genes provide the hardware, in the form of enzymes and regulatory circuits for controlling their production. But the genetic input doesn’t in itself specify the collective behavior of cell communities.

Instead, Levin thinks that it programs cells with an ensemble of tendencies that produce a repertoire of behaviors. Under the normal conditions of embryogenesis, those behaviors follow a certain path toward forming the organisms we know. But give the cells a very different set of circumstances, and other behaviors and new emergent shapes will appear.

“What the genome provides for the cells is some mechanism that allows them to undertake goal-directed activities,” Levin said — in effect, a drive to adapt and survive.

Innate Drives to Survive

One such goal that Levin and his colleagues think they have seen is known as infotaxis, a push for cells to maximize the amount of information they get from their neighbors. Cells may also seek to minimize “surprise,” the chance of encountering something unexpected. The best way to do that, Levin says, is to surround yourself with copies of yourself. Some other goals are based on pure mechanics and geometry, such as minimizing the surface area of a cluster.

The genomic programs for the pursuit of these goals, he says, are very ancient. Indeed, a reversion to something like ancestral behavior from before cells figured out how to work together may emerge in cancers — where cells adopt a potentially lethal mode of organizing themselves that sets proliferation ahead of cooperation.

If that’s right, then the variety of body shapes and functions in natural organisms is not so much the result of specific developmental programs written into their genomes, but of tweaks to the strengths and tendencies of these single-cell behaviors, which may come from both the genome and the environment.

Jablonka guesses that the behaviors on display in the xenobots are probably “something like the most basic self-organization of a multicellular animal-cell aggregate.” That is, they are what happens when both the constraints on form and the resources and opportunities provided by the environment are minimal. “It tells you something about the physics of biological, developing multicellular systems,” she said: “how sticky animal cells interact.” For that reason, she thinks the work might hold clues to the emergence of multicellularity in evolutionary history.

Solé agrees with that. “One of our dreams in the study of synthetic complexity is to be able to move beyond the actual repertoire of life forms that we can see around us, and to explore alternatives,” he said. The fossil traces of simple animals that began to evolve before the Cambrian era, more than about 540 million years ago, give only the vaguest hints of how multicellularity arose through the interactions of single-celled organisms.

That cells might be programmed to collectively “compute” their own ways solutions to growth and form, rather than for their genome to prescribe them, makes sense in evolutionary terms, because it means that the collective goals of the cells in a tissue remain resilient to disturbance. There’s no need to hard-wire a contingency plan into the genome for every injury or challenge the tissue might face, because the cells will spontaneously revert to the right course. “What you have is organs and tissues that have very specific large-scale goals, and if you try to deviate them off of that, they will come back,” Levin said.

This robustness against disruption seems to be borne out by the fact that the xenobots can regenerate from damage. “Once they’ve developed this new body, they have some ability to maintain it,” Levin said. In one experiment, a xenobot was cut almost in two, its ragged halves opened up like a hinge. Left to itself, the hinge shut again and the two fragments rebuilt the original shape. Such a movement requires substantial force applied at the hinge joint — a situation skin cells would not normally encounter, but which they can apparently adapt to.

Navigating Without a Map

Whether the xenobots really are on a new and distinct developmental path remains unclear at this point. Christoph Adami, a microbiologist at Michigan State University, suggests that the xenobots’ development of cilia, for example, might not reflect some novel “decision” but rather just an automatic response to the mechanical forces acting on the cell clusters. He thinks that more work, perhaps by tracking changes in gene expression, will be required to establish what’s happening.

But Levin said that the idea of cells collectively deciding on and remembering goals is supported by experiments that he and his colleagues conducted previously on Xenopus tadpoles. To become a frog, a tadpole has to rearrange its face; the genome was thought to hard-wire a set of cell movements for every facial feature. “I had doubts about this story,” Levin said, “so we made what we call Picasso tadpoles. By manipulating the electrical signals, we made tadpoles where everything was in the wrong place. It was totally messed up, like Mr. Potato Head.”

And yet from this abstract rearrangement of tadpole features, normal frogs emerged. “During metamorphosis, the organs take unusual paths that they don’t normally take, until they settle in the right place for a normal frog face,” Levin said. It’s as if the developing organism has a target design, a global plan, that it can achieve from any starting configuration. This is far different from the view that cells are “following orders” each step of the way. “There’s some way the system is storing a large-scale map of what it’s supposed to build,” Levin said. That map is not in the genome, however, but in a kind of collective memory of the cells themselves.

If, however, you totally reconfigure the cells, it seems you can change the map. The next step is to work out what the rules are that create the new map — so that we can control it and build what we want. “We know very little about the plasticity of developmental programs,” Adami said. “Our thinking has been shaped by a few well-studied organisms and genes, like worms, flies and sea urchins. But there is likely an iceberg of ancient potential pathways under every tip.”

Fundamentally, Levin says, no one yet know what factors specifically induce cells to multiply and spread in a flat layer, gather into a dense mass, make an organlike structure … or grow into a mobile “bot.” The challenge now is to discover the rules and to learn how to apply them for desired outcomes. “We need to learn how cells themselves encode whatever pattern they’re supposed to build, and then to rewrite that target morphology,” he said.

He thinks the outcomes might include the possibility of regenerating tissue and limbs — a trick that some amphibians, such as axolotls, are adept at but which we can’t do. “To me, this is the answer to the problem in regenerative medicine that we’re going to hit very soon,” he said. We’re very good at switching genes and manipulating molecules in cells, but we don’t know how to turn those dials to make fingers, eyes or limbs. “It’s entirely not obvious how you get changes to 3D anatomy by manipulating that lowest genetic level,” Levin said. “We need to learn how cells themselves encode whatever pattern they’re supposed to build, and then to rewrite that target morphology and let the cells do their thing.”

The potential for cells to find their way to body plans was dramatically illustrated recently with a report that when some sea slugs become heavily infected with parasites, their head separates from the body through self-induced decapitation and then regrows an entire new body within a few weeks. It’s tempting to see this as just an extreme case of regeneration, but that perspective leaves some profound questions hanging.

“First, where does the information for the anatomy it’s trying to regenerate come from?” Levin asked. “It’s easy to say ‘genome,’ but we now know from our xenobots that there is extreme plasticity, and cells are actually willing and able to build very different bodies.”

The second question, he says, is how regeneration knows when to stop. “How do cells know when the ‘correct’ final shape has been produced, and they can stop remodeling and growing?” he asked. The answer is critical for understanding the unruliness of cancer cells, he thinks.

Levin’s group is now studying whether adult human cells (which lack the versatility of embryonic cells) display a similar ability to assemble into “bots” if given the chance. Preliminary findings suggest that they do, the researchers said.

Organisms, Living Machines or Both?

In their paper, Levin and his colleagues discuss the potential of xenobots as “living machines” that could be used as microscopic probes or deployed in swarms to perform collective operations such as cleaning up watery environments. Adami, however, remains to be convinced that the Tufts team understands enough to begin to do this. “They have not shown that you can design these things, that you can program them, that they are doing anything that is not ‘normal’ once you release the mechanical constraints,” he said.

Levin is undeterred, however, and thinks that the ramifications of xenobots for fundamental science may ultimately go far beyond their biomedical or bioengineering applications, to any collective system that exhibits an emergent design not specifically encoded in its parts.

“I think this is bigger than even biology,” Levin said. “We need a science of where larger-scale goals come from. We’re going to be surrounded by the internet of things, by swarm robotics, and even by corporations and companies. We don’t know where their goals come from, we’re not good at predicting them and we’re certainly not good at programming them.”

Solé shares that wider vision. “This work is remarkable in particular for how much it reveals about the generative potential of self-organization,” he said. He feels it might broaden our view of how nature creates its endless forms: “One thing we also know well is that nature constantly tinkers with biological matter and that different functions or solutions can be achieved by different combinations of pieces.” Maybe an animal, even a human one, is not an entity written in stone — or rather, in DNA — but is just one possible outcome of cells making decisions.

Are xenobots “organisms,” though? Absolutely, Levin says — provided we adopt the right meaning of the word. A collection of cells that has clear boundaries and well-defined, collective, goal-directed activity can be considered a “self.” When xenobots encounter each other and temporarily stick, they don’t merge; they maintain and respect their selfhood. They “have natural boundaries that demarcate them from the rest of the world and allow them to have coherent functional behaviors,” Levin said. “That’s at the core of what it means to be an organism.”

“They are organisms,” Jablonka agreed. It’s true that xenobots presumably can’t reproduce — but then, neither can a mule. Moreover, “a xenobot may be induced to fragment and form two small ones,” she said, “and maybe some cells will divide and differentiate into motile and nonmotile ones.” If that’s so, xenobots could even undergo a kind of evolution. In which case, who knows what they might become?

Coinsmart. Beste Bitcoin-Börse in Europa

Continue Reading


Mathematicians Find a New Class of Digitally Delicate Primes




Take a look at the numbers 294,001, 505,447 and 584,141. Notice anything special about them? You may recognize that they’re all prime — evenly divisible only by themselves and 1 — but these particular primes are even more unusual.

If you pick any single digit in any of those numbers and change it, the new number is composite, and hence no longer prime. Change the 1 in 294,001 to a 7, for instance, and the resulting number is divisible by 7; change it to a 9, and it’s divisible by 3.

Such numbers are called “digitally delicate primes,” and they’re a relatively recent mathematical invention. In 1978, the mathematician and prolific problem poser Murray Klamkin wondered if any numbers like this existed. His question got a quick response from one of the most prolific problem solvers of all time, Paul Erdős. He proved not only that they do exist, but also that there are an infinite number of them — a result that holds not just for base 10, but for any number system. Other mathematicians have since extended Erdős’ result, including the Fields Medal winner Terence Tao, who proved in a 2011 paper that a “positive proportion” of primes are digitally delicate (again, for all bases). That means the average distance between consecutive digitally delicate primes remains fairly steady as prime numbers themselves get really big — in other words, digitally delicate primes won’t become increasingly scarce among the primes.

Now, with two recent papers, Michael Filaseta of the University of South Carolina has carried the idea further, coming up with an even more rarefied class of digitally delicate prime numbers.

“It’s a remarkable result,” said Paul Pollack of the University of Georgia.

Motivated by Erdős’ and Tao’s work, Filaseta wondered what would happen if you included an infinite string of leading zeros as part of the prime number. The numbers 53 and …0000000053 have the same value, after all; would changing any one of those infinite zeros tacked on to a digitally delicate prime automatically make it composite?

Filaseta decided to call such numbers, assuming they existed, “widely digitally delicate,” and he investigated their properties in a November 2020 paper with his former graduate student Jeremiah Southwick.

Not surprisingly, the added condition makes such numbers harder to find. “294,001 is digitally delicate, but not widely digitally delicate,”  Pollack said, “since if we change …000,294,001 to …010,294,001, we get 10,294,001” — another prime number.

In fact, Filaseta and Southwick couldn’t find one example in base 10 of a widely digitally delicate prime, despite looking through all the integers up to 1,000,000,000. But that didn’t prevent them from proving some strong statements about these hypothetical numbers.

First, they showed that such numbers are indeed possible in base 10, and, what’s more, an infinite number of them exist. Going a step further, they also proved that a positive proportion of prime numbers are widely digitally delicate, just as Tao had done for digitally delicate primes. (In his doctoral dissertation, Southwick achieved the same results in bases 2 through 9, 11 and 31.)

Pollack was impressed with the findings. “There are infinitely many possible things you’re allowed to do to these numbers and, no matter which you do, you’re still guaranteed a composite answer,” he said.

The proof relied on two tools. The first, called covering systems or covering congruences, was invented by Erdős in 1950 to solve a different problem in number theory. “What a covering system does for you,” Southwick said, “is to give you a large number of buckets, along with a guarantee that every positive integer is in at least one of those buckets.” If, for example, you divide all positive integers by 2, you’ll end up with two buckets: one containing even numbers in which the remainder is 0 and one containing odd numbers in which the remainder is 1. In this way, all positive integers have been “covered,” and the numbers occupying the same bucket are considered “congruent” to each other.

The situation involving widely digitally delicate primes is more complicated, of course. You’ll need a lot more buckets, something on the order of 1025,000, and in one of those buckets every prime number is guaranteed to become composite if any of its digits, including its leading zeros, is increased.

But to be widely digitally delicate, a prime number must also become composite if any of its digits is decreased. That’s where the second tool, called a sieve, comes in. Sieve methods, which date back to the ancient Greeks, offer a way of counting, estimating or setting limits on the number of integers that satisfy certain properties. Filaseta and Southwick used a sieve argument, similar to the approach Tao took in 2011, to show that if you take prime numbers in the aforementioned bucket and decrease one of the digits, a positive proportion of those primes will become composite. In other words, a positive proportion of those primes are widely digitally delicate.

“The Filaseta-Southwick theorem,” Pollack said, “is a beautiful and unexpected illustration of the power of covering congruences.”

Then, in a January paper, Filaseta and his current graduate student Jacob Juillerat made an even more astonishing claim: There exist arbitrarily long sequences of consecutive primes, each of which is widely digitally delicate. It would be possible, for instance, to find 10 consecutive primes that are widely digitally delicate. But to do so, you’d have to examine a huge number of primes, Filaseta said, “probably more than the number of atoms in the observable universe.” He compared it to winning the lottery 10 times in a row: The odds of doing so are extraordinarily slim, but still nonzero.

Filaseta and Juillerat proved their theorem in two stages. First, they used covering system arguments to prove that there is a bucket containing infinitely many primes, all of which are widely digitally delicate. In the second step, they applied a theorem, proved in 2000 by Daniel Shiu, to show that somewhere in the list of all primes, there exists any arbitrary number of consecutive primes contained in this bucket. Those consecutive primes, by virtue of being in that bucket, are necessarily widely digitally delicate.

Carl Pomerance of Dartmouth College thoroughly enjoyed these papers, calling Filaseta “a master at applying covering congruences to many interesting number theory problems. Mathematics can be an exercise in bringing powerful tools to bear, and it can also be pure fun.”

At the same time, Pomerance noted, representing a number in terms of its digits in base 10 might be convenient, “but it doesn’t go to the essence of what that number really is.” There are more fundamental ways of representing numbers, he maintained, such as the way Mersenne primes are defined — prime numbers of the form 2p – 1 for a prime p.

Filaseta agrees. Nevertheless, the recent papers raise questions that may be worth exploring. Filaseta is curious as to whether widely digitally delicate primes exist in every base. Juillerat, for his part, wonders whether “there are infinitely many primes that become composite when you insert a digit between two digits, instead of just replacing a digit.”

Another tantalizing question comes from Pomerance: Do all primes eventually become digitally delicate or widely digitally delicate as you approach infinity? Equivalently, is there a limited number of primes that are not digitally delicate (or widely digitally delicate)? He feels that the answer to that question, however it is phrased, must be no. But he and Filaseta consider it an intriguing conjecture, one that neither of them knows how to prove without relying on another unproved conjecture.

“The story of mathematical research is that you don’t know beforehand if you can solve a challenging problem or whether it will lead to something important,” Pomerance said. “You can’t decide in advance: Today I’m going to do something valuable. Though it’s great, of course, when things turn out that way.”

Coinsmart. Beste Bitcoin-Börse in Europa

Continue Reading


Distinguishing noisy boson sampling from classical simulations




Valery Shchesnovich

Centro de Ciências Naturais e Humanas, Universidade Federal do ABC, Santo André, SP, 09210-170 Brazil

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


Giving a convincing experimental evidence of the quantum supremacy over classical simulations is a challenging goal. Noise is considered to be the main problem in such a demonstration, hence it is urgent to understand the effect of noise. Recently found classical algorithms can efficiently approximate, to any small error, the output of boson sampling with finite-amplitude noise. In this work it is shown analytically and confirmed by numerical simulations that one can efficiently distinguish the output distribution of such a noisy boson sampling from the approximations accounting for low-order quantum multiboson interferences, what includes the mentioned classical algorithms. The number of samples required to tell apart the quantum and classical output distributions is strongly affected by the previously unexplored parameter: density of bosons, i.e., the ratio of total number of interfering bosons to number of input ports of interferometer. Such critical dependence is strikingly reminiscent of the quantum-to-classical transition in systems of identical particles, which sets in when the system size scales up while density of particles vanishes.

Small-size quantum devices are shown to have superior computational powers as compared to digital computers. Boson Sampling is one of such quantum systems. What level of noise can prevent demonstration of quantum advantage? Can one distinguish a noisy quantum device from classical simulations? It is shown in the present work how a realistic noisy Boson Sampling with single photons can be efficiently distinguished from a wide range of classically efficient simulations which approximate its output distribution.

► BibTeX data

► References

[1] R. Feynman. Simulating Physics with Computers. Int. J. Theoret. Phys. 21, 467-488 (1982).

[2] P. W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the 35th Annual Symposium Foundations of Computer Science (IEEE, New York, 1994), p. 124–134.

[3] J. Preskill. Quantum Computing in the NISQ era and beyond. Quantum 2, 79 (2018).

[4] S. Aaronson and A. Arkhipov, The computational complexity of linear optics. Theory of Computing 9, 143 (2013).

[5] M. J. Bremner, A. Montanaro, and D. J. Shepherd. Achieving quantum supremacy with sparse and noisy commuting quantum computations. Quantum 1, 8 (2017).

[6] J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert. Architectures for Quantum Simulation Showing a Quantum Speedup. Phys. Rev. X 8, 021010 (2018).

[7] S. O. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven. Characterizing quantum supremacy in near-term devices. Nature Physics, 14, 595-600 (2018).

[8] X. Gao, S.-T. Wang, and L.-M. Duan. Quantum Supremacy for Simulating a Translation-Invariant Ising Spin Model. Phys. Rev. Lett. 118, 040502 (2017).

[9] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505-510 (2019).

[10] G. Kalai. The Quantum Computer Puzzle. Notices of the AMS, 63, 508-516 (2016).

[11] A. Arkhipov and G. Kuperberg. The bosonic birthday paradox. Geometry & Topology Monographs 18, 1-7 (2012).

[12] E. R. Caianiello. On quantum field theory — I: explicit solution of Dyson’s equation in electrodynamics without use of Feynman graphs. Nuovo Cimento, 10, 1634-1652 (1953); Combinatorics and Renormalization in Quantum Field Theory, Frontiers in Physics, Lecture Note Series (W. A. Benjamin, Reading, MA, 1973).

[13] S. Scheel. Permanents in linear optical networks. arXiv:quant-ph/​0406127.

[14] L. G. Valiant. The complexity of computing the permanent. Theoretical Comput. Sci., 8, 189-201 (1979).

[15] M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM 51, 671-697 (2004).

[16] S. Aaronson. A linear-optical proof that the permanent is $#$P-hard. Proc. Roy. Soc. London A, 467, 3393–3405 (2011).

[17] H. Ryser, Combinatorial Mathematics (Cams Mathematical Monographs, No. 14; published by The Mathematical Association of America, distributed by John Wiley and Sons, 1963).

[18] M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. C. Ralph, and A. G. White. Photonic Boson Sampling in a Tunable Circuit. Science 339, 794-798 (2013).

[19] J. B. Spring, B. J. Metcalf, P. C. Humphreys, W. S. Kolthammer, X.-M. Jin, M. Barbieri, A. Datta, N. Thomas-Peter, N. K. Langford, D. Kundys, J. C. Gates, B. J. Smith, P. G. R. Smith, and I. A. Walmsley. Boson Sampling on a Photonic Chip. Science, 339, 798-801 (2013).

[20] M. Tillmann, B. Dakić, R. Heilmann, S. Nolte, A. Szameit, and P. Walther. Experimental boson sampling. Nature Photonics, 7, 540-544 (2013).

[21] A. Crespi, R. Osellame, R. Ramponi, D. J. Brod, E. F. Galvão, N. Spagnolo, C. Vitelli, E. Maiorino, P. Mataloni, and F. Sciarrino. Integrated multimode interferometers with arbitrary designs for photonic boson sampling. Nature Photonics, 7, 545-549 (2013).

[22] J. Carolan, J. D. A. Meinecke, P. J. Shadbolt, N. J. Russell, N. Ismail, K. Wörhoff, T. Rudolph, M. G. Thompson, J. L. O’Brien, J. C. F. Matthews, and A. Laing. On the experimental verification of quantum complexity in linear optics. Nature Photonics, 8, 621-626 (2014).

[23] A. P. Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, J. L. O’Brien, and T. C. Ralph. Boson Sampling from a Gaussian State. Phys. Rev. Lett. 113, 100502 (2014).

[24] M. Bentivegna, N. Spagnolo, C. Vitelli, F. Flamini, N. Viggianiello, L. Latmiral, P. Mataloni, D. J. Brod, E. F. Galvão, A. Crespi, R. Ramponi, R. Osellame, and F. Sciarrino. Experimental scattershot boson sampling. Science Advances 1, e1400255 (2015).

[25] H.-S. Zhong, L.-C. Peng, Y. Li, Y. Hu, W. Li, J. Qin, D. Wu, W. Zhang, H. Li, L. Zhang, Z. Wang et al. Experimental Gaussian Boson sampling. Science Bulletin, 64, 511-515 (2019).

[26] K. R. Motes, A. Gilchrist, J. P. Dowling, and P. P. Rohde. Scalable Boson Sampling with Time-Bin Encoding Using a Loop-Based Architecture. Phys. Rev. Lett. 113, 120501 (2014).

[27] Y. He, X. Ding, Z. E. Su, H. L. Huang, J. Qin, C. Wang, S. Unsleber, C. Chen, H. Wang, Y. M. He, et al. Time-Bin-Encoded Boson Sampling with a Single-Photon Device. Phys. Rev. Lett. 118, 190501 (2017).

[28] J. C. Loredo, M. A. Broome, P. Hilaire, O. Gazzano, I. Sagnes, A. Lemaitre, M. P. Almeida, P. Senellart, and A. G. White. Boson Sampling with Single-Photon Fock States from a Bright Solid-State Source. Phys. Rev. Lett. 118, 130503 (2017).

[29] H. Wang, Y. He, Y.-H. Li, Z.-E. Su, B. Li, H.-L. Huang, X. Ding, M.-C. Chen, C. Liu, J. Qin et al. High-efficiency multiphoton boson sampling. Nature Photonics 11, 361-365 (2017).

[30] H. Wang, W. Li, X. Jiang, Y. M. He, Y. H. Li, X. Ding, M. C. Chen, J. Qin, C. Z. Peng, C. Schneider et al. Toward Scalable Boson Sampling with Photon Loss. Phys. Rev. Lett. 120, 230502 (2018).

[31] H.-S. Zhong, Y. Li, W. Li, L.-C. Peng, Z.-E. Su, Y. Hu, Y.-M. He, X. Ding, W. Zhang, H. Li et al. 12-Photon Entanglement and Scalable Scattershot Boson Sampling with Optimal Entangled-Photon Pairs from Parametric Down-Conversion. Phys. Rev. Lett. 121, 250505 (2018).

[32] H. Wang, J. Qin, X. Ding, M.-C. Chen, S. Chen, X. You, Y.-M. He, X. Jiang, L. You, Z. Wang, C. Schneider, J. J. Renema, S. Höfling, C.-Y. Lu, and J.-W. Pan. Boson Sampling with 20 Input Photons and a 60-Mode Interferometer in a $10^{14}$-Dimensional Hilbert Space. Phys. Rev. Lett. 123, 250503 (2019).

[33] C. Shen, Z. Zhang, and L.-M. Duan. Scalable Implementation of Boson Sampling with Trapped Ions. Phys. Rev. Lett. 112, 050504 (2014).

[34] B. Peropadre, G. G. Guerreschi, J. Huh, and A. Aspuru-Guzik. Proposal for Microwave Boson Sampling. Phys. Rev. Lett. 117, 140505 (2016).

[35] S. Goldstein, S. Korenblit, Y. Bendor, H. You, M. R. Geller, and N. Katz. Decoherence and interferometric sensitivity of boson sampling in superconducting resonator networks. Phys. Rev. B 95, 020502(R) (2017).

[36] A. Deshpande, B. Fefferman, M. C. Tran, M. Foss-Feig and A. V. Gorshkov. Dynamical Phase Transitions in Sampling Complexity. Phys. Rev. Lett. 121, 030501 (2018).

[37] B. Peropadre, J. Huk and C. Sabín. Dynamical Casimir Effect for Gaussian Boson Sampling. Scientific Reports 8, 3751 (2018).

[38] A. Neville, C. Sparrow, R. Clifford, E. Johnston, P. M. Birchall, A. Montanaro, and A. Laing. Classical boson sampling algorithms with superior performance to near-term experiments. Nature Physics 13, 1153-1157 (2017).

[39] P. Clifford, and R. Clifford. The Classical Complexity of Boson Sampling. Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms pp. 146–55.

[40] G. Kalai and G. Kindler. Gaussian Noise Sensitivity and BosonSampling. arXiv:1409.3093 [quant-ph].

[41] A. Leverrier and R. García-Patrón. Analysis of circuit imperfections in BosonSampling. Quant. Inf. & Computation 15, 489-512 (2015).

[42] V. S. Shchesnovich. Sufficient condition for the mode mismatch of single photons for scalability of the boson-sampling computer. Phys. Rev. A 89, 022333 (2014).

[43] A. Arkhipov. BosonSampling is robust against small errors in the network matrix. Phys. Rev. A 92, 062326 (2015).

[44] S. Aaronson and D. J. Brod. BosonSampling with lost photons. Phys. Rev. A 93, 012335 (2016).

[45] L. Latmiral, N. Spagnolo and F. Sciarrino. Towards quantum supremacy with lossy scattershot boson sampling. New J. Phys. 18, 113008 (2016).

[46] P. P. Rohde and T. C. Ralph. Error tolerance of the boson-sampling model for linear optics quantum computing. Phys. Rev. A 85, 022332 (2012).

[47] S. Rahimi-Keshari, T. C. Ralph, and C. M. Caves. Sufficient Conditions for Efficient Classical Simulation of Quantum Optics. Phys. Rev. X 6, 021039 (2016).

[48] J. J. Renema, A. Menssen, W. R. Clements, G. Triginer, W. S. Kolthammer, and I. A. Walmsley. Efficient Classical Algorithm for Boson Sampling with Partially Distinguishable Photons. Phys. Rev. Lett. 120, 220502 (2018).

[49] M. Oszmaniec and D. J. Brod. Classical simulation of photonic linear optics with lost particles. New J. Phys. 20, 092002 (2018).

[50] R. García-Patrón, J. J. Renema, and V. S. Shchesnovich. Simulating boson sampling in lossy architectures. Quantum 3, 169 (2019).

[51] D. J. Brod and M. Oszmaniec. Classical simulation of linear optics subject to nonuniform losses. Quantum 4, 267 (2020).

[52] J. J. Renema, V. S. Shchesnovich, and R. García-Patrón. Classical simulability of noisy boson sampling. arXiv:1809.01953 [quant-ph].

[53] V. S. Shchesnovich. Noise in boson sampling and the threshold of efficient classical simulatability. Phys. Rev. A 100, 012340 (2019).

[54] S. Aaronson and A. Arkhipov. Bosonsampling is far from uniform. Quant. Inform. & Computation 14, 1383 (2014).

[55] C. Gogolin, M. Kliesch, L. Aolita, and J. Eisert. Boson-Sampling in the light of sample complexity. arXiv:1306.3995 [quant-ph].

[56] V. S. Shchesnovich. Universality of Generalized Bunching and Efficient Assessment of Boson Sampling. Phys. Rev. Lett. 116, 123601 (2016).

[57] M. Walschaers, J. Kuipers, J.-D. Urbina, K. Mayer, M. C. Tichy, K. Richter, and A. Buchleitner. Statistical benchmark for BosonSampling. New J. Phys. 18, 032001 (2016).

[58] T. Giordani, F. Flamini, M. Pompili, N. Viggianiello, N. Spagnolo, A. Crespi, R. Osellame, N. Wiebe, M. Walschaers, A. Buchleitner, and F. Sciarrino. Experimental statistical signature of many-body quantum interference. Nature Photonics 12, 173-178 (2018).

[59] S. T. Wang and L.-M. Duan. Certification of Boson Sampling Devices with Coarse-Grained Measurements. arXiv:1601.02627 [quant-ph].

[60] I. Agresti, N. Viggianiello, F. Flamini, N. Spagnolo, A. Crespi, R. Osellame, N. Wiebe, and F. Sciarrino. Pattern Recognition Techniques for Boson Sampling Validation. Phys. Rev. X 9, 011013 (2019).

[61] V. S. Shchesnovich. On the classical complexity of sampling from quantum interference of indistinguishable bosons. Int. J. of Quantum Inform. 18, 2050044 (2020).

[62] A. I. Barvinok. Two Algorithmic Results for the Traveling Salesman Problem. Math. of Oper. Research, 21 65-84 (1996); see theorem (3.3).

[63] V. S. Shchesnovich. Asymptotic evaluation of bosonic probability amplitudes in linear unitary networks in the case of large number of bosons. Int. J. Quantum Inform. 11, 1350045 (2013); see appendix D.

[64] A. E. Moylett, R. García-Patrón, J. J. Renema, and P. S. Turner. Classically simulating near-term partially-distinguishable and lossy boson sampling. Quantum Sci. Technol. 5, 015001 (2020).

[65] A. L. Migdall, D. Branning, and S. Castelletto. Tailoring single-photon and multiphoton probabilities of a single-photon on-demand source. Phys. Rev. A 66, 053805. (2002).

[66] S. M. Barnett, C. R. Gilson, B. Huttner, and N. Imoto. Field Commutation Relations in Optical Cavities. Phys. Rev. Lett. 77, 1739 (1996).

[67] C. K. Hong, Z. Y. Ou, and L. Mandel. Measurement of subpicosecond time intervals between two photons by interference. Phys. Rev. Lett. 59, 2044 (1987).

[68] V. S. Shchesnovich. Partial indistinguishability theory for multiphoton experiments in multiport devices. Phys. Rev. A 91, 013844 (2015).

[69] R. P. Stanley, Enumerative Combinatorics, 2nd ed., Vol. 1 (Cambridge University Press, 2011).

[70] V. S. Shchesnovich and M. E. O. Bezerra. Collective phases of identical particles interfering on linear multiports. Phys. Rev. A 98, 033805 (2018).

[71] V. S. Shchesnovich and M. E. O. Bezerra. Distinguishability theory for time-resolved photodetection and boson sampling. Phys. Rev. A 101, 053853 (2020).

[72] Z. Puchala and J. A. Miszczak. Symbolic integration with respect to the Haar measure on the unitary groups. Bull. Polish Acad. Sci.: Techn. Sci. 65, 21-27 (2017).

[73] V. S. Shchesnovich. Asymptotic Gaussian law for noninteracting indistinguishable particles in random networks. Scientific Reports 7, 31 (2017).

[74] S. Rahimi-Keshari, A. P. Lund, and T. C. Ralph. What Can Quantum Optics Say about Computational Complexity Theory? Phys. Rev. Lett. 114, 060501 (2015).

[75] L. Chakhmakhchyan, N. J. Cerf, and R. García-Patrón. Quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices. Phys. Rev. A 96, 022329 (2017).

[76] A. Agresti and B. A. Coull. Approximate is Better than “Exact” for Interval Estimation of Binomial Proportions. The American Statistician 52, 119-126 (1998).

[77] N. N. Bogolyubov and N. N. Bogolyubov (Jr.), Introduction to Quantum Statistical Mechanics (Nauka, Moscow (1984)).

[78] M. N. Anderson, J. R. Ensher, M. R. Mathews, C. E. Wieman and E. A. Cornell. Observation of Bose-Einstein Condensation in a Dilute Atomic Vapor. Science 269, 198-201 (1995).

[79] K. B. Davis, M.-O. Mewes, M. R. Andrews, N. J. van Druten, D. S. Durfee, D. M. Kurn, and W. Ketterle. Bose-Einstein Condensation in a Gas of Sodium Atoms. Phys. Rev. Lett. 75, 3969 (1995).

[80] L. P. Pitaevskii. Vortex lines in an imperfect Bose gas. Soviet Phys. JETP 13, 451-454 (1961).

[81] E. P. Gross. Structure of a quantized vortex in boson systems. Il Nuovo Cimento 20, 454-477 (1961).

[82] L. Takács. On the Method of Inclusion and Exclusion. J. of Amer. Stat. Assoc. 62, 102-113 (1967).

Cited by

[1] V. S. Shchesnovich, “Noise in boson sampling and the threshold of efficient classical simulatability”, Physical Review A 100 1, 012340 (2019).

[2] Jelmer J. Renema, “Marginal probabilities in boson samplers with arbitrary input states”, arXiv:2012.14917.

The above citations are from SAO/NASA ADS (last updated successfully 2021-03-29 16:03:58). 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-03-29 16:03:56: Could not fetch cited-by data for 10.22331/q-2021-03-29-423 from Crossref. This is normal if the DOI was registered recently.

Coinsmart. Beste Bitcoin-Börse in Europa

Continue Reading
Esports4 days ago

Free Fire World Series APK Download for Android

Esports2 days ago

C9 White Keiti Blackmail Scandal Explains Sudden Dismissal

Esports2 days ago

Overwatch League 2021 Day 1 Recap

Esports4 days ago

Dota 2: Top Mid Heroes of Patch 7.29

Esports2 days ago

Fortnite: Epic Vaults Rocket Launchers, Cuddlefish & Explosive Bows From Competitive

Esports3 days ago

Don’t Miss Out on the Rogue Energy x Esports Talk Giveaway!

Esports4 days ago

Capcom Reveals Ransomware Hack Came from Old VPN

Esports3 days ago

Fortnite: DreamHack Cash Cup Extra Europe & NA East Results

Esports2 days ago

Gamers Club and Riot Games Organize Women’s Valorant Circuit in Latin America

Esports4 days ago

PSA: CSGO Fans Beware, Unfixed Steam Invite Hack Could Take Over Your PC.

Blockchain3 days ago

CoinSmart Appoints Joe Tosti as Chief Compliance Officer

Fintech4 days ago

FinSS and Salt Edge partner for CDR Compliance solution in Australia

Blockchain4 days ago

Bitfinex-Hacker versenden BTC im Wert von 750 Millionen USD

Blockchain5 days ago

Tech firm unveils Australian first initiative to help charities access blockchain funding

Blockchain3 days ago

April Continuum Blockchain Legislation Summit ContinuumBlockLegs

Esports4 days ago

AI-Driven Overwatch Power Rankings Coming From IBM

Esports4 days ago

COD Mobile Season 3 Tokyo Escape

Esports3 days ago

2021 Call of Duty Mobile World Championship Announced

Fintech3 days ago

Mambu research reveals global consumers are hesitant to use Open Banking

Blockchain2 days ago

15. BNB Burn: Binance zerstört Coins im Wert von 600 Mio. USD