Connect with us

Quantum

White House reportedly aims to double AI research budget to $2B

Published

on

The White House is pushing to dedicate an additional billion dollars to fund artificial intelligence research, effectively doubling the budget for that purpose outside of Defense Department spending, Reuters reported today, citing people briefed on the plan. Investment in quantum computing would also receive a major boost.

The 2021 budget proposal would reportedly increase AI R&D funding to nearly $2 billion, and quantum to about $860 million, over the next two years.

The U.S. is engaged in what some describe as a “race” with China in the field of AI, though unlike most races this one has no real finish line. Instead, any serious lead means opportunities in business and military applications that may grow to become the next globe-spanning monopoly, a la Google or Facebook — which themselves, as quasi-sovereign powers, invest heavily in the field for their own purposes.

Simply doubling the budget isn’t a magic bullet to take the lead, if anyone can be said to have it, but deploying AI to new fields is not without cost and an increase in grants and other direct funding will almost certainly enable the technology to be applied more widely. Machine learning has proven to be useful for a huge variety of purposes and for many researchers and labs is a natural next step — but expertise and processing power cost money.

It’s not clear how the funds would be disbursed; It’s possible existing programs like federal Small Business Innovation Research awards could be expanded with this topic in mind, or direct funding to research centers like the National Labs could be increased.

Quantum computing’s ‘Hello World’ moment

Research into quantum computing and related fields is likewise costly. Google’s milestone last fall of achieving “quantum superiority,” or so the claim goes, is only the beginning for the science and neither the hardware nor software involved have much in the way of precedents.

Furthermore quantum computers as they exist today and for the foreseeable future have very few valuable applications, meaning pursuing them is only an investment in the most optimistic sense. However, government funding via SBIR and grants like those are intended to de-risk exactly this kind of research.

The proposed budget for NASA is also expected to receive a large increase in order to accelerate and reinforce various efforts within the Artemis Moon landing program. It was not immediately clear how these funds would be raised or from where they would be reallocated.

Read more: https://techcrunch.com/2020/02/07/white-house-reportedly-aims-to-double-ai-research-budget-to-2b/

Quantum

How a Space Engineer Made Her Own Rotary Cell Phone

Published

on

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!

Advertisement

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 

Advertisement

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.

Advertisement

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: https://www.wired.com/story/justine-haupt-rotary-phone/

Continue Reading

Quantum

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

Published

on

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.”

Advertisement

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: https://www.wired.com/story/trump-proposes-cut-research-spending-boost-ai/

Continue Reading

Quantum

Quantum SDP-Solvers: Better upper and lower bounds

Published

on


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.

Abstract

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.
https:/​/​doi.org/​10.4086/​toc.2012.v008a006

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

[3] Andris Ambainis. Quantum walk algorithm for element distinctness. siamjc, 37(1):210–239, 2007. Earlier version in FOCS’04. arXiv: quant-ph/​0311001?.
https:/​/​doi.org/​10.1137/​S0097539705447311
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?.
https:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2019.99
arXiv:1804.05058

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

[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?.
https:/​/​doi.org/​10.1109/​FOCS.2017.44
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?.
https:/​/​doi.org/​10.22331/​q-2020-01-13-220
arXiv:1809.00643

[8] Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley-Interscience, third edition, 2008.
https:/​/​doi.org/​10.1002/​0471722154

[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?.
3.0.CO;2-P”>https:/​/​doi.org/​10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P
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?.
https:/​/​doi.org/​10.1103/​PhysRevLett.114.090502
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?.
https:/​/​doi.org/​10.1109/​FOCS.2015.54
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?.
https:/​/​doi.org/​10.1090/​conm/​305/​05215
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?.
https:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2019.27
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?.
https:/​/​doi.org/​10.1109/​FOCS.2017.45
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?.
https:/​/​doi.org/​10.22331/​q-2020-01-13-221
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?.
https:/​/​doi.org/​10.1098/​rspa.1998.0164
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?.
https:/​/​doi.org/​10.1137/​16M1087072
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?.
https:/​/​doi.org/​10.26421/​QIC17.1-2
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?.
https:/​/​doi.org/​10.26421/​QIC12.11-12
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.
arXiv:quant-ph/9607014

[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?.
https:/​/​doi.org/​10.1137/​050644719
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.
https:/​/​doi.org/​10.1007/​BF02579273

[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.
arXiv:quant-ph/0208112

[26] Lov K. Grover. A fast quantum mechanical algorithm for database search. In stoc28th, pages 212–219, 1996. arXiv: quant-ph/​9605043?.
https:/​/​doi.org/​10.1145/​237814.237866
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?.
https:/​/​doi.org/​10.1145/​3313276.3316366
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.
https:/​/​doi.org/​10.1145/​227683.227684

[29] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. prl, 103(15):150502, 2009. arXiv: 0811.3171?.
https:/​/​doi.org/​10.1103/​PhysRevLett.103.150502
arXiv:0811.3171

[30] Shelby Kimmel. Quantum adversary (upper) bound. cjtcs, 2013:4:1–14, 2013. Earlier version in ICALP’12. arXiv: 1101.0797?.
https:/​/​doi.org/​10.4086/​cjtcs.2013.004
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.
https:/​/​doi.org/​10.1137/​S0097539705447372

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

[33] Guang Hao Low and Isaac L. Chuang. Optimal Hamiltonian simulation by quantum signal processing. prl, 118(1):010501, 2017. arXiv: 1606.02685?.
https:/​/​doi.org/​10.1103/​PhysRevLett.118.010501
arXiv:1606.02685

[34] Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. quantum, 3:163, 2019. arXiv: 1610.06546?.
https:/​/​doi.org/​10.22331/​q-2019-07-12-163
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?.
https:/​/​doi.org/​10.1109/​FOCS.2015.68
arXiv:1508.04874

[36] Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000.
https:/​/​doi.org/​10.1017/​CBO9780511976667

[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.
https:/​/​doi.org/​10.1137/​1.9781611970791

[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?.
https:/​/​doi.org/​10.1103/​PhysRevLett.102.130503
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?.
https:/​/​doi.org/​10.1103/​PhysRevLett.103.220502
arXiv:0905.2199

[40] James Renegar. “Efficient” subgradient methods for general convex optimization. siamjc, 26(4):2649–2676, 2016. arXiv: 1605.08712?.
https:/​/​doi.org/​10.1137/​15M1027371
arXiv:1605.08712

[41] James Renegar. Accelerated first-order methods for hyperbolic programming. Mathematical Programming, 173(1):1–35, 2019. arXiv: 1512.07569?.
https:/​/​doi.org/​10.1007/​s10107-017-1203-y
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?.
https:/​/​doi.org/​10.1137/​S0097539795293172
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.
http:/​/​jmlr.csail.mit.edu/​papers/​volume6/​tsuda05a/​tsuda05a.pdf

[45] Manfred K. Warmuth and Dima Kuzmin. Online variance minimization. Machine Learning, 87(1):1–32, 2012. Earlier version in COLT’06.
https:/​/​doi.org/​10.1007/​s10994-011-5269-0

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.

Source: https://quantum-journal.org/papers/q-2020-02-14-230/

Continue Reading

Trending