Connect with us


On the merits of flatworm reproduction



On my right sat a quantum engineer. She was facing a melanoma specialist who works at a medical school. Leftward of us sat a networks expert, a flatworm enthusiast, and a condensed-matter theorist.

Farther down sat a woman who slices up mouse brains. 

Welcome to “Coherent Spins in Biology,” a conference that took place at the University of California, Los Angeles (UCLA) this past December. Two southern Californians organized the workshop: Clarice Aiello heads UCLA’s Quantum Biology Tech lab. Thorsten Ritz, of the University of California, Irvine, cofounded a branch of quantum biology.

Clarice logo

Quantum biology served as the conference’s backdrop. According to conventional wisdom, quantum phenomena can’t influence biology significantly: Biological systems have high temperatures, many particles, and fluids. Quantum phenomena, such as entanglement (a relationship that quantum particles can share), die quickly under such conditions.

Yet perhaps some survive. Quantum biologists search for biological systems that might use quantum resources. Then, they model and measure the uses and resources. Three settings (at least) have held out promise during the past few decades: avian navigation, photosynthesis, and olfaction. You can read about them in this book, cowritten by a conference participant for the general public. I’ll give you a taste (or a possibly quantum smell?) by sketching the avian-navigation proposal, developed by Thorsten and colleagues.

Bird + flower

Birds migrate southward during the autumn and northward during the spring. How do they know where to fly? At least partially by sensing the Earth’s magnetic field, which leads compass needles to point northward. How do birds sense the field?

Possibly with a protein called “cryptochrome.” A photon (a particle of light) could knock an electron out of part of the protein and into another part. Each part would have one electron that lacked a partner. The electrons would share entanglement. One electron would interact with the Earth’s magnetic field differently than its partner, because its surroundings would differ. (Experts: The electrons would form a radical pair. One electron would neighbor different atoms than the other, so the electron would experience a different local magnetic field. The discrepancy would change the relative phase between the electrons’ spins.) The discrepancy could affect the rate at which the chemical system could undergo certain reactions. Which reactions occur could snowball into large and larger effects, eventually signaling the brain about where the bird should fly.

Angry bird

Quantum mechanics and life rank amongst the universe’s mysteries. How could a young researcher resist the combination? A postdoc warned me away, one lunchtime at the start of my PhD. Quantum biology had enjoyed attention several years earlier, he said, but noise the obscured experimental data. Controversy marred the field.

I ate lunch with that postdoc in 2013. Interest in quantum biology is reviving, as evidenced in the conference. Two reasons suggested themselves: new technologies and new research avenues. For example, Thorsten described the disabling and deletion of genes that code for cryptochrome. Such studies require years’ more work but might illuminate whether cryptochrome affects navigation.

Open door

The keynote speaker, Harvard’s Misha Lukin, illustrated new technologies and new research avenues. Misha’s lab has diamonds that contain quantum defects, which serve as artificial atoms. The defects sense tiny magnetic fields and temperatures. Misha’s group applies these quantum sensors to biology problems.

For example, different cells in an embryo divide at different times. Imagine reversing the order in which the cells divide. Would the reversal harm the organism? You could find out by manipulating the temperatures in different parts of the embryo: Temperature controls the rate at which cells divide.

Misha’s team injected nanoscale diamonds into a worm embryo. (See this paper for a related study.) The diamonds reported the temperature at various points in the worm. This information guided experimentalists who heated the embryo with lasers.

The manipulated embryos grew into fairly normal adults. But their cells, and their descendants’ cells, cycled through the stages of life slowly. This study exemplified, to me, one of the most meaningful opportunities for quantum physicists interested in biology: to develop technologies and analyses that can answer biology questions.


I mentioned, in an earlier blog post, another avenue emerging in quantum biology: Physicist Matthew Fisher proposed a mechanism by which entanglement might enhance coordinated neuron firing. My collaborator Elizabeth Crosson and I analyzed how the molecules in Matthew’s proposal—Posner clusters—could process quantum information. The field of Posner quantum biology had a population of about two, when Elizabeth and I entered, and I wondered whether anyone would join us.

