Connect with us


Completely positive master equation for arbitrary driving and small level spacing



Evgeny Mozgunov1 and Daniel Lidar1,2,3,4

1Center for Quantum Information Science & Technology, University of Southern California, Los Angeles, California 90089, USA
2Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, California 90089, USA
3Department of Chemistry, University of Southern California, Los Angeles, California 90089, USA
4Department of Physics and Astronomy, University of Southern California, Los Angeles, California 90089, USA

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


Markovian master equations are a ubiquitous tool in the study of open quantum systems, but deriving them from first principles involves a series of compromises. On the one hand, the Redfield equation is valid for fast environments (whose correlation function decays much faster than the system relaxation time) regardless of the relative strength of the coupling to the system Hamiltonian, but is notoriously non-completely-positive. On the other hand, the Davies equation preserves complete positivity but is valid only in the ultra-weak coupling limit and for systems with a finite level spacing, which makes it incompatible with arbitrarily fast time-dependent driving.
Here we show that a recently derived Markovian coarse-grained master equation (CGME), already known to be completely positive, has a much expanded range of applicability compared to the Davies equation, and moreover, is locally generated and can be generalized to accommodate arbitrarily fast driving. This generalization, which we refer to as the time-dependent CGME, is thus suitable for the analysis of fast operations in gate-model quantum computing, such as quantum error correction and dynamical decoupling. Our derivation proceeds directly from the Redfield equation and allows us to place rigorous error bounds on all three equations: Redfield, Davies, and coarse-grained. Our main result is thus a completely positive Markovian master equation that is a controlled approximation to the true evolution for any time-dependence of the system Hamiltonian, and works for systems with arbitrarily small level spacing. We illustrate this with an analysis showing that dynamical decoupling can extend coherence times even in a strictly Markovian setting.

Real quantum devices available in the lab today are never perfectly isolated from their environment. ​If the isolation is good enough, the effect of the environment can be either neglected altogether, or approximated by a simple mathematical model. We investigate this intuition in great detail, trying to answer exactly how good the isolation needs to be for a simple mathematical model to be within, say, 5% of what an experimentalist would actually see in the lab. Usually, this question is answered on a case-by-case basis by attempting to fit the experimental results with the model and observing the error of the fit. Here we approach this question in some generality, as a rigorous mathematical theorem that we prove under very weak assumptions.

Our result states that as long as the dynamics of the environment is much faster than its effect on the system, so the environment has time to equilibrate regardless of what the system is doing, then there is a mathematical model that can be trusted. The generality of our result is such that it applies to any number of qubits, as well as other quantum systems such as atoms and quantum dots. The control applied to the quantum system by the experimentalist is included in our model and can have a nontrivial interplay with the open system effects. Our model captures this interplay in many relevant cases, both for future theoretical results in quantum information, and for the simulation of quantum experiments.

► BibTeX data

► References

[1] R. Alicki and K. Lendi, Quantum Dynamical Semigroups and Applications (Springer Science & Business Media, 2007).

[2] H.-P. Breuer and F. Petruccione, The Theory of Open Quantum Systems (Oxford University Press, Oxford, 2002).

[3] C.W. Gardiner and P. Zoller, Quantum Noise, Springer Series in Synergetics, Vol. 56 (Springer, Berlin, 2000).

[4] E. B. Davies, “Markovian master equations,” Communications in Mathematical Physics 39, 91-110 (1974).

[5] G. Lindblad, “On the generators of quantum dynamical semigroups,” Comm. Math. Phys. 48, 119-130 (1976).

[6] T. Albash, W. Vinci, A. Mishra, P. A. Warburton, and D. A. Lidar, “Consistency tests of classical and quantum models for a quantum annealer,” Phys. Rev. A 91, 042314- (2015a).

[7] S. Boixo, V. N. Smelyanskiy, A. Shabani, S. V. Isakov, M. Dykman, V. S. Denchev, M. H. Amin, A. Y. Smirnov, M. Mohseni, and H. Neven, “Computational multiqubit tunnelling in programmable quantum annealers,” Nat Commun 7 (2016).

[8] T. Albash, I. Hen, F. M. Spedalieri, and D. A. Lidar, “Reexamination of the evidence for entanglement in a quantum annealer,” Physical Review A 92, 062328- (2015b).

[9] A. Mishra, T. Albash, and D. A. Lidar, “Finite temperature quantum annealing solving exponentially small gap problem with non-monotonic success probability,” Nature Communications 9, 2917 (2018).

