Connect with us

Quantum

Deep tech VCs on what they view as some of the most impactful young startups right now

Published

on

During this week’s Democratic debate, there was a lot of talk, unsurprisingly, about ensuring the future of this country’s children and grandchildren. Climate change was of particular interest to billionaire Tom Steyer, who said repeatedly that addressing it would be his top priority were he elected U.S. president.

As it happens, earlier the same day, we’d spent time on the phone with two venture capitalists who think of almost nothing else every day. The reason: they both invest in so-called deep tech, and they meet routinely with startups whose central focus is on making the world habitable for generations of people to come — as well as trying to produce outsize financial returns, of course.

The two VCs with whom we talked know each other well. Siraj Khaliq is a partner at the global venture firm Atomico, where he tries to find world-changing startups that are enabled by machine learning, AI, and computer vision. He has strong experience in the area, having cofounded The Climate Corporation back in 2006, a company that helps farmers optimize crop yield and that was acquired by Monsanto in 2013 for roughly $1 billion.

Seth Bannon is meanwhile a founding partner of Fifty Years, a nearly five-year-old, San Francisco-based seed-stage fund whose stated ambition is backing founders who want to solve the world’s biggest problems. The investors’ interests overlap so much that Khaliq is also one of Fifty Years’s investors.

From both, we wanted to know which companies or trends are capturing their imagination and, in some cases, their investment dollars. Following are excerpts from our extended conversation earlier this week. (We thought it was interesting; hopefully you will, too.)

TC: Seth, how would you describe what you’re looking to fund at your firm?

SB: There’s a Winston Churchill essay [penned nearly 100 years ago] called “Fifty Years Hence” that describes what we do. He predicts genomic engineering, synthetic biology, growing meat without animals, nuclear power, satellite telephony.  Churchill also notes that because tech changes so quickly that it’s important that technologists take a principled approach to their work. [Inspired by him] we’re backing founders who can make a ton of money while doing good and focusing on health, disease, the climate crisis . . .

TC: What does that mean exactly? Are you investing in software?

SB: We’re not so enthusiastic about pure software because it’s been so abstracted away that it’s become a commodity. High school students can now build an app, which is great, but it also means that competitive pressures are very high. There are a thousand funds focused on software seed investing. Fortunately, you can now launch a synthetic biology startup with seed funding, and that wasn’t possible 10 years ago. There are a lot of infrastructural advancements happening that makes [deep tech investing even with smaller checks] interesting.

TC: Siraj, you also invest exclusively on frontier, or deep tech, at Atomico . What’s your approach to funding startups?

SK: We do Series A [deals] onward and don’t do seed stage. We primarily focus on Europe. But there’s lot of common thinking between us and Seth. As a fund, we’re looking for big problems that change the world, sometimes at companies that won’t necessarily be big in five years but if you look out 10 years could be necessary for humanity. So we’re trying to anticipate all of these big trends and focus on three or four theses a year and talk as much as we can with academics and other experts to understand what’s going on. Founders then know we have an informed view.

Last year, we focused on synthetic biology, which is a becoming so broad a category that it’s time to start subdividing it. We were also doing AI-based drug discovery and quantum computing and we started to spend some time on energy as well. We also [continued an earlier focus on ] the future of manufacturing and industry. We see a number of trends that make [the latter] attractive, especially in Europe where manufacturing hasn’t yet been digitized.

TC: Seth, you mentioned synthetic biology infrastructure. Can you elaborate on what you’re seeing that’s interesting on this front?

SB: You’ve maybe heard of directed evolution, technology that allows biologists to use the power of evolution to get microbes or other biological machines to do what they want them to do that would have been impossible before. [Editor’s note: here, Bannon talks a bit about Frances Arnold, the Nobel Prize-winning chemist who was awarded the honor in 2018 for developing the technique.]

So we’re excited to back [related] startups. One, Solugen, enzymatically makes industrial chemicals [by combining genetically modified enzymes with organic compounds, like plant sugars]. Hydrogen peroxide is a $6 billion dollar industry, and it’s currently made through a petroleum-based process in seven-football-field-long production plants that sometimes explode and kill people.

TC: Is this then akin to Zymergen, which develops molecules in order to create unique specialty materials?

SB: Zymergen mainly works as a kind of consultant to help companies engineer strains that they want. Solugen is a vertically integrated chemicals company, so it [creates its formulations], then sells directly into industry.

TC: How does this relate to new architectures?

SB: The way to think about it is that there’s a bunch of application-level companies, but as synthetic biology companies start to take off, there’s a bunch of emerging infrastructure layer companies. One of these is Ansa Biotechnologies, which has a fully enzymatic process for writing DNA. Like Twist, which went public, they make DNA to sell to customers in the biotech industry. But whereas Twist is using a chemical process to make DNA, Ansa’s approach is fully enzymatic. [Editor’s note: More on the competition in this emerging space here.]