The conference helped resolve my uncertainty. Three speakers (including me) presented work based on Matthew’s; two other participants were tilling the Posner soil; and another speaker mentioned Matthew’s proposal. The other two Posner talks related data from three experiments. The experimentalists haven’t finished their papers, so I won’t share details. But stay tuned.

Posner 2

Posner molecule (image by Swift et al.)

Clarice and Thorsten’s conference reminded me of a conference I’d participated in at the end of my PhD: Last month, I moonlighted as a quantum biologist. In 2017, I moonlighted as a quantum-gravity theorist. Two years earlier, I’d been dreaming about black holes and space-time. At UCLA, I was finishing the first paper I’ve coauthored with biophysicists. What a toolkit quantum information theory and thermodynamics provide, that it can unite such disparate fields. 

The contrast—on top of what I learned at UCLA—filled my mind for weeks. And reminded me of the description of asexual reproduction that we heard from the conference’s flatworm enthusiast. According to Western Michigan University’s Wendy Beane, a flatworm “glues its butt down, pops its head off, and grows a new one. Y’know. As one does.” 

I hope I never flinch from popping my head off and growing a new one—on my quantum-information-thermodynamics spine—whenever new science calls for figuring out.

With thanks to Clarice, Thorsten, and UCLA for their invitation and hospitality.



How a Space Engineer Made Her Own Rotary Cell Phone



Justine Haupt never expected that a project she’d been working on for the past three years would suddenly cause her website to crash. But when Haupt published photos and schematics for her handheld rotary cell phone yesterday, that’s exactly what happened.

Haupt, who works as an astronomy instrumentation engineer at Brookhaven National Laboratory in New York, detailed how she took the rotary mechanism from an old Trimline telephone, paired it with a microcontroller and an Adafruit Fona 3G cell transceiver, put it all into a 3D-printed casing, and built something that could replace her daily flip phone.

Correct: A flip phone. Haupt is firmly anti-smartphone, she told WIRED in an interview, and for a long time she’s used an LG flip phone for her basic mobile needs. But even that felt like too much, so Haupt’s goal with the rotary cell was two-pronged: She wanted to strip a mobile phone down to its absolute essentials, while giving her an even more legitimate excuse for not text messaging her friends. “The point isn't to be anachronistic,” Haupt wrote on her website. “It's to show that it's possible to have a perfectly usable phone that goes as far from having a touchscreen as I can imagine, and which in some ways may actually be more functional.”

In our interview, which has been edited for clarity and length, Haupt talks about tech products as novelties, the similarities between cellphone trends and ChapStick, and why she’s excited about our tech’s rapid release cycles, despite some obvious downsides to it.

Lauren Goode: Let’s talk about your background first. Can you tell me a little bit more about what you do at Brookhaven?

Justine Haupt: I’ve worked on mostly instrumentation development for cosmology and astronomy projects. For example, I've been working on a large ground-based survey telescope for dark energy and dark matter for the past 10 years; that's winding down. I’m working on a radio telescope now and and some other projects, including a possible NASA mission and a quantum information experiment, which is not astronomy-related but it's interesting so I've been getting more involved with that. So it’s, you know, basically building experimental hardware for those kinds of things.

LG: How much of your free time do you spend on your own experimental hardware?

The custom board Haupt created for her phone.

Illustration: Justine Haupt 

JH: It’s pretty hard actually, though I do make time for it. I'm also trying to start a company, so I reduced my time at Brookhaven to 80 percent so that I’d have an extra day a week to work on that. I'm pretty strict with myself about not taking too much work home with me.

LG: What kind of company are you trying to start?

JH: You know, it’s a shame because I was so surprised when this [rotary phone] went viral, I didn’t intend to do anything that would make that happen, I just put the thing up on my own website which I didn’t think anybody ever read, and then this happened. I would have made sure the website for my new company was up. My first product is basically a kind of two-channel brushless motor controller for domestic robots. And my next project will hopefully be an actual full-size domestic robot because robots are, you know—they’re awesome.