[10] R. Feynman and F. Vernon, “The theory of a general quantum system interacting with a linear dissipative system,” Annals of Physics 24, 118 – 173 (1963).

[11] A. Caldeira and A. Leggett, “Quantum tunnelling in a dissipative system,” Annals of Physics 149, 374 – 456 (1983).

[12] D. E. Makarov and N. Makri, “Path integrals for dissipative systems by tensor multiplication. condensed phase quantum dynamics for arbitrarily long time,” Chemical Physics Letters 221, 482 – 491 (1994).

[13] E. Sim, “Quantum dynamics for a system coupled to slow baths: On-the-fly filtered propagator method,” The Journal of Chemical Physics 115, 4450-4456 (2001).

[14] K. Kraus, States, Effects, and Operations (Springer, Berlin, 1983).

[15] J. M. Dominy and D. A. Lidar, “Beyond complete positivity,” Quant. Inf. Proc. 15, 1349 (2016).

[16] V. Gorini, A. Frigerio, M. Verri, A. Kossakowski, and E. C. G. Sudarshan, “Properties of quantum Markovian master equations,” Reports on Mathematical Physics 13, 149-173 (1978).

[17] S. Nakajima, “On Quantum Theory of Transport Phenomena : Steady Diffusion,” Prog. Theor. Phys. 20, 948 (1958).

[18] R. Zwanzig, “Ensemble Method in the Theory of Irreversibility,” J. Chem. Phys. 33, 1338 (1960).

[19] A. Redfield, “The theory of relaxation processes,” in Advances in Magnetic Resonance, Advances in Magnetic and Optical Resonance, Vol. 1, edited by J. S. Waugh (Academic Press, 1965) pp. 1 – 32.

[20] D. Bacon, D. A. Lidar, and K. B. Whaley, “Robustness of decoherence-free subspaces for quantum computation,” Phys. Rev. A 60, 1944-1955 (1999).

[21] A. J. van Wonderen and K. Lendi, “Virtues and limitations of markovian master equations with a time-dependent generator,” J. Stat. Phys. 100, 633-658 (2000).

[22] D. A. Lidar, Z. Bihary, and K. Whaley, “From completely positive maps to the quantum Markovian semigroup master equation,” Chem. Phys. 268, 35 (2001).

[23] S. Daffer, K. Wodkiewicz, J.D. Cresser, J.K. McIver, “Depolarizing channel as a completely positive map with memory,” Phys. Rev. A 70, 010304(R) (2004).

[24] A. Shabani and D. A. Lidar, “Completely positive post-markovian master equation via a measurement approach,” Phys. Rev. A 71, 020101(R) (2005).

[25] S. Maniscalco and F. Petruccione, “Non-Markovian dynamics of a qubit,” Phys. Rev. A 73, 012111 (2006).

[26] J. Piilo, S. Maniscalco, K. Härkönen, and K.-A. Suominen, “Non-markovian quantum jumps,” Physical Review Letters 100, 180402- (2008).

[27] H.-P. Breuer and B. Vacchini, “Quantum semi-markov processes,” Physical Review Letters 101, 140402- (2008).

[28] R. S. Whitney, “Staying positive: going beyond lindblad with perturbative master equations,” Journal of Physics A: Mathematical and Theoretical 41, 175304 (2008).

[29] L.-A. Wu, G. Kurizki, and P. Brumer, “Master equation and control of an open quantum system with leakage,” Physical Review Letters 102, 080405- (2009).

[30] D. Chruściński and A. Kossakowski, “Non-markovian quantum dynamics: Local versus nonlocal,” Phys. Rev. Lett. 104, 070406 (2010).

[31] T. Albash, S. Boixo, D. A. Lidar, and P. Zanardi, “Quantum adiabatic Markovian master equations,” New J. of Phys. 14, 123016 (2012).

[32] E. Mozgunov, “Local master equation for small temperatures,” arXiv:1611.04188 (2016).

[33] A. Y. Smirnov and M. H. Amin, “Theory of open quantum dynamics with hybrid noise,” New Journal of Physics 20, 103037 (2018).

[34] R. Dann, A. Levy, and R. Kosloff, “Time-dependent markovian quantum master equation,” Phys. Rev. A 98, 052129 (2018).