Also, if you look at plant-based alternatives to meat, they’re more sustainable but also far more expensive than traditional beef. Why is that? Well plant-based chicken is more expensive because the processing infrastructure being used is more than 10 years behind real chicken processing, where you’ll see robot arms that cut up chicken so efficiently that it looks like a Tesla factory.

[Alternative meat] companies are basically using these extruders built in the ’70s because the industry has been so small, and that’s because there’s been a lot of skepticism from the investment community in these companies. Or there was. The performance of Beyond Meat’s IPO ended it. Now there’s a rush of founders and dollars into that space, and whenever you have a space where the core infrastructure has been neglected, there’s opportunity. A former mechanical engineer with Boeing has started a company, Rebellyous Foods, to basically build the AWS for the plant-based food industry, for example. She’s using [the machines she’s building] to sell plant-based chicken nuggets, [but that’s the longer-term plan].

TC: Siraj, you say last year you started to spend time on energy. What’s interesting to you as it relates to energy?

SK: There’s been some improvement in how we capture emissions, but [carbon emissions] are still very deleterious to our health and the planet’s health, and there are a few areas to think about [to address the problem]. Helping people measure and control their consumption is one approach, but also we think about how to produce new energy, which is a shift we [meaning mankind] need to undertake. The challenge [in making that shift] is often [capital expenditures]. It’s hard for venture investors to back companies that are [building nuclear reactors], which makes government grants the best choice for early innovation oftentimes. There is one company, Seaborg, that has figured out a clever reactor. It’s not a portfolio company but it’s [compelling].

SB: We also really like what Seaborg is doing. These [fourth generation] nuclear companies have a whole host of approaches that allow for smaller, safer reactors that you wouldn’t mind having in your backyard. But Siraj put his finger on it: as an early-stage deep tech investor, we have to consider the capital plan of a company, and if it needs to raise billions of dollars, early investors will get really diluted, so early-stage venture just isn’t the best fit.

TC: There are other areas you like, though, because costs have fallen so much.

SB: Yes. Satellite telephony used to be one of those areas. Some of the satellites in space right now cost $350 million [to launch] and took three to four years to build, which would be really hard for any early-stage investor to fund. But now, a new generation of companies is building satellites for one-tenth of the cost in months, not years. That’s a game changer. They can iterate faster. They can build a better product. They don’t have to raise equity to build and launch either; they can raise from a debt financier [from whom they can] borrow money and pay it back over time. That model isn’t available to a company like Uber or Lyft, because those companies can’t say, ‘X is going to cost us Y dollars and it will pay back Z over time.’

TC: What of concerns that all these cheap satellites are going to clog up the sky pretty quickly?

SB: It’s a real concern. Most [of today’s satellites] are low earth satellites, and the closer to the earth they are, the brighter they are; they reflect the sun more, the more satellites we’re seeing instead of stars. I do think it’s incumbent on all of these companies to think about how they are contributing to the future of humanity. But when you connect the unconnected, educational outcomes improve, health improves, inequality decreases, and the stability of governments improves, so maybe the developed world needs to sacrifice a bit. I think that’s a reasonable tradeoff. If on the other hand, we’re putting up satellites to help people buy more crap . . .

TC: It’s like the argument for self-driving cars in a way. Life becomes more efficient, but they’ll require far more energy generation, for example. There are always second-order consequences.

SK: But think of how many people are killed in driving accidents, versus terrorist attacks. Humans have many great qualities, but being able to drive a lethal machine consistently isn’t one of them. So when we take that into perspective, it’s really important that we build autonomous vehicles.

You [voice] a legitimate concern, and often when there are step changes, there are discontinuities along the way that lead to side effects that aren’t great. That comes down to several things. First, infrastructure will have to keep up. We’ll also have to create regulations that don’t lead to the worst outcomes. One our investments, Lilium in Munich, has built an entirely electric air taxi service that’s built on vertical takeoff. It’s nimble. It’s quiet enough to operate in city environments.

On roads, cars are constrained by 2D terrain and buildings, but [in the air] if you can do dynamic air traffic control, it opens up far much efficient transport. If you can get from downtown London to Heathrow [airport] in five minutes versus 50 minutes in a Tesla? That’s far more energy efficient.

Read more: https://techcrunch.com/2020/01/17/deep-tech-vcs-on-what-they-view-as-some-of-the-most-impactful-young-startups-right-now/

Quantum

Sense, sensibility, and superconductors

Published

on

Jonathan Monroe disagreed with his PhD supervisor—with respect. They needed to measure a superconducting qubit, a tiny circuit in which current can flow forever. The qubit emits light, which carries information about the qubit’s state. Jonathan and Kater intensify the light using an amplifier. They’d fabricated many amplifiers, but none had worked. Jonathan suggested changing their strategy—with a politeness to which Emily Post couldn’t have objected. Jonathan’s supervisor, Kater Murch, suggested repeating the protocol they’d performed many times.