LG: You talk a little bit about this on your website, but why did you decide to make this rotary phone? What problem were you looking to solve?

JH: It’s funny, I usually love [having] problems to solve … But this wasn’t intended to be a product or an invention or anything like that. I just thought for a long time that rotary dials are so cool, they don’t have a use in modern society, and I’d love to make myself some device that uses it for data entry. And then I thought, Well, it might as well be a phone. And if I'm gonna do this, it should be something that I could really use. It wouldn't just be a novelty. It would be something I could actually fit in my pocket, that I'd want to use as my primary cell phone.

That would probably be a tough sell for most people who live with their smartphones. But I'm anti-smartphone, despite working in technology development. All of my friends know that I have a flip phone, or have had a flip phone until now, and that I don't text. I don't. I just don't like being that connected. I don't want to have to respond to people at any point of the day. So this is kind of a way of downgrading my flip phone even more. And then if people say, "You don't text? Why don't you text?" I could just hold up the phone and say, this is why!


And also, you know, smartphones are one thing—you have this finicky annoying touchscreen interface, it drives me crazy, it really does. But then even my flip phone does things that I don’t ask it to do, unexpectedly, because some weird button got pushed. I wanted physical keys or buttons I could push for every function and not having to guess whether or not it was actually going to do what I told it to do. You know, when you hold down the power button–is it turning on right now? Is it turning off? I have a switch. It’s a toggle switch, it’s either on or it’s off. That’s it. I just wanted to control the technology. I think people have gone too far acquiescing to the standards of dealing with smartphones.

LG: What kind of flip phone have you been using?

JH: Oh, OK … Do I have it with me? This is so new, it’s only my third day of using my rotary phone over my primary phone, but I’ve been keeping my flip phone in my pocketbook. It is an LG branded flip phone, it’s on a T-Mobile pay-as-you-go-plan, but I don’t even know the model number.

LG: It sounds like what you’re describing is a kind of yearning for a tactile experience.

JH: Exactly. There’s something to be said for tactile interface, actual switches and buttons. Even simple things, like, a little FM radio that has a dial so you can listen to stations, even that’s been replaced by electronic keys that only let you increment left and right. I guess it’s fine, but it does come with its tradeoffs, and no one seems to care and I care.

LG: What would you say was the biggest challenge in building this? You were not only working with the rotary dial but also the 3D-printed enclosure and the micro controller and the cell transceiver and—was it a Raspberry Pi?

JH: Actually it was an Arduino custom board. First, I’ll say that this has been a back-burner project for a long time. I first had the idea years ago. Now if you Google rotary cell phones, a few other people have done it, but none I don’t think could be used as your primary phone. Adafruit has some stuff that makes this easier—for example, a cell phone radio development board, which I started with. I got it working in a very basic way on my workbench, without it being enclosed in the cell phone casing, and proved it wasn’t too crazy.

Testing the circuits on breadboards.

Photograph: Justine Haupt 


But the hardest part was moving from that, which was minimally usable, to something that was truly compact and light enough and sleek enough so I could slip it into my pocket and really use it. And know that it would be reliable and have long enough battery life. That took awhile, I think about three years, and only in the past couple months did I pick it up again. It’s still a work in progress.

LG: What’s interesting is that you still have an e-paper display [on the phone] so that you can see messages and missed calls. Which is funny because, when you think about it, with the old rotary phones, you couldn’t see any of that. It just rang and rang, and if you missed it, you missed it.

JH: Right. The main point I think is that I didn’t do it just to be a throwback novelty thing, to reproduce a rotary phone for the modern era. I wanted it to be a usable, functional phone, and you can’t really do that without having some kind of display now, especially because of robocalls. You know, you want to be sure it’s a number you’re really interested in before you pick it up.

LG: It seems like an important point to make, because there is a lot of nostalgic tech out now. Motorola’s just resurrected the Razr. Of course, it has this new flexible polymer display, but it’s a clamshell phone that flips open and closed. Nintendo has resurrected the original NES in a new form. There was even an app for iPhone recently that mimicked the click wheel experience on an old iPod. What do you think all of this says about the way we’re looking back to tech from 10, 20, 30 years ago, right as we’re being inundated with new tech?