[35] L. C. Venuti and D. A. Lidar, “Error reduction in quantum annealing using boundary cancellation: Only the end matters,” Phys. Rev. A 98, 022315 (2018).

[36] G. McCauley, B. Cruikshank, D. I. Bondar, and K. Jacobs, “Completely positive, accurate master equation for weakly-damped quantum systems across all regimes,” arXiv:1906.08279 (2019).

[37] F. Benatti, R. Floreanini, and U. Marzolino, “Environment-induced entanglement in a refined weak-coupling limit,” EPL (Europhysics Letters) 88, 20011 (2009).

[38] F. Benatti, R. Floreanini, and U. Marzolino, “Entangling two unequal atoms through a common bath,” Phys. Rev. A 81, 012105 (2010).

[39] M. Merkli, “Quantum markovian master equations: Resonance theory shows validity for all time scales,” Annals of Physics 412, 167996 (2020).

[40] C. Majenz, T. Albash, H.-P. Breuer, and D. A. Lidar, “Coarse graining can beat the rotating-wave approximation in quantum markovian master equations,” Phys. Rev. A 88, 012103- (2013).

[41] T. S. Cubitt, A. Lucia, S. Michalakis, and D. Perez-Garcia, “Stability of local quantum dissipative systems,” Communications in Mathematical Physics 337, 1275-1315 (2015).

[42] E. Knill, “Quantum computing with realistically noisy devices,” Nature 434, 39-44 (2005).

[43] R. Alicki, D. A. Lidar, and P. Zanardi, “Internal consistency of fault-tolerant quantum error correction in light of rigorous derivations of the quantum markovian limit,” Phys. Rev. A 73, 052311 (2006).

[44] D. A. Lidar, “Lecture notes on the theory of open quantum systems,” arXiv preprint arXiv:1902.00967 (2019).

[45] T. Albash and D. A. Lidar, “Decoherence in adiabatic quantum computation,” Phys. Rev. A 91, 062320- (2015).

[46] M. Žnidarič, “Dephasing-induced diffusive transport in the anisotropic heisenberg model,” New Journal of Physics 12, 043001 (2010).

[47] M. V. Medvedyeva, T. Prosen, and M. Žnidarič, “Influence of dephasing on many-body localization,” Phys. Rev. B 93, 094205 (2016).

[48] R. Bhatia, Matrix Analysis, Graduate Texts in Mathematics No. 169 (Springer-Verlag, New York, 1997).

[49] P. Gaspard and M. Nagaoka, “Slippage of initial conditions for the redfield master equation,” Journal of Chemical Physics 111, 5668-5675 (1999).

[50] G. Vidal, “Efficient classical simulation of slightly entangled quantum computations,” Phys. Rev. Lett. 91, 147902 (2003).

[51] F. Verstraete, J. J. Garcia-Ripoll, and J. I. Cirac, “Matrix product density operators: Simulation of finite-temperature and dissipative systems,” Phys. Rev. Lett. 93, 207204 (2004).

[52] E. H. Lieb and D.W. Robinson, “The finite group velocity of quantum spin systems,” Commun. Math. Phys. 28, 251 (1972).

[53] J. Haah, M. Hastings, R. Kothari, and G. H. Low, “Quantum algorithm for simulating real time evolution of lattice hamiltonians,” in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) (2018) pp. 350-360.

[54] H. Pichler, A. J. Daley, and P. Zoller, “Nonequilibrium dynamics of bosonic atoms in optical lattices: Decoherence of many-body states due to spontaneous emission,” Phys. Rev. A 82, 063605 (2010).

[55] L.-M Duan and G.-C. Guo, “Reducing decoherence in quantum-computer memory with all quantum bits coupling to the same environment,” Phys. Rev. A 57, 737 (1998).

[56] P. Zanardi and M. Rasetti, “Noiseless quantum codes,” Phys. Rev. Lett. 79, 3306-3309 (1997).

[57] D. A. Lidar, I. L. Chuang, and K. B. Whaley, “Decoherence-free subspaces for quantum computation,” Phys. Rev. Lett. 81, 2594-2597 (1998).

[58] D. A. Lidar and K. B. Whaley, “Decoherence-free subspaces and subsystems,” in Irreversible Quantum Dynamics, Lecture Notes in Physics, Vol. 622, edited by F. Benatti and R. Floreanini (Springer, Berlin, 2003) p. 83.

[59] P.G. Kwiat, A.J. Berglund, J.B. Altepeter, and A.G. White, “Experimental Verification of Decoherence-Free Subspaces,” Science 290, 498 (2000).