“That’s the definition of insanity,” Kater admitted, “but I think experiment needs to involve some of that.”

I watched the exchange via Skype, with more interest than I’d have watched the Oscars with. Someday, I hope, I’ll be able to weigh in on such a debate, despite working as a theorist. Someday, I’ll have partnered with enough experimentalists to develop insight.

I’m partnering with Jonathan and Kater on an experiment that coauthors and I proposed in a paper blogged about here. The experiment centers on an uncertainty relation, an inequality of the sort immortalized by Werner Heisenberg in 1927. Uncertainty relations imply that, if you measure a quantum particle’s position, the particle’s momentum ceases to have a well-defined value. If you measure the momentum, the particle ceases to have a well-defined position. Our uncertainty relation involves weak measurements. Weakly measuring a particle’s position doesn’t disturb the momentum much and vice versa. We can interpret the uncertainty in information-processing terms, because we cast the inequality in terms of entropies. Entropies, described here, are functions that quantify how efficiently we can process information, such as by compressing data. Jonathan and Kater are checking our inequality, and exploring its implications, with a superconducting qubit.

With chip

I had too little experience to side with Jonathan or with Kater. So I watched, and I contemplated how their opinions would sound if expressed about theory. Do I try one strategy again and again, hoping to change my results without changing my approach? 

At the Perimeter Institute for Theoretical Physics, Masters students had to swallow half-a-year of course material in weeks. I questioned whether I’d ever understand some of the material. But some of that material resurfaced during my PhD. Again, I attended lectures about Einstein’s theory of general relativity. Again, I worked problems about observers in free-fall. Again, I calculated covariant derivatives. The material sank in. I decided never to question, again, whether I could understand a concept. I might not understand a concept today, or tomorrow, or next week. But if I dedicate enough time and effort, I chose to believe, I’ll learn.

My decision rested on experience and on classes, taught by educational psychologists, that I’d taken in college. I’d studied how brains change during learning and how breaks enhance the changes. Sense, I thought, underlay my decision—though expecting outcomes to change, while strategies remain static, sounds insane.

Old cover

Does sense underlie Kater’s suggestion, likened to insanity, to keep fabricating amplifiers as before? He’s expressed cynicism many times during our collaboration: Experiment needs to involve some insanity. The experiment probably won’t work for a long time. Plenty more things will likely break. 

Jonathan and I agree with him. Experiments have a reputation for breaking, and Kater has a reputation for knowing experiments. Yet Jonathan—with professionalism and politeness—remains optimistic that other methods will prevail, that we’ll meet our goals early. I hope that Jonathan remains optimistic, and I fancy that Kater hopes, too. He prophesies gloom with a quarter of a smile, and his record speaks against him: A few months ago, I met a theorist who’d collaborated with Kater years before. The theorist marveled at the speed with which Kater had operated. A theorist would propose an experiment, and boom—the proposal would work.

Sea monsters

Perhaps luck smiled upon the implementation. But luck dovetails with the sense that underlies Kater’s opinion: Experiments involve factors that you can’t control. Implement a protocol once, and it might fail because the temperature has risen too high. Implement the protocol again, and it might fail because a truck drove by your building, vibrating the tabletop. Implement the protocol again, and it might fail because you bumped into a knob. Implement the protocol a fourth time, and it might succeed. If you repeat a protocol many times, your environment might change, changing your results.

Sense underlies also Jonathan’s objections to Kater’s opinions. We boost our chances of succeeding if we keep trying. We derive energy to keep trying from creativity and optimism. So rebelling against our PhD supervisors’ sense is sensible. I wondered, watching the Skype conversation, whether Kater the student had objected to prophesies of doom as Jonathan did. Kater exudes the soberness of a tenured professor but the irreverence of a Californian who wears his hair slightly long and who tattooed his wedding band on. Science thrives on the soberness and the irreverence.

Green cover

Who won Jonathan and Kater’s argument? Both, I think. Last week, they reported having fabricated amplifiers that work. The lab followed a protocol similar to their old one, but with more conscientiousness. 

I’m looking forward to watching who wins the debate about how long the rest of the experiment takes. Either way, check out Jonathan’s talk about our experiment if you attend the American Physical Society’s March Meeting. Jonathan will speak on Thursday, March 5, at 12:03, in room 106. Also, keep an eye out for our paper—which will debut once Jonathan coaxes the amplifier into synching with his qubit.

Source: https://quantumfrontiers.com/2020/02/23/sense-sensibility-and-superconductors/

Continue Reading

Quantum

Approximating Hamiltonian dynamics with the Nyström method

Published

on

Alessandro Rudi1, Leonard Wossnig2,3, Carlo Ciliberto2, Andrea Rocchetto2,4,5, Massimiliano Pontil6, and Simone Severini2