JH: I was just thinking about this the other day. You’re right about this resurgence of older-feeling technology. Even cameras, you know, mirrorless single-lens cameras are being stylized in this '70s and '80s film SLR style of camera, more bulky and boxy with more buttons. And in some ways it’s perceived as a kind of hipster mentality. I do like it, even though I don’t identify as a hipster. And then things like the Motorola Razr, which I just found out about today … I think the point of these throwbacks is that novelty wins. People love novelty so much that they’re willing to overlook functionality.

Take, for example, a really simple thing: ChapStick. It’s been around forever. My parents used it. It’s not a technological thing. And then all of a sudden these egg-shaped ones appear, and everybody starts using them. If you think about it, an egg-shaped applicator is a lot less precise and annoying to use than the little pencil one. But gosh darn it, it looks like an egg, it’s colorful, people want it! And it wins. Given enough time, people circle around again and then the older stick-shaped ones become the novelty and then you go back to that. But none of it is really based in logic or how usable the thing is. It’s just trends. And you certainly see that with phones. I mean, maybe people are finally ready to explore a form factor for phones other than what Apple invented with the iPhone. And maybe with other things too. I don’t know if we ever stabilize, or if we keep oscillating between different styles.

LG: What do you think about the fact that production cycles for some of these new products are compressed, and not only that, but purchasing cycles are compressed? When I think back to the rotary phone, the family PC, the VCR … people had those for years.


JH: I’m sorry that we always have this bias that your childhood, your nostalgia, is the deepest one. But also, being in technology and developing technology, I wonder how it might affect one’s ability to understand technology. When I grew up, I could easily take things apart. They were hard to understand, but at least there was something to take apart and you could see mechanisms and understand that there was circuitry inside. And now technology is increasingly like magic, so you really can’t disassemble things. So I do wonder how the next generation of engineers, how they’ll bridge the gap between being interested in something and being able to actualize it.

On the other hand, I’m so excited that release timelines are so compressed and how fast the future is coming. Just in the past ten years I’m seeing things I never thought I’d see and I’m recalibrating myself to expect even greater things. For example, things like gene editing and what biohackers are doing. And space exploration, which is a passion of mine. And all of that. So on the other hand I’m just so excited. I think we live in an amazing time.

Read more:

Continue Reading


Trump Proposes a Cut in Research Spending, but a Boost for AI



President Trump Monday proposed cutting federal research spending—except in key areas including artificial intelligence and quantum technologies.

Trump’s budget for the fiscal year beginning October 1 proposes spending $142.2 billion in research and development, 9 percent less than in the current year. The White House says its proposal is 6 percent more than it requested last year.

The budget request is something of a gambler’s approach to funding American innovation, betting big in select areas. “I find it disappointing and concerning that funding for basic research is down,” says Martijn Rasser, a senior fellow at the Center for a New American Security, a policy think tank in Washington, DC. “We just don’t know where the next breakthroughs will come from.”

The budget goes all-in on AI and quantum, proposing to double funding across the departments including the National Science Foundation, the National Institutes of Health, the Department of Energy, Darpa, and the DoD’s Joint AI Center.

At the same time, the president proposed cutting research spending in nearly every arm of the government, including by $424 million at the National Science Foundation, $4.7 billion at the Defense Department, and $3.2 billion at the Department of Energy.

Rasser says it’s good to see proposed funding for AI and quantum increase, since both are critical emerging areas. He recently coauthored a report that called for substantially more government funding for AI, noting that the technology could transform industries in the way that software has.

But Rasser worries that cutting overall funding for fundamental research will undermine progress and growth because innovations can emerge from many fields. “It’s just not a good trajectory,” he says.

Keep Reading
The latest on artificial intelligence, from machine learning to computer vision and more

The president’s budget is a proposal and is likely to be altered by Congress. But the plan signals an approach to scientific research that prioritizes areas that are seen as crucial to international competition and military advantage. AI and quantum technologies have received substantial investment from America’s big geopolitical rival, China, and both are being rushed into military service by Beijing.