[60] L. Viola, E. M. Fortunato, M. A. Pravia, E. Knill, R. Laflamme, and D. G. Cory, “Experimental realization of noiseless subsystems for quantum information processing,” Science 293, 2059-2063 (2001).

[61] D. Kielpinski, V. Meyer, M. A. Rowe, C. A. Sackett, W. M. Itano, C. Monroe, and D. J. Wineland, “A decoherence-free quantum memory using trapped ions,” Science 291, 1013-1015 (2001).

[62] J. E. Ollerenshaw, D. A. Lidar, and L. E. Kay, “Magnetic resonance realization of decoherence-free quantum computation,” Phys. Rev. Lett. 91, 217904 (2003).

[63] L. Viola and S. Lloyd, “Dynamical suppression of decoherence in two-state quantum systems,” Phys. Rev. A 58, 2733-2744 (1998).

[64] P. Zanardi, “Symmetrizing evolutions,” Physics Letters A 258, 77-82 (1999).

[65] D. Lidar and T. Brun, eds., Quantum Error Correction (Cambridge University Press, Cambridge, UK, 2013).

[66] D. Suter and G. A. Álvarez, “Colloquium: Protecting quantum information against environmental noise,” Reviews of Modern Physics 88, 041001- (2016).

[67] H. K. Ng, D. A. Lidar, and J. Preskill, “Combining dynamical decoupling with fault-tolerant quantum computation,” Phys. Rev. A 84, 012305- (2011).

[68] K. Szczygielski and R. Alicki, “Markovian theory of dynamical decoupling by periodic control,” Physical Review A 92, 022349- (2015).

[69] J. E. Gough and H. I. Nurdin, “Can quantum markov evolutions ever be dynamically decoupled?” in 2017 IEEE 56th Annual Conference on Decision and Control (CDC) (2017) pp. 6155-6160.

[70] C. Addis, F. Ciccarello, M. Cascio, G. M. Palma, and S. Maniscalco, “Dynamical decoupling efficiency versus quantum non-markovianity,” New Journal of Physics 17, 123004 (2015).

[71] C. Arenz, D. Burgarth, P. Facchi, and R. Hillier, “Dynamical decoupling of unbounded hamiltonians,” Journal of Mathematical Physics, Journal of Mathematical Physics 59, 032203 (2018).

[72] L. Li, M. J. W. Hall, and H. M. Wiseman, “Concepts of quantum non-markovianity: A hierarchy,” Concepts of quantum non-Markovianity: A hierarchy, Physics Reports 759, 1-51 (2018).

[73] I. de Vega, M. C. Bañuls, and A. Pérez, “Effects of dissipation on an adiabatic quantum search algorithm,” New J. of Phys. 12, 123010 (2010).

[74] https:/​/​​mvjenia/​CGMEcode, code for the numerical section of the paper.

[75] L. Isserlis, “On certain probable errors and correlation coefficients of multiple frequency distributions with skew regression,” Biometrika 11, 185 (1916).

[76] T. Albash, D. A. Lidar, M. Marvian, and P. Zanardi, “Fluctuation theorems for quantum processes,” Phys. Rev. E 88, 032146- (2013).

[77] T. Albash and D. A. Lidar, “Adiabatic quantum computation,” Reviews of Modern Physics 90, 015002- (2018).

[78] R. Alicki, M. Fannes, and M. Horodecki, “A statistical mechanics view on kitaev’s proposal for quantum memories,” Journal of Physics A: Mathematical and Theoretical 40, 6451-6467 (2007).

[79] H. Bombin, “Topological subsystem codes,” Physical Review A 81, 032301- (2010).

[80] B. Altshuler, H. Krovi, and J. Roland, “Anderson localization makes adiabatic quantum optimization fail,” Proceedings of the National Academy of Sciences 107, 12446-12450 (2010).

[81] M. Reed and B. Simon, Methods of Modern Mathematical Physics: Fourier analysis, self-adjointness, Vol. 2 (Academic Press, 1975).

[82] H. Alzer, “On some inequalities for the incomplete gamma function,” Mathematics of Computation 66, 771 (1997).

Cited by

Could not fetch Crossref cited-by data during last attempt 2020-02-06 15:54:51: Could not fetch cited-by data for 10.22331/q-2020-02-06-227 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-06 15:54:51).



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