1INRIA – Sierra project team, Paris, France
2Department of Computer Science, University College London, London, United Kingdom
3Rahko Ltd., London, United Kingdom
4Department of Computer Science, University of Texas at Austin, Austin, United States
5Department of Computer Science, University of Oxford, Oxford, United Kingdom
6Computational Statistics and Machine Learning, IIT, Genoa, Italy

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

Abstract

Simulating the time-evolution of quantum mechanical systems is BQP-hard and expected to be one of the foremost applications of quantum computers. We consider classical algorithms for the approximation of Hamiltonian dynamics using subsampling methods from randomized numerical linear algebra. We derive a simulation technique whose runtime scales polynomially in the number of qubits and the Frobenius norm of the Hamiltonian. As an immediate application, we show that sample based quantum simulation, a type of evolution where the Hamiltonian is a density matrix, can be efficiently classically simulated under specific structural conditions. Our main technical contribution is a randomized algorithm for approximating Hermitian matrix exponentials. The proof leverages a low-rank, symmetric approximation via the Nyström method. Our results suggest that under strong sampling assumptions there exist classical poly-logarithmic time simulations of quantum computations.

► BibTeX data

► References

[1] Aharonov and Ta-Shma “Adiabatic Quantum State Generation and Statistical Zero Knowledge” Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing 20-29 (2003).
https:/​/​doi.org/​10.1145/​780542.780546

[2] Aleksandrov and Peller “Operator Lipschitz functions” Russian Mathematical Surveys 71, 605 (2016).
https:/​/​doi.org/​10.1070/​RM9729

[3] Belabbas and Wolfe “Fast low-rank approximation for covariance matrices” 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2007. 293-296 (2007).
https:/​/​doi.org/​10.1109/​CAMSAP.2007.4498023

[4] Belabbas and Wolfe “On sparse representations of linear operators and the approximation of matrix products” 42nd Annual Conference on Information Sciences and Systems 258-263 (2008).
https:/​/​doi.org/​10.1109/​CISS.2008.4558532

[5] Berry, Childs, and Kothari, “Hamiltonian simulation with nearly optimal dependence on all parameters” IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) 792-809 (2015).
https:/​/​doi.org/​10.1109/​FOCS.2015.54

[6] Biamonte, Wittek, Pancotti, Rebentrost, Wiebe, and Lloyd, “Quantum machine learning” Nature 549, 195 (2017).
https:/​/​doi.org/​10.1038/​nature23474

[7] Bravyi, Browne, Calpin, Campbell, Gosset, and Howard, “Simulation of quantum circuits by low-rank stabilizer decompositions” arXiv preprint arXiv:1808.00128 (2018).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[8] Chia, Gilyén, Li, Lin, Tang, and Wang, “Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning” arXiv preprint arXiv:1910.06151 (2019).

[9] Childs and Kothari “Simulating Sparse Hamiltonians with Star Decompositions” Proceedings of the 5th Conference on Theory of Quantum Computation, Communication, and Cryptography 94-103 (2011).
https:/​/​doi.org/​10.1007/​978-3-642-18073-6_8

[10] Childs and Wiebe “Hamiltonian Simulation Using Linear Combinations of Unitary Operations” Quantum Info. Comput. 12, 901-924 (2012).
https:/​/​doi.org/​10.5555/​2481569.2481570

[11] Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman, “Exponential Algorithmic Speedup by a Quantum Walk” Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing 59-68 (2003).
https:/​/​doi.org/​10.1145/​780542.780552

[12] Ciliberto, Herbster, Ialongo, Pontil, Rocchetto, Severini, and Wossnig, “Quantum machine learning: a classical perspective” Proc. R. Soc. A 474, 20170551 (2018).
https:/​/​doi.org/​10.1098/​rspa.2017.0551

[13] Drineas, Kannan, and Mahoney, “Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication” SIAM Journal on Computing 36, 132-157 (2006).
https:/​/​doi.org/​10.1137/​S0097539704442684

[14] Drineas, Kannan, and Mahoney, “Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix” SIAM Journal on computing 36, 158-183 (2006).
https:/​/​doi.org/​10.1137/​S0097539704442696

[15] Drineas and Mahoney “On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning” J. Mach. Learn. Res. 6, 2153-2175 (2005).
https:/​/​doi.org/​10.5555/​1046920.1194916

[16] Drineas and Mahoney “Lectures on randomized numerical linear algebra” The Mathematics of Data 25, 1 (2018).

[17] Drineas, Mahoney, Muthukrishnan, and Sarlós, “Faster Least Squares Approximation” Numer. Math. 117, 219-249 (2011).
https:/​/​doi.org/​10.1007/​s00211-010-0331-6

[18] Fowlkes, Belongie, Chung, and Malik, “Spectral Grouping Using the Nyström Method” IEEE Trans. Pattern Anal. Mach. Intell. 26, 214-225 (2004).
https:/​/​doi.org/​10.1109/​TPAMI.2004.1262185

[19] Frieze, Kannan, and Vempala, “Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations” J. ACM 51, 1025-1041 (2004).
https:/​/​doi.org/​10.1145/​1039488.1039494

[20] Haegeman, Cirac, Osborne, Pižorn, Verschelde, and Verstraete, “Time-dependent variational principle for quantum lattices” Physical review letters 107, 070601 (2011).
https:/​/​doi.org/​10.1103/​PhysRevLett.107.070601

[21] Higham “The Scaling and Squaring Method for the Matrix Exponential Revisited” SIAM J. Matrix Anal. Appl. 26, 1179-1193 (2005).
https:/​/​doi.org/​10.1137/​04061101X

[22] Higham “The Scaling and Squaring Method for the Matrix Exponential Revisited” SIAM Rev. 51, 747-764 (2009).
https:/​/​doi.org/​10.1137/​090768539

[23] Hsu “Weighted sampling of outer products” arXiv preprint arXiv: 1410.4429 (2014).

[24] Huang, Newman, and Szegedy, “Explicit lower bounds on strong quantum simulation” arXiv preprint arXiv:1804.10368 (2018).

[25] Jónsson, Bauer, and Carleo, “Neural-network states for the classical simulation of quantum computing” arXiv preprint arXiv:1808.05232 (2018).

[26] Kerenidis and Prakash “Quantum recommendation systems” arXiv preprint arXiv:1603.08675 (2016).

[27] Kimmel, Lin, Low, Ozols, and Yoder, “Hamiltonian simulation with optimal sample complexity” npj Quantum Information 3, 13 (2017).
https:/​/​doi.org/​10.1038/​s41534-017-0013-7

[28] Kumar, Mohri, and Talwalkar, “On Sampling-Based Approximate Spectral Decomposition” Proceedings of the 26th Annual International Conference on Machine Learning 553-560 (2009).
https:/​/​doi.org/​10.1145/​1553374.1553446

[29] Kumar, Mohri, and Talwalkar, “Sampling methods for the Nyström method” Journal of Machine Learning Research 13, 981-1006 (2012).
https:/​/​doi.org/​10.5555/​2188385.2343678

[30] Li, Kwok, and Lu, “Making Large-Scale Nyström Approximation Possible” Proceedings of the 27th International Conference on International Conference on Machine Learning 631-638 (2010).
https:/​/​doi.org/​10.5555/​3104322.3104403

[31] Lloyd “Universal Quantum Simulators” Science 273, 1073-1078 (1996).
https:/​/​doi.org/​10.1126/​science.273.5278.1073

[32] Lloyd, Mohseni, and Rebentrost, “Quantum principal component analysis” Nature Physics 10, 631 (2014).
https:/​/​doi.org/​10.1038/​nphys3029

[33] Lowand Chuang “Hamiltonian Simulation by Uniform Spectral Amplification” arXiv preprint arXiv:1707.05391 (2017).

[34] Mackey, Talwalkar, and Jordan, “Divide-and-Conquer Matrix Factorization” Proceedings of the 24th International Conference on Neural Information Processing Systems 1134-1142 (2011).
https:/​/​doi.org/​10.5555/​2986459.2986586

[35] Mahoney “Randomized algorithms for matrices and data” Foundations and Trends® 3, 123-224 (2011).
https:/​/​doi.org/​10.1561/​2200000035

[36] Mathias “Approximation of matrix-valued functions” SIAM journal on matrix analysis and applications 14, 1061-1063 (1993).
https:/​/​doi.org/​10.1137/​0614070

[37] Al-Mohyand Higham “A new scaling and squaring algorithm for the matrix exponential” SIAM Journal on Matrix Analysis and Applications 31, 970-989 (2009).
https:/​/​doi.org/​10.1137/​09074721X

[38] Al-Mohyand Higham “Computing the action of the matrix exponential, with an application to exponential integrators” SIAM journal on scientific computing 33, 488-511 (2011).
https:/​/​doi.org/​10.1137/​100788860

[39] Nakamoto “A norm inequality for Hermitian operators” The American mathematical monthly 110, 238 (2003).
https:/​/​doi.org/​10.1080/​00029890.2003.11919961

[40] Nyström “Über die praktische Auflösung von Integralgleichungen mit Anwendungen auf Randwertaufgaben” Acta Mathematica 54, 185-204 (1930).
https:/​/​doi.org/​10.1007/​BF02547521

[41] Orecchia, Sachdeva, and Vishnoi, “Approximating the Exponential, the Lanczos Method and an Õ(m)-Time Spectral Algorithm for Balanced Separator” Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing 1141-1160 (2012).
https:/​/​doi.org/​10.1145/​2213977.2214080

[42] Orús “A practical introduction to tensor networks: Matrix product states and projected entangled pair states” Annals of Physics 349, 117-158 (2014).
https:/​/​doi.org/​10.1016/​j.aop.2014.06.013

[43] Rebentrost, Mohseni, and Lloyd, “Quantum support vector machine for big data classification” Physical review letters 113, 130503 (2014).
https:/​/​doi.org/​10.1103/​PhysRevLett.113.130503

[44] Rebentrost, Schuld, Wossnig, Petruccione, and Lloyd, “Quantum gradient descent and Newton’s method for constrained polynomial optimization” New Journal of Physics 21, 073023 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​ab2a9e

[45] Rudi, Camoriano, and Rosasco, “Less is More: Nyström Computational Regularization” Proceedings of the 28th International Conference on Neural Information Processing Systems – Volume 1 1657-1665 (2015).
https:/​/​doi.org/​10.5555/​2969239.2969424

[46] Rudi, Camoriano, and Rosasco, “Less is More: Nyström Computational Regularization” arXiv preprint arXiv:1507.04717 (2015).

[47] Schuld, Sinayskiy, and Petruccione, “Prediction by linear regression on a quantum computer” Physical Review A 94, 022342 (2016).
https:/​/​doi.org/​10.1103/​PhysRevA.94.022342

[48] Schwarz and Nest “Simulating quantum circuits with sparse output distributions” arXiv preprint arXiv:1310.6749 (2013).

[49] Spielman and Teng “Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems” Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing 81-90 (2004).
https:/​/​doi.org/​10.1145/​1007352.1007372

[50] Spielman and Teng “Spectral sparsification of graphs” SIAM Journal on Computing 40, 981-1025 (2011).
https:/​/​doi.org/​10.1137/​08074489X

[51] Suzuki “Generalized Trotter’s formula and systematic approximants of exponential operators and inner derivations with applications to many-body problems” Communications in Mathematical Physics 51, 183-190 (1976).
https:/​/​doi.org/​10.1007/​BF01609348

[52] Talwalkar, Kumar, and Rowley, “Large-scale manifold learning” IEEE Conference on Computer Vision and Pattern Recognition 1-8 (2008).
https:/​/​doi.org/​10.1109/​CVPR.2008.4587670

[53] Tang “A Quantum-Inspired Classical Algorithm for Recommendation Systems” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing 217-228 (2019).
https:/​/​doi.org/​10.1145/​3313276.3316310

[54] Tropp “User-Friendly Tail Bounds for Sums of Random Matrices” Found. Comput. Math. 12, 389-434 (2012).
https:/​/​doi.org/​10.1007/​s10208-011-9099-z

[55] Trotter “On the product of semi-groups of operators” Proceedings of the American Mathematical Society 10, 545-551 (1959).
https:/​/​doi.org/​10.1090/​S0002-9939-1959-0108732-6

[56] Van Den Nest “Classical simulation of quantum computation, the Gottesman” Quantum Information & Computation 10, 258-271 (2010).
https:/​/​doi.org/​10.5555/​2011350.2011356

[57] Verstraete, Garcia-Ripoll, and Cirac, “Matrix product density operators: Simulation of finite-temperature and dissipative systems” Physical review letters 93, 207204 (2004).
https:/​/​doi.org/​10.1103/​PhysRevLett.93.207204

[58] Verstraete, Murg, and Cirac, “Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems” Advances in Physics 57, 143-224 (2008).
https:/​/​doi.org/​10.1063/​1.5026985

[59] Vidal “Efficient Simulation of One-Dimensional Quantum Many-Body Systems” Phys. Rev. Lett. 93, 040502 (2004).
https:/​/​doi.org/​10.1103/​PhysRevLett.93.040502

[60] Williams and Seeger “Using the Nyström Method to Speed Up Kernel Machines” Advances in Neural Information Processing Systems 13 682-688 (2001).
https:/​/​doi.org/​10.5555/​3008751.3008847

[61] Williams, Rasmussen, Schwaighofer, and Tresp, “Observations on the Nyström Method for Gaussian Process Prediction” report (2002).

[62] Woodruff “Sketching as a tool for numerical linear algebra” Foundations and Trends® 10, 1-157 (2014).
https:/​/​doi.org/​10.1561/​0400000060

[63] Zhang and Kwok “Clustered Nyström method for large scale manifold learning and dimension reduction” IEEE Transactions on Neural Networks 21, 1576-1587 (2010).
https:/​/​doi.org/​10.1109/​TNN.2010.2064786

[64] Zhang, Tsang, and Kwok, “Improved Nyström Low-Rank Approximation and Error Analysis” Proceedings of the 25th International Conference on Machine Learning 1232-1239 (2008).
https:/​/​doi.org/​10.1145/​1390156.1390311

Cited by

[1] Ewin Tang, “Quantum-inspired classical algorithms for principal component analysis and supervised clustering”, arXiv:1811.00414.

[2] Juan A. Acebron, “A Monte Carlo method for computing the action of a matrix exponential on a vector”, arXiv:1904.12759.

[3] Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang, “Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning”, arXiv:1910.06151.

The above citations are from SAO/NASA ADS (last updated successfully 2020-02-20 15:40:36). 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 2020-02-20 15:40:34: Could not fetch cited-by data for 10.22331/q-2020-02-20-234 from Crossref. This is normal if the DOI was registered recently.

Source: https://quantum-journal.org/papers/q-2020-02-20-234/

Continue Reading

Quantum

Extension of the Alberti-Ulhmann criterion beyond qubit dichotomies

Published

on

Michele Dall’Arno1,2, Francesco Buscemi3, and Valerio Scarani1,4

1Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, 117543, Singapore
2Faculty of Education and Integrated Arts and Sciences, Waseda University, 1-6-1 Nishiwaseda, Shinjuku-ku, Tokyo 169-8050, Japan
3Graduate School of Informatics, Nagoya University, Chikusa-ku, 464-8601 Nagoya, Japan
4Department of Physics, National University of Singapore, 2 Science Drive 3, 117542, Singapore

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

Abstract

The Alberti-Ulhmann criterion states that any given qubit dichotomy can be transformed into any other given qubit dichotomy by a quantum channel if and only if the testing region of the former dichotomy includes the testing region of the latter dichotomy. Here, we generalize the Alberti-Ulhmann criterion to the case of arbitrary number of qubit or qutrit states. We also derive an analogous result for the case of qubit or qutrit measurements with arbitrary number of elements. We demonstrate the possibility of applying our criterion in a semi-device independent way.

As soon as entanglement was recognised as a resource, theorists started studying the interconversions properties of this resource. The most famous such question is: given N copies of a state rho, how many copies N’ of the state rho’ can one obtain with local operations and classical communication? This question led to the definition of entanglement of formation (rho is the maximally entangled state), of distillation (rho’ is the maximally entangled state), to the discovery of inequivalent entanglement classes for multipartite systems… The amount of literature on this question is enormous.

Very little however is known about a different problem, the one we consider here. The question is whether a pair of states (rho,sigma) can be converted into another pair of states (rho’,sigma’). This question does not need to refer to entanglement: in fact, here we don’t consider composite systems, and consequently we don’t restrict the possible operations. A very simple answer would be the one that holds for classical probability distributions: Pair 1 can be converted into Pair 2, if all the statistics that can be observed with Pair 2 can also be observed with Pair 1. This conveys the idea that Pair 1 can do all that Pair 2 can do, and possibly more. This answer holds for two states of qubits (Alberti and Uhlmann, 1980), but counter-examples are known already when Pair 1 comprises qutrit states. In this paper, we prove that the classical-like characterisation still holds when Pair 1 is generalized to any family of qubit states, as soon as they can all be expressed with real coefficients, and Pair 2 is generalized to any family of qubit or, under certain hypotheses, qutrit, states. We also exploit a duality between states and measurements to present a similar characterisation of measurement devices.

► BibTeX data

► References

[1] J. M. Renes, Relative submajorization and its use in quantum resource theories, J. Math. Phys. 57, 122202 (2016).
https:/​/​doi.org/​10.1063/​1.4972295

[2] D. Blackwell, Equivalent Comparisons of Experiments, Ann. Math. Statist. 24, 265 (1953).
https:/​/​doi.org/​10.1214/​aoms/​1177729032

[3] E. N. Torgersen, Comparison of statistical experiments, (Cambridge University Press, 1991).
https:/​/​doi.org/​10.1017/​CBO9780511666353

[4] E. N. Torgersen, Comparison of experiments when the parameter space is finite, Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 16, 219 (1970).
https:/​/​doi.org/​10.1007/​BF00534598

[5] K. Matsumoto, An example of a quantum statistical model which cannot be mapped to a less informative one by any trace preserving positive map, arXiv:1409.5658.
arXiv:1409.5658

[6] K. Matsumoto, On the condition of conversion of classical probability distribution families into quantum families, arXiv:1412.3680 (2014).
arXiv:1412.3680

[7] F. Buscemi and G. Gour, Quantum Relative Lorenz Curves, Phys. Rev. A 95, 012110 (2017).
https:/​/​doi.org/​10.1103/​PhysRevA.95.012110

[8] D. Reeb, M. J. Kastoryano, and M. M. Wolf, Hilbert’s projective metric in quantum information theory, J. Math. Phys. 52, 082201 (2011).
https:/​/​doi.org/​10.1063/​1.3615729

[9] A. Jenčová, Comparison of Quantum Binary Experiments, Reports on Mathematical Physics 70, 237 (2012).
https:/​/​doi.org/​10.1016/​S0034-4877(12)60043-3

[10] F. Buscemi, Comparison of Quantum Statistical Models: Equivalent Conditions for Sufficiency, Communications in Mathematical Physics 310, 625 (2012).
https:/​/​doi.org/​10.1007/​s00220-012-1421-3

[11] K. Matsumoto, A quantum version of randomization criterion, arXiv: 1012.2650 (2010).
arXiv:1012.2650

[12] A. Jenčová, Comparison of quantum channels and statistical experiments, in 2016 IEEE International Symposium on Information Theory (ISIT), 2249 (2016).
arXiv:1512.07016

[13] A. W. Marshall, I. Olkin, and B. C. Arnold, Inequalities: Theory of Majorization and Its Applications (Springer, 2011).
https:/​/​doi.org/​10.1007/​978-0-387-68276-1

[14] K. Matsumoto, Reverse Test and Characterization of Quantum Relative Entropy, arXiv:1010.1030.
arXiv:1010.1030

[15] F. Buscemi, D. Sutter, and M. Tomamichel, An information-theoretic treatment of quantum dichotomies, arXiv:1907.08539.
arXiv:1907.08539
https:/​/​quantum-journal.org/​papers/​q-2019-12-09-209/​

[16] X. Wang and M. M. Wilde, “Resource theory of asymmetric distinguishability”, arXiv:1905.11629 (2019).
https:/​/​doi.org/​10.1103/​PhysRevResearch.1.033170
arXiv:1905.11629

[17] P. M. Alberti and A. Uhlmann, A problem relating to positive linear maps on matrix algebras, Reports on Mathematical Physics 18, 163 (1980).
https:/​/​doi.org/​10.1016/​0034-4877(80)90083-X

[18] M. Dall’Arno, S. Brandsen, F. Buscemi, and V. Vedral, Device-independent tests of quantum measurements, Phys. Rev. Lett. 118, 250501 (2017).
https:/​/​doi.org/​10.1103/​PhysRevLett.118.250501

[19] M. Dall’Arno, Device-independent tests of quantum states, Phys. Rev. A 99, 052353 (2019).
https:/​/​doi.org/​%20%2010.1103/​PhysRevA.99.052353

[20] M. Dall’Arno, F. Buscemi, A. Bisio, and A. Tosini, Data-driven inference, reconstruction, and observational completeness of quantum devices, arXiv:1812.08470.
arXiv:1812.08470

[21] F. Buscemi and M. Dall’Arno, Data-driven Inference of Physical Devices: Theory and Implementation, New J. Phys. 21, 113029 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​ab5003

[22] M. Dall’Arno, A. Ho, F. Buscemi, and V. Scarani, Data-driven inference and observational completeness of quantum devices, arXiv:1905.04895.
arXiv:1905.04895

[23] S. L. Woronowicz, Positive maps of low dimensional matrix algebras, Rep. Math. Phys. 10, 165 (1976).
https:/​/​doi.org/​10.1016/​0034-4877/​(76)90038-0

[24] M. M. Wilde, Quantum Information Theory, (Cambridge University Press, 2017).
https:/​/​doi.org/​10.1017/​CBO9781139525343

[25] F. Buscemi, G. M. D’Ariano, M. Keyl, P. Perinotti, and R. Werner, Clean Positive Operator Valued Measures, J. Math. Phys. 46, 082109 (2005).
https:/​/​doi.org/​10.1063/​1.2008996

[26] F. John, Extremum problems with inequalities as subsidiary conditions, in Studies and Essays Presented to R. Courant on his 60th Birthday, 187–204, (Interscience Publishers, New York, 1948).

[27] K. M. Ball, Ellipsoids of maximal volume in convex bodies, Geom. Dedicata. 41, 241 (1992).
https:/​/​doi.org/​10.1007/​BF00182424

[28] Michael J. Todd, Minimum-Volume Ellipsoids: Theory and Algorithms, (Cornell University, 2016).
https:/​/​doi.org/​10.1137/​1.9781611974386

[29] S. Boyd and L. Vandenberghe, Convex Optimization, (Cambridge University Press, 2004).
https:/​/​doi.org/​10.1017/​CBO9780511804441

[30] G. M. D’Ariano, G. Chiribella, and P. Perinotti, Quantum Theory from First Principles: An Informational Approach (Cambridge University Press, 2017).
https:/​/​doi.org/​10.1017/​9781107338340

Cited by

Could not fetch Crossref cited-by data during last attempt 2020-02-20 14:17:42: Could not fetch cited-by data for 10.22331/q-2020-02-20-233 from Crossref. This is normal if the DOI was registered recently. On SAO/NASA ADS no data on citing works was found (last attempt 2020-02-20 14:17:43).

Source: https://quantum-journal.org/papers/q-2020-02-20-233/

Continue Reading

Trending