AI has emerged as a powerful technology, with big tech companies investing billions into its development and harnessing it to build everything from self-driving cars to voice assistants.

Quantum computing and communications technologies, built on the peculiar properties of quantum physics, are far less proven, though they have the potential to deliver equally big payoffs someday. A quantum version of the internet, for instance, should guarantee perfect security, while quantum computers could crack now-unsolvable problems with relative ease.

During Trump’s time in office, AI and quantum technologies have become increasing areas of focus. The president launched the American AI Initiative in February 2019, outlining a national strategy for AI leadership. And Trump signed the National Quantum Initiative Act into law in December 2018, increasing funding for quantum computing and communications.

Today, AI researchers find themselves in hot demand and, increasingly, able to secure ready government funding. But some are wary of the White House plan.

“It looks like a mixed blessing,” says Subbarao Kambhampati, an AI professor at Arizona State University and a past president of the Association for the Advancement of Artificial Intelligence.

Kambhampati notes that the funding allocated for AI seems geared towards driving fundamental work in AI, which will help push new advances in the field. “I am happy to see funding for basic research,” he says.

But he warns that cutting funding for other areas of research may not only undermine progress in other fields but also have a knock-on effect on AI, because progress has often drawn from other areas. Studies of animal brains can inspire new designs for artificial neural networks, for example. “Neuroscience will be really relevant to AI in over the longer term,” he says.

Kelvin Droegemeier, director of the White House Office of Science and Technology Policy, defended the proposed drop in research funding in a call with reporters. “President Trump has made very clear that investing in early stage basic research is extremely important and this budget does that,” Droegemeier said. “I think it's a very responsible act on President Trump's part to make sure that we prioritize what are high importance activities are especially relative to great power competition.”


Dario Gil, director of IBM research and a member of the President’s Council of Advisors on Science and Technology, argues that government investment in AI will boost scientific discovery in general, thereby helping advance research in other areas. “The purpose is to accelerate discovery,” he says. “That is going to permeate every sector of the economy and national defense.”

Gil also suggests that, like the internet before it, quantum computers and communications networks may have unforeseen payoffs. “We need to see a significant acceleration of the investments, and this is a very good step in the direction,” he says.

He might be right, but it’s tricky to pick the winners in research and innovation. As Rasser says, “With basic research, you never know what’s going to pan out.”

Read more:

Continue Reading


Quantum SDP-Solvers: Better upper and lower bounds



Joran van Apeldoorn1,2, András Gilyén1,2, Sander Gribling1,2, and Ronald de Wolf1,2,3

1QuSoft, Amsterdam, the Netherlands.
2University of Amsterdam, the Netherlands.
3University of Amsterdam, the Netherlands.

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


Brandão and Svore [14] recently gave quantum algorithms for approximately solving semidefinite programs, which in some regimes are faster than the best-possible classical algorithms in terms of the dimension $n$ of the problem and the number $m$ of constraints, but worse in terms of various other parameters. In this paper we improve their algorithms in several ways, getting better dependence on those other parameters. To this end we develop new techniques for quantum algorithms, for instance a general way to efficiently implement smooth functions of sparse Hamiltonians, and a generalized minimum-finding procedure.

We also show limits on this approach to quantum SDP-solvers, for instance for combinatorial optimization problems that have a lot of symmetry. Finally, we prove some general lower bounds showing that in the worst case, the complexity of every quantum LP-solver (and hence also SDP-solver) has to scale linearly with $mn$ when $mapprox n$, which is the same as classical.

Semidefinite programs (SDPs) are an important tool in convex optimization tasks and approximation algorithms. They allow to optimize a linear function over positive semidefinite matrices, subject to linear constraints on those matrices, and they are solvable in polynomial time on a classical computer. Brand~ao and Svore recently gave a quantum algorithm for solving semidefinite programs that (in some regimes) is faster than the best-possible classical algorithm. In this paper we improve on their algorithm in several ways, in particular we obtain a 4-th root improvement in the running time with respect to the required precision. We also show strong limits for this particular approach to quantum SDP-solvers, for instance for combinatorial optimization problems that have a lot of symmetry, and we prove some general limitations for quantum SDP-solvers.

► BibTeX data

► References

[1] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. toc, 8(6):121–164, 2012.

[2] Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach to semidefinite programs. jacm, 63(2):12:1–12:35, 2016. Earlier version in STOC’07.

[3] Andris Ambainis. Quantum walk algorithm for element distinctness. siamjc, 37(1):210–239, 2007. Earlier version in FOCS’04. arXiv: quant-ph/​0311001?.

[4] Joran van Apeldoorn and András Gilyén. Improvements in quantum SDP-solving with applications. In icalp46th, pages 99:1–99:15, 2019. arXiv: 1804.05058?.

[5] Joran van Apeldoorn and András Gilyén. Quantum algorithms for zero-sum games. arXiv: 1904.03180?, 2019.

[6] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-solvers: Better upper and lower bounds. In focs58th, pages 403–414, 2017. arXiv: 1705.01843?.

[7] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Convex optimization using quantum oracles. quantum, 4:220, 2020. arXiv: 1809.00643?.

[8] Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley-Interscience, third edition, 2008.

[9] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4–5):493–505, 1998. arXiv: quant-ph/​9605034?.

[10] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. prl, 114(9):090502, 2015. arXiv: 1412.4687?.

[11] Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In focs56th, pages 792–809, 2015. arXiv: 1501.01715?.

[12] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of Contemporary Mathematics Series, pages 53–74. AMS, 2002. arXiv: quant-ph/​0005055?.

[13] Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning. In icalp46th, pages 27:1–27:14, 2019. arXiv: 1710.02581?.

[14] Fernando G. S. L. Brandão and Krysta M. Svore. Quantum speed-ups for solving semidefinite programs. In focs58th, pages 415–426, 2017. arXiv: 1609.05537?.

[15] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu. Quantum algorithms and lower bounds for convex optimization. quantum, 4:221, 2020. arXiv: 1809.01731?.

[16] Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. rspa, 454(1969):339–354, 1998. arXiv: quant-ph/​9708016?.

[17] Andrew M. Childs, Robin Kothari, and Rolando D. Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. siamjc, 46(6):1920–1950, 2017. arXiv: 1511.02306?.

[18] Anirban Narayan Chowdhury and Rolando D. Somma. Quantum algorithms for Gibbs sampling and hitting-time estimation. qic, 17(1&2):41–64, 2017. arXiv: 1603.02940?.

[19] Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. qic, 12(11&12):901–924, 2012. arXiv: 1202.5822?.

[20] George B. Dantzig. Maximization of a linear function of variables subject to linear inequalities. In Activity Analysis of Production and Allocation, Cowles Commission Monograph No. 13, pages 339–347. John Wiley & Sons Inc., New York, N. Y., 1951.

[21] Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum. arXiv: quant-ph/​9607014?, 1996.

[22] Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. siamjc, 35(6):1310–1328, 2006. Earlier version in ICALP’04. arXiv: quant-ph/​0401091?.

[23] Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. comb, 1(2):169–197, 1981.

[24] Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer, 1988.

[25] Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv: quant-ph/​0208112?, 2002.

[26] Lov K. Grover. A fast quantum mechanical algorithm for database search. In stoc28th, pages 212–219, 1996. arXiv: quant-ph/​9605043?.

[27] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In stoc51st, pages 193–204, 2019. arXiv: 1806.01838?.

[28] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. jacm, 42(6):1115–1145, 1995. Earlier version in STOC’94.

[29] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. prl, 103(15):150502, 2009. arXiv: 0811.3171?.

[30] Shelby Kimmel. Quantum adversary (upper) bound. cjtcs, 2013:4:1–14, 2013. Earlier version in ICALP’12. arXiv: 1101.0797?.

[31] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? siamjc, 37(1):319–357, 2007. Earlier version in FOCS’04.

[32] Iordanis Kerenidis and Anupam Prakash. A quantum interior point method for LPs and SDPs. arXiv: 1808.09266?, 2018.

[33] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. prl, 118(1):010501, 2017. arXiv: 1606.02685?.

[34] Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. quantum, 3:163, 2019. arXiv: 1610.06546?.

[35] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In focs56th, pages 1049–1065, 2015. arXiv: 1508.04874?.

[36] Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000.

[37] Y. Nesterov and A. Nemirovski. Interior-point polynomial algorithms in convex programming, volume 13 of SIAM Studies in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), 1994.

[38] David Poulin and Pawel Wocjan. Preparing ground states of quantum many-body systems on a quantum computer. prl, 102(13):130503, 2009. arXiv: 0809.2705?.

[39] David Poulin and Pawel Wocjan. Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer. prl, 103(22):220502, 2009. arXiv: 0905.2199?.

[40] James Renegar. “Efficient” subgradient methods for general convex optimization. siamjc, 26(4):2649–2676, 2016. arXiv: 1605.08712?.

[41] James Renegar. Accelerated first-order methods for hyperbolic programming. Mathematical Programming, 173(1):1–35, 2019. arXiv: 1512.07569?.

[42] Alexander Schrijver. Theory of Linear and Integer Programming. John Wiley & Sons, Inc., New York, NY, USA, 1986.

[43] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. siamjc, 26(5):1484–1509, 1997. Earlier version in FOCS’94. arXiv: quant-ph/​9508027?.

[44] Koji Tsuda, Gunnar Rätsch, and Manfred K. Warmuth. Matrix exponentiated gradient updates for on-line learning and Bregman projection. Journal of Machine Learning Research, 6:995–1018, 2005. Earlier version in NIPS’04.

[45] Manfred K. Warmuth and Dima Kuzmin. Online variance minimization. Machine Learning, 87(1):1–32, 2012. Earlier version in COLT’06.

Cited by

[1] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe, “Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics”, arXiv:1806.01838.

[2] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, and Leonard Wossnig, “Quantum machine learning: a classical perspective”, Proceedings of the Royal Society of London Series A 474 2209, 20170551 (2018).

[3] Patrick Rebentrost and Seth Lloyd, “Quantum computational finance: quantum algorithm for portfolio optimization”, arXiv:1811.03975.

[4] Joran van Apeldoorn and András Gilyén, “Quantum algorithms for zero-sum games”, arXiv:1904.03180.

[5] András Gilyén, Srinivasan Arunachalam, and Nathan Wiebe, “Optimizing quantum optimization algorithms via faster quantum gradient computation”, arXiv:1711.00465.

[6] Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione, and Seth Lloyd, “Quantum gradient descent and Newton’s method for constrained polynomial optimization”, arXiv:1612.01789.

[7] Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu, “Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning”, arXiv:1710.02581.

[8] Joran van Apeldoorn and András Gilyén, “Improvements in Quantum SDP-Solving with Applications”, arXiv:1804.05058.

[9] Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang, “Quantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches”, arXiv:1901.03254.

[10] Simon Apers, “Quantum Walk Sampling by Growing Seed Sets”, arXiv:1904.11446.

[11] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf, “Convex optimization using quantum oracles”, arXiv:1809.00643.

[12] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu, “Quantum algorithms and lower bounds for convex optimization”, arXiv:1809.01731.

[13] Yimin Ge, Jordi Tura, and J. Ignacio Cirac, “Faster ground state preparation and high-precision ground energy estimation with fewer qubits”, arXiv:1712.03193.

[14] Ivan Bardet and Cambyse Rouzé, “Hypercontractivity and logarithmic Sobolev Inequality for non-primitive quantum Markov semigroups and estimation of decoherence rates”, arXiv:1803.05379.

[15] Ashley Montanaro, “Quantum speedup of branch-and-bound algorithms”, arXiv:1906.10375.

[16] Johannes Bausch, Sathyawageeswar Subramanian, and Stephen Piddock, “A Quantum Search Decoder for Natural Language Processing”, arXiv:1909.05023.

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


Continue Reading