Connect with us


3Q: Scott Aaronson on Google’s new quantum-computing paper




In 2010, a Canadian company called D-Wave announced that it had begun production of what it called the world’s first commercial quantum computer, which was based on theoretical work done at MIT. Quantum computers promise to solve some problems significantly faster than classical computers — and in at least one case, exponentially faster. In 2013, a consortium including Google and NASA bought one of D-Wave’s machines.

Over the years, critics have argued that it’s unclear whether the D-Wave machine is actually harnessing quantum phenomena to perform its calculations, and if it is, whether it offers any advantages over classical computers. But this week, a group of Google researchers released a paper claiming that in their experiments, a quantum algorithm running on their D-Wave machine was 100 million times faster than a comparable classical algorithm.

Scott Aaronson, an associate professor of electrical engineering and computer science at MIT, has been following the D-Wave story for years. MIT News asked him to help make sense of the Google researchers’ new paper.

Q: The Google researchers’ paper focused on two algorithms: simulated annealing and quantum annealing. What are they?

A: Simulated annealing is one of the premier optimization methods that’s used today. It was invented in the early 1980s by direct analogy with what happens when people anneal metals, which is a 7,000-year-old technology. You heat the metal up, the atoms are all jiggling around randomly, and as you slowly cool it down, the atoms are more and more likely to go somewhere that will decrease the total energy.

In the case of an algorithm, you have a whole bunch of bits that start flipping between 1 and 0 willy-nilly, regardless of what that does to the solution quality. And then as you lower the “temperature,” a bit becomes more and more unwilling to flip in a way that would make the solution worse, until at the end, when the temperature is zero, a bit will only go to the value that keeps the solution going straight downhill — toward better solutions.

The main problem with simulated annealing, or for that matter with any other local-search method, is that you can get stuck in local optima. If you’re trying to reach the lowest point in some energy landscape, you can get stuck in a crevice that is locally the best, but you don’t realize that there’s a much lower valley somewhere else, if you would only go up and search. Simulated annealing tries to deal with that already: When the temperature is high, then you’re willing to move up the hill sometimes. But if there’s a really tall hill, even if it’s a very, very narrow hill — just imagine it’s a big spike sticking out of the ground — it could take you an exponential amount of time until you happen to flip so many bits that you happen to get over that spike.

In quantum mechanics, we know that particles can tunnel through barriers. (This is the language that the physicists use, which is a little bit misleading.) There’s an important 2002 paper by Farhi, Goldstone, and Gutmann, all of whom are here at MIT, and what they showed is that if your barrier really is a tall thin spike, then quantum annealing can give you an exponential speedup over classical simulated annealing. Classical annealing is going to get stuck at the base of that spike for exponential time, and quantum annealing is going to tunnel over it and get down to the global minimum in polynomial time.

Q: So is the D-Wave machine using quantum tunneling?

A: In the current model of the D-Wave chip, there are 1,000 or so qubits [quantum bits], but they’re organized into clusters of eight qubits each. The qubits within each cluster are very tightly connected to each other, and between clusters there are only weaker connections. I think that this is the best evidence we’ve had so far for quantum tunneling behavior, at least at the level of the eight-bit clusters.

The main way that they got an advantage over simulated annealing in these results was by taking advantage of the fact that quantum tunneling — or anything that correlates all the qubits within the cluster — can flip all the bits within each cluster at the same time, whereas simulated annealing is going to try flipping the bits one by one, then see that that’s not a good idea, then flip them all back, and not realize that by flipping all eight of them, you could get something better.

The case has now clearly been made that whatever the D-Wave device is doing, it’s something that can tunnel past this eight-qubit barrier. Of course, that still doesn’t mean that you’re doing anything faster than you could do it classically.

Q: What does it mean, then?

A: In computer science, normally we care about asymptotic speedup: We care about, “What is your running time as a function of the size of the problem? Does it grow linearly? Does it grow quadratically?” The constant that’s in front — Does it take 5N steps? Does it take 10N steps? — we don’t care that much about. We just care that it’s linear in N.

In the Google paper, they discuss two classical algorithms that do match the asymptotic performance — and one of them beats the real-world performance — of the D-Wave machine. So besides simulated annealing, there are two more classical algorithms that are actors in this story. One of them is quantum Monte Carlo, which is actually a classical optimization method, but it’s one that’s inspired by quantum mechanics.

In this new Google paper, they say that even though quantum Monte Carlo has the same asymptotic performance, the constant is way, way better for the D-Wave machine. The constant is about 100 million times better.

There are two huge issues that I would have with that. The first issue is that the problem instances where the comparison is being done are basically for the problem of simulating the D-Wave machine itself. There were $150 million that went into designing this special-purpose hardware for this D-Wave machine and making it as fast as possible. So in some sense, it’s no surprise that this special-purpose hardware could get a constant-factor speedup over a classical computer for the problem of simulating itself.

The qubits in their chip are organized in this particular graph topology. If you want to solve a practically important optimization problem, you need to map it somehow onto that topology. And there’s always a loss when you do that mapping. It seems entirely possible that that loss would kill a constant-factor advantage.

But the other point is that there’s yet another classical algorithm on the stage, which is Selby’s algorithm, which I think was first announced on my blog. It’s a local-search algorithm, but it’s one that is able to figure out that the qubits are organized into these clusters. What the Google paper finds is that Selby’s algorithm, which runs on a classical computer, totally outperforms the D-Wave machine on all the instances they tested.

If I know that these eight qubits form a cluster, and I should be thinking of them as one giant variable, then I just find the best setting of that variable, and I’m done. There are only 256 — 2 to the 8th — cases to check. That you can do pretty quickly.

If the clusters were 800 bits, then you wouldn’t be able to do this. On the other hand, building 800 qubits that are all talking to each other is a super-hard engineering problem. And even if you did [build those qubit clusters], it’s not at all clear that quantum annealing would be able to tunnel over that.

Remember, quantum annealing does best when there’s a tall, thin potential barrier. When you make the potential barrier wider, as would happen if you had 800-qubit clusters, then quantum annealing would have trouble as well.

We’re finally seeing clearly the logical consequences of the design decisions that D-Wave made 10, 15 years ago, which were, “Go for as many qubits as possible as quickly as possible. Don’t really worry about their lifetime, about their coherence. Don’t worry about error correction. Don’t worry about solving something where we’re confident theoretically that there’s a quantum speedup.”

I think of them as taking the dirty approach, and most of the others are trying to take the clean approach. Of course, it is possible that the dirty approach will get somewhere before the clean approach does. There are many precedents for that in the history of technology, where the dirty approach wins. But it hasn’t won yet.



Probing nonclassicality with matrices of phase-space distributions




Martin Bohmann1,2, Elizabeth Agudelo1, and Jan Sperling3

1Institute for Quantum Optics and Quantum Information – IQOQI Vienna, Austrian Academy of Sciences, Boltzmanngasse 3, 1090 Vienna, Austria
2QSTAR, INO-CNR, and LENS, Largo Enrico Fermi 2, I-50125 Firenze, Italy
3Integrated Quantum Optics Group, Applied Physics, Paderborn University, 33098 Paderborn, Germany

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


We devise a method to certify nonclassical features via correlations of phase-space distributions by unifying the notions of quasiprobabilities and matrices of correlation functions. Our approach complements and extends recent results that were based on Chebyshev’s integral inequality [65]. The method developed here correlates arbitrary phase-space functions at arbitrary points in phase space, including multimode scenarios and higher-order correlations. Furthermore, our approach provides necessary and sufficient nonclassicality criteria, applies to phase-space functions beyond $s$-parametrized ones, and is accessible in experiments. To demonstrate the power of our technique, the quantum characteristics of discrete- and continuous-variable, single- and multimode, as well as pure and mixed states are certified only employing second-order correlations and Husimi functions, which always resemble a classical probability distribution. Moreover, nonlinear generalizations of our approach are studied. Therefore, a versatile and broadly applicable framework is devised to uncover quantum properties in terms of matrices of phase-space distributions.

The intuitively accessible representation of quantum effects via quasiprobabilities, defying the nonnegativity requirement of classical probabilities, is a common technique to identify quantum features. However, the complexity of the reconstruction of such distributions increases with their sensitivity to uncover nonclassical signatures. Conversely, approaches based on correlation functions are experimentally available but less intuitive.

The method devised in our paper overcomes such disadvantageous features by unifying both aforementioned techniques. That is, quasiprobabilities can be correlated to unveil nonclassical properties even if the individual distributions are not sensitive enough to identify quantum properties. For example, it is shown that this necessary and sufficient approach applies to discrete- and continuous-variable, single- and multimode, pure and mixed states of light using phase-space distributions that can never become negative.

Thereby, we demonstrate the usefulness of our novel method to certify quantum characteristics in a practical manner that formthe basis for current and future quantum technologies.

► BibTeX data

► References

[1] E. Knill, R. Laflamme, and G. J. Milburn, A scheme for efficient quantum computation with linear optics, Nature (London) 409, 46 (2001).

[2] T. C. Ralph and P. K. Lam, A bright future for quantum communications, Nat. Photonics 3, 671 (2009).

[3] J. L. O’Brien, A. Furusawa, and J. Vučković, Photonic quantum technologies, Nat. Photonics 3, 687 (2009).

[4] M. Krenn, M. Malik, T. Scheidl, R. Ursin, and A. Zeilinger, Quantum communication with photons, in Optics in Our Time (Springer, Cham, 2016), pp. 455–482.

[5] S. Slussarenko and G. J. Pryde, Photonic quantum information processing: A concise review, Appl. Phys. Rev. 6, 041303 (2019).

[6] B. Yadin, F. C. Binder, J. Thompson, V. Narasimhachar, M. Gu, and M. S. Kim, Operational Resource Theory of Continuous-Variable Nonclassicality, Phys. Rev. X 8, 041038 (2018).

[7] H. Kwon, K. C. Tan, T. Volkoff, and H. Jeong, Nonclassicality as a Quantifiable Resource for Quantum Metrology, Phys. Rev. Lett. 122, 040503 (2019).

[8] F. Shahandeh, A. P. Lund, and T. C. Ralph, Quantum Correlations in Nonlocal Boson Sampling, Phys. Rev. Lett. 119, 120502 (2017).

[9] F. Shahandeh, A. P. Lund, and T. C. Ralph, Quantum correlations and global coherence in distributed quantum computing, Phys. Rev. A 99, 052303 (2019).

[10] M. S. Kim, W. Son, V. Bužek, and P. L. Knight, Entanglement by a beam splitter: Nonclassicality as a prerequisite for entanglement, Phys. Rev. A 65, 032323 (2002).

[11] W. Vogel and J. Sperling, Unified quantification of nonclassicality and entanglement, Phys. Rev. A 89, 052302 (2014).

[12] N. Killoran, F. E. S. Steinhoff, and M. B. Plenio, Converting Nonclassicality into Entanglement, Phys. Rev. Lett. 116, 080402 (2016).

[13] A. Miranowicz, M. Bartkowiak, X. Wang, Y.-x. Liu, and F. Nori, Testing nonclassicality in multimode fields: A unified derivation of classical inequalities, Phys. Rev. A 82, 013824 (2010).

[14] J. Sperling and W. Vogel, Quasiprobability distributions for quantum-optical coherence and beyond, Phys. Scr. 95, 034007 (2020).

[15] W. P. Schleich, Quantum Optics in Phase Space (Wiley-VCH, Berlin, 2001).

[16] C. Zachos, D. Fairlie, and T. Curtright, Quantum Mechanics in Phase Space (World Scientific, Singapore, 2005).

[17] D. D. Nolte, The tangled tale of phase space, Phys. Today 63, 33 (2010).

[18] H. Weyl, Quantenmechanik und Gruppentheorie, Z. Phys. 46, 1 (1927).

[19] E. Wigner, On the Quantum Correction For Thermodynamic Equilibrium, Phys. Rev. 40, 749 (1932).

[20] H. J. Groenewold, On the principles of elementary quantum mechanics, Physica 12, 405 (1946).

[21] J. Moyal, Quantum mechanics as a statistical theory, Math. Proc. Camb. Philos. Soc. 45, 99 (1949).

[22] J. Sperling and I. A. Walmsley, Quasiprobability representation of quantum coherence, Phys. Rev. A 97, 062327 (2018).

[23] R. J. Glauber, Coherent and Incoherent States of the Radiation Field, Phys. Rev. 131, 2766 (1963).

[24] E. C. G. Sudarshan, Equivalence of Semiclassical and Quantum Mechanical Descriptions of Statistical Light Beams, Phys. Rev. Lett. 10, 277 (1963).

[25] K. Husimi, Some formal properties of the density matrix, Proc. Phys. Math. Soc. Jpn. 22, 264 (1940).

[26] U. M. Titulaer and R. J. Glauber, Correlation functions for coherent fields, Phys. Rev. 140, B676 (1965).

[27] L. Mandel, Non-classical states of the electromagnetic field, Phys. Scr. T 12, 34 (1986).

[28] L. Cohen, Generalized Phase-Space Distribution Functions, J. Math. Phys. 7, 781 (1966).

[29] K. E. Cahill and R. J. Glauber, Density Operators and Quasiprobability Distributions, Phys. Rev. 177, 1882 (1969).

[30] G. S. Agarwal and E. Wolf, Calculus for Functions of Noncommuting Operators and General Phase-Space Methods in Quantum Mechanics. II. Quantum Mechanics in Phase Space, Phys. Rev. D 2, 2187 (1970).

[31] S. L. Braunstein and P. van Loock, Quantum information with continuous variables, Rev. Mod. Phys. 77, 513 (2005).

[32] C. Weedbrook, S. Pirandola, R. García-Patrón, N. J. Cerf, T. C. Ralph, J. H. Shapiro, and S. Lloyd, Gaussian quantum information, Rev. Mod. Phys. 84, 621 (2012).

[33] G. Adesso, S. Ragy, and A. R. Lee, Continuous Variable Quantum Information: Gaussian States and Beyond, Open Syst. Inf. Dyn. 21, 1440001 (2014).

[34] H. Grote, K. Danzmann, K. L. Dooley, R. Schnabel, J. Slutsky, and H. Vahlbruch, First Long-Term Application of Squeezed States of Light in a Gravitational-Wave Observatory, Phys. Rev. Lett. 110, 181101 (2013).

[35] M. Tse et al., Quantum-Enhanced Advanced LIGO Detectors in the Era of Gravitational-Wave Astronomy, Phys. Rev. Lett. 123, 231107 (2019).

[36] H. J. Carmichael and D. F. Walls, Proposal for the measurement of the resonant Stark effect by photon correlation techniques, J. Phys. B 9, L43 (1976).

[37] H. J. Kimble and L. Mandel, Theory of resonance fluorescence, Phys. Rev. A 13, 2123 (1976).

[38] H. J. Kimble, M. Dagenais, and L. Mandel, Photon Antibunching in Resonance Fluorescence, Phys. Rev. Lett. 39, 691 (1977).

[39] L. Mandel, Sub-Poissonian photon statistics in resonance fluorescence, Opt. Lett. 4, 205 (1979).

[40] X. T. Zou and L. Mandel, Photon-antibunching and sub-Poissonian photon statistics, Phys. Rev. A 41, 475 (1990).

[41] H. P. Yuen, Two-photon coherent states of the radiation field, Phys. Rev. A 13, 2226 (1976).

[42] D. F. Walls, Squeezed states of light, Nature (London) 306, 141 (1983).

[43] R. Loudon and P. Knight, Squeezed Light, J. Mod. Opt. 34, 709 (1987).

[44] G. Agarwal, Nonclassical characteristics of the marginals for the radiation field, Opt. Commun. 95, 109 (1993).

[45] G. S. Agarwal, Nonclassical statistics of fields in pair coherent states, J. Opt. Soc. Am. B 5, 1940 (1988).

[46] M. Hillery, Amplitude-squared squeezing of the electromagnetic field, Phys. Rev. A 36, 3796 (1987).

[47] D. N. Klyshko, The nonclassical light, Phys.-Uspekhi 39, 573 (1996).

[48] Á. Rivas and A. Luis, Nonclassicality of states and measurements by breaking classical bounds on statistics, Phys. Rev. A 79, 042105 (2009).

[49] M. Bohmann, L. Qi, W. Vogel, and M. Chekhova, Detection-device-independent verification of nonclassical light, Phys. Rev. Res. 1, 033178 (2019).

[50] G. S. Agarwal and K. Tara, Nonclassical character of states exhibiting no squeezing or sub-Poissonian statistics, Phys. Rev. A 46 485 (1992).

[51] E. Shchukin and W. Vogel, Inseparability Criteria for Continuous Bipartite Quantum States, Phys. Rev. Lett. 95, 230502 (2005).

[52] E. Shchukin and W. Vogel, Conditions for multipartite continuous-variable entanglement, Phys. Rev. A 74, 030302(R) (2006).

[53] A. Miranowicz, M. Piani, P. Horodecki, and R. Horodecki, Inseparability criteria based on matrices of moments, Phys. Rev. A 80, 052303 (2009).

[54] E. Shchukin and W. Vogel, Universal Measurement of Quantum Correlations of Radiation, Phys. Rev. Lett. 96, 200403 (2006).

[55] W. Vogel, Nonclassical states: An observable criterion, Phys. Rev. Lett. 84, 1849 (2000).

[56] T. Richter and W. Vogel, Nonclassicality of quantum states: A hierarchy of observable conditions, Phys. Rev. Lett. 89, 283601 (2002).

[57] A. I. Lvovsky and J. H. Shapiro, Nonclassical character of statistical mixtures of the single-photon and vacuum optical states, Phys. Rev. A 65, 033830 (2002).

[58] A. Zavatta, V. Parigi, and M. Bellini, Experimental nonclassicality of single-photon-added thermal light states, Phys. Rev. A 75, 052106 (2007).

[59] T. Kiesel, W. Vogel, B. Hage, J. DiGuglielmo, A. Samblowski, and R. Schnabel, Experimental test of nonclassicality criteria for phase-diffused squeezed states, Phys. Rev. A 79, 022122 (2009).

[60] A. Mari, K. Kieling, B. M. Nielsen, E. S. Polzik, and J. Eisert, Directly estimating nonclassicality, Phys. Rev. Lett. 106, 010403 (2011).

[61] J. Sperling, W. Vogel, and G. S. Agarwal, Operational definition of quantum correlations of light, Phys. Rev. A 94, 013833 (2016).

[62] S. Ryl, J. Sperling, E. Agudelo, M. Mraz, S. Köhnke, B. Hage, and W. Vogel, Unified nonclassicality criteria, Phys. Rev. A 92, 011801(R) (2015).

[63] S. Wallentowitz, R. L. de Matos Filho, and W. Vogel, Determination of entangled quantum states of a trapped atom, Phys. Rev. A 56, 1205 (1997).

[64] E. Agudelo, J. Sperling, L. S. Costanzo, M. Bellini, A. Zavatta, and W. Vogel, Conditional Hybrid Nonclassicality, Phys. Rev. Lett. 119, 120403 (2017).

[65] M. Bohmann and E. Agudelo, Phase-space inequalities beyond negativities, Phys. Rev. Lett. 124, 133601 (2020).

[66] E. Schrödinger, Der stetige Übergang von der Mikro- zur Makromechanik, Naturwiss. 14, 664 (1926).

[67] M. Hillery, Classical Pure States are Coherent States, Phys. Lett. 111, 409 (1985).

[68] M. Rezai, J. Sperling, and I. Gerhardt, What can single photons do what lasers cannot do?, Quantum Sci. Technol. 4, 045008 (2019).

[69] J. Sperling, Characterizing maximally singular phase-space distributions, Phys. Rev. A 94, 013814 (2016).

[70] W. Vogel and D.-G. Welsch, Quantum Optics (Wiley-VCH, Weinheim, 2006).

[71] E. Shchukin, T. Richter, and W. Vogel, Nonclassicality criteria in terms of moments, Phys. Rev. A 71, 011802(R) (2005).

[72] E. Shchukin and W. Vogel, Nonclassical moments and their measurement, Phys. Rev. A 72, 043808 (2005).

[73] R. A. Horn and C. R. Johnson, Matrix Analysis (Cambridge University Press, Cambridge, 1985).

[74] The determinant of a $3times 3$ matrix $X=left(begin{smallmatrix} mu & u & v u & U & chi v & chi & V end{smallmatrix}right)$ takes the general form $det X=[(mu U-u^2)(mu V-v^2)-(muchi-uv)^2]/​mu$, which is particularly interesting for the case $mu=1$ because it relates to cross-correlation functions.

[75] It is worth noting that, in quantum optics, the partial derivative with respect to a complex amplitude $alpha$ is given in terms of partial derivatives of the real and imaginary part, $partial_alpha=(partial_{mathrm{Re}(alpha)}+ipartial_{mathrm{Im}(alpha)})/​2$ and $partial_{alpha^ast}=(partial_{mathrm{Re}(alpha)}-ipartial_{mathrm{Im}(alpha)})/​2$.

[76] A. I. Lvovsky and M. G. Raymer, Continuous-variable optical quantum-state tomography, Rev. Mod. Phys. 81, 299 (2009).

[77] S. Wallentowitz and W. Vogel, Unbalanced homodyning for quantum state measurements, Phys. Rev. A 53, 4528 (1996).

[78] K. Banaszek, C. Radzewicz, K. Wódkiewicz, and J. S. Krasiński, Direct measurement of the Wigner function by photon counting, Phys. Rev. A 60, 674 (1999).

[79] P. L. Kelley and W. H. Kleiner, Theory of electromagnetic field measurement and photoelectron counting, Phys. Rev. 136, A316 (1964).

[80] J. Sperling et al., Detector-Agnostic Phase-Space Distributions, Phys. Rev. Lett. 124, 013605 (2020).

[81] G. S. Agarwal, M. O. Scully, and H. Walther, Phase narrowing a coherent state via repeated measures: only the no counts count, Phys. Scr. T 48, 128 (1993).

[82] For simplicity, we assume an equal dark-count rate $delta$ for both detectors. However, one can readily generalized this to different dark-count rates for each detector, as $det (M)<0$ remains a sufficient nonclassicality condition.

[83] M. Bohmann, J. Tiedau, T. Bartley, J. Sperling, C. Silberhorn, and W. Vogel, Incomplete Detection of Nonclassical Phase-Space Distributions, Phys. Rev. Lett. 120, 063607 (2018).

[84] T. Kiesel and W. Vogel, Nonclassicality filters and quasi-probabilities, Phys. Rev. A 82, 032107 (2010).

[85] T. Kiesel, W. Vogel, B. Hage, and R. Schnabel, Direct sampling of negative quasiprobabilities of a squeezed state, Phys. Rev. Lett. 107 113604 (2011).

[86] T. Richter, Pattern functions used in tomographic reconstruction of photon statistics revisited, Phys. Lett. A 211, 327 (1996).

[87] U. Leonhard, M. Munroe, T. Kiss, T. Richter, and M. G. Raymer, Sampling of photon statistics and density matrix using homodyne detection, Opt. Commun. 127, 144 (1996).

[88] E. Agudelo, J. Sperling, W. Vogel, S. Köhnke, M. Mraz, and B. Hage, Continuous sampling of the squeezed-state nonclassicality, Phys. Rev. A 92, 033837 (2015).

[89] N. Lütkenhaus and S. M. Barnett, Nonclassical effects in phase space, Phys. Rev. A 51, 3340 (1995).

[90] E. Agudelo, J. Sperling, and W. Vogel, Quasiprobabilities for multipartite quantum correlations of light, Phys. Rev. A 87, 033811 (2013).

[91] A. Ferraro and M. G. A. Paris, Nonclassicality Criteria from Phase-Space Representations and Information-Theoretical Constraints Are Maximally Inequivalent, Phys. Rev. Lett. 108, 260403 (2012).

[92] J. Sperling, M. Bohmann, W. Vogel, G. Harder, B. Brecht, V. Ansari, and C. Silberhorn, Uncovering Quantum Correlations with Time-Multiplexed Click Detection, Phys. Rev. Lett. 115, 023601 (2015).

[93] V. V. Dodonov, I. A. Malkin, and V. I. Manko, Even and odd coherent states and excitations of a singular oscillator, Physica (Amsterdam) 72, 597 (1974).

[94] W. Dür, G. Vidal, and J. I. Cirac, Three qubits can be entangled in two inequivalent ways, Phys. Rev. A 62, 062314 (2000).

[95] A. K. Jaiswal and G. S. Agarwal, Photoelectric detection with Two-Photon Absorption, J. Opt. Soc. Am. 59, 1446 (1969).

[96] The approximate POVM element in Eq. (43) has a decomposition in terms of lossy even photon-number operators with the expansion coefficients $[(2n)!/​n!](chi/​eta^2)^n$, which diverge for $ntoinfty$. Using the bounds $sqrt{2pi}m^{m+1/​2}e^{-m}leq m!leq e m^{m+1/​2}e^{-m}$, one finds the bound $chill eeta^2/​[4n]$ to satisfy $[(2n)!/​n!](chi/​eta^2)^nleq [e/​sqrtpi]([4nchi]/​[eeta^2])^nleq 1$ for correctly applying this approximation for upto $2n$ photons. Also note that for coherent states, one obtains the nonnegative function $langlealpha|hatPi|alpharangle=exp(-eta|alpha|^2+chi|alpha|^4)geq0$, representing the non-Gaussian integration kernel $Omega$.

[97] N. Biagi, M. Bohmann, E. Agudelo, M. Bellini, and A. Zavatta, Experimental certification of nonclassicality via phase-space inequalities, arXiv:2010.00259 [quant-ph].

[98] R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, Quantum entanglement, Rev. Mod. Phys. 81, 865 (2009).

[99] K. C. Tan, S. Choi, and H. Jeong, Negativity of Quasiprobability Distributions as a Measure of Nonclassicality, Phys. Rev. Lett. 124, 110404 (2020).

[100] J. Park, J. Lee, and H. Nha Verifying nonclassicality beyond negativity in phase space, arXiv:2005.05739 [quant-ph]; J. Park and H. Nha, Efficient and faithful criteria on nonclassicality for continuous variables, presented at 15th International Conference on Squeezed States and Uncertainty Relations, Jeju, South Korea, 2017.

Cited by

[1] Jiyong Park, Jaehak Lee, and Hyunchul Nha, “Verifying nonclassicality beyond negativity in phase space”, arXiv:2005.05739.

[2] Nicola Biagi, Martin Bohmann, Elizabeth Agudelo, Marco Bellini, and Alessandro Zavatta, “Experimental certification of nonclassicality via phase-space inequalities”, arXiv:2010.00259.

The above citations are from SAO/NASA ADS (last updated successfully 2020-10-16 02:17:01). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref’s cited-by service no data on citing works was found (last attempt 2020-10-16 02:16:59).


Continue Reading


A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time




Jonathan Allcock and Chang-Yu Hsieh

Tencent Quantum Laboratory

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


We propose a quantum algorithm for training nonlinear support vector machines (SVM) for feature space learning where classical input data is encoded in the amplitudes of quantum states. Based on the classical SVM-perf algorithm of Joachims [1], our algorithm has a running time which scales linearly in the number of training examples $m$ (up to polylogarithmic factors) and applies to the standard soft-margin $ell_1$-SVM model. In contrast, while classical SVM-perf has demonstrated impressive performance on both linear and nonlinear SVMs, its efficiency is guaranteed only in certain cases: it achieves linear $m$ scaling only for linear SVMs, where classification is performed in the original input data space, or for the special cases of low-rank or shift-invariant kernels. Similarly, previously proposed quantum algorithms either have super-linear scaling in $m$, or else apply to different SVM models such as the hard-margin or least squares $ell_2$-SVM which lack certain desirable properties of the soft-margin $ell_1$-SVM model. We classically simulate our algorithm and give evidence that it can perform well in practice, and not only for asymptotically large data sets.

► BibTeX data

► References

[1] Thorsten Joachims. Training linear SVMs in linear time. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 217–226. ACM, 2006. 10.1145/​1150402.1150429.

[2] Bernhard E Boser, Isabelle M Guyon, and Vladimir N Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the fifth annual workshop on Computational learning theory, pages 144–152. ACM, 1992. 10.1145/​130385.130401.

[3] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine Learning, 20 (3): 273–297, 1995. 10.1023/​A:1022627411411.

[4] Christopher JC Burges. A tutorial on support vector machines for pattern recognition. Data mining and knowledge discovery, 2 (2): 121–167, 1998. 10.1023/​A:1009715923555.

[5] Michael C Ferris and Todd S Munson. Interior-point methods for massive support vector machines. SIAM Journal on Optimization, 13 (3): 783–804, 2002. 10.1137/​S1052623400374379.

[6] Olvi L Mangasarian and David R Musicant. Lagrangian support vector machines. Journal of Machine Learning Research, 1 (Mar): 161–177, 2001. 10.1162/​15324430152748218.

[7] S Sathiya Keerthi and Dennis DeCoste. A modified finite Newton method for fast solution of large scale linear SVMs. Journal of Machine Learning Research, 6 (Mar): 341–361, 2005.

[8] Shai Shalev-Shwartz, Yoram Singer, Nathan Srebro, and Andrew Cotter. Pegasos: Primal Estimated sub-GrAdient SOlver for SVM. Mathematical programming, 127 (1): 3–30, 2011. 10.1145/​1273496.1273598.

[9] Bernhard Scholkopf and Alexander J Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2001.

[10] Christopher KI Williams and Matthias Seeger. Using the Nyström method to speed up kernel machines. In Advances in Neural Information Processing Systems, pages 682–688, 2001.

[11] Shai Fine and Katya Scheinberg. Efficient SVM training using low-rank kernel representations. Journal of Machine Learning Research, 2 (Dec): 243–264, 2001.

[12] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, pages 1177–1184, 2008.

[13] Thorsten Joachims. Making large-scale SVM learning practical. In Advances in Kernel Methods-Support Vector Learning. MIT-press, 1999.

[14] John C Platt. Fast training of support vector machines using sequential minimal optimization. MIT press, 1999.

[15] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2 (3): 27, 2011. 10.1145/​1961189.1961199.

[16] Ronan Collobert and Samy Bengio. SVMTorch: Support vector machines for large-scale regression problems. Journal of Machine Learning Research, 1 (Feb): 143–160, 2001. 10.1162/​15324430152733142.

[17] Thorsten Joachims and Chun-Nam John Yu. Sparse kernel SVMs via cutting-plane training. Machine Learning, 76 (2-3): 179–193, 2009. 10.1007/​s10994-009-5126-6.

[18] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Physical Review Letters, 113 (13): 130503, 2014. 10.1103/​PhysRevLett.113.130503.

[19] Vojtěch Havlíček, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta. Supervised learning with quantum-enhanced feature spaces. Nature, 567 (7747): 209–212, 2019. 10.1038/​s41586-019-0980-2.

[20] Maria Schuld and Nathan Killoran. Quantum machine learning in feature hilbert spaces. Physical Review Letters, 122 (4): 040504, 2019. 10.1103/​PhysRevLett.122.040504.

[21] Iordanis Kerenidis, Anupam Prakash, and Dániel Szilágyi. Quantum algorithms for second-order cone programming and support vector machines. arXiv preprint arXiv:1908.06720, 2019.

[22] Tomasz Arodz and Seyran Saeedi. Quantum sparse support vector machines. arXiv preprint arXiv:1902.01879, 2019.

[23] Tongyang Li, Shouvanik Chakrabarti, and Xiaodi Wu. Sublinear quantum algorithms for training linear and kernel-based classifiers. In Proceedings of the 36th International Conference on Machine Learning. PMLR, 2019.

[24] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Physical Review Letters, 100 (16): 160501, 2008. 10.1103/​PhysRevLett.100.160501.

[25] Anupam Prakash. Quantum algorithms for linear algebra and machine learning. PhD thesis, UC Berkeley, 2014.

[26] Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 217–228, 2019. 10.1145/​3313276.3316310.

[27] Ewin Tang. Quantum-inspired classical algorithms for principal component analysis and supervised clustering. arXiv preprint arXiv:1811.00414, 2018.

[28] András Gilyén, Seth Lloyd, and Ewin Tang. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. arXiv preprint arXiv:1811.04909, 2018.

[29] Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan, and Seth Lloyd. Quantum-inspired algorithms in practice. Quantum, 4: 307, 2020. 10.22331/​q-2020-08-13-307.

[30] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004. 10.1017/​CBO9780511804441.

[31] Ioannis Tsochantaridis, Thorsten Joachims, Thomas Hofmann, and Yasemin Altun. Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research, 6 (Sep): 1453–1484, 2005.

[32] Jonathan Allcock, Chang-Yu Hsieh, Iordanis Kerenidis, and Shengyu Zhang. Quantum algorithms for feedforward neural networks. ACM Transactions on Quantum Computing, 1 (1), 2020. 10.1145/​3411466.

[33] Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. 10.4230/​LIPIcs.ITCS.2017.49.

[34] Mario Motta, Chong Sun, Adrian TK Tan, Matthew J O’Rourke, Erika Ye, Austin J Minnich, Fernando GSL Brandão, and Garnet Kin-Lic Chan. Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution. Nature Physics, 16 (2): 205–210, 2020. 10.1038/​s41567-019-0704-4.

[35] Chang-Yu Hsieh, Qiming Sun, Shengyu Zhang, and Chee Kong Lee. Unitary-coupled restricted boltzmann machine ansatz for quantum simulations. https:/​/​​abs/​1912.02988, 2019.

[36] Jonathan Romero, Jonathan P Olson, and Alan Aspuru-Guzik. Quantum autoencoders for efficient compression of quantum data. Quantum Science and Technology, 2 (4): 045001, 2017. 10.1088/​2058-9565/​aa8072.

[37] Edward Farhi and Hartmut Neven. Classification with quantum neural networks on near term processors. arXiv preprint arXiv:1802.06002, 2018.

[38] Seth Lloyd, Maria Schuld, Aroosa Ijaz, Josh Isaac, and Nathan Killoran. Quantum embeddings for machine learning. arXiv preprint arXiv:2001.03622, 2020.

[39] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305: 53–74, 2002.

Cited by


Continue Reading


Yao.jl: Extensible, Efficient Framework for Quantum Algorithm Design




Xiu-Zhe Luo1,2,3,4, Jin-Guo Liu1, Pan Zhang2, and Lei Wang1,5

1Institute of Physics, Chinese Academy of Sciences, Beijing 100190, China
2Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China
3Department of Physics and Astronomy, University of Waterloo, Waterloo N2L 3G1, Canada
4Perimeter Institute for Theoretical Physics, Waterloo, Ontario N2L 2Y5, Canada
5Songshan Lake Materials Laboratory, Dongguan, Guangdong 523808, China

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


We introduce $texttt{Yao}$, an extensible, efficient open-source framework for quantum algorithm design. $texttt{Yao}$ features generic and differentiable programming of quantum circuits. It achieves state-of-the-art performance in simulating small to intermediate-sized quantum circuits that are relevant to near-term applications. We introduce the design principles and critical techniques behind $texttt{Yao}$. These include the quantum block intermediate representation of quantum circuits, a builtin automatic differentiation engine optimized for reversible computing, and batched quantum registers with GPU acceleration. The extensibility and efficiency of $texttt{Yao}$ help boost innovation in quantum algorithm design.

► BibTeX data

► References

[1] John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2: 79, 2018. 10.22331/​q-2018-08-06-79.

[2] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien. A variational eigenvalue solver on a photonic quantum processor. Nature communications, 5: 4213, 2014a. 10.1038/​ncomms5213.

[3] Dave Wecker, Matthew B Hastings, and Matthias Troyer. Progress towards practical quantum variational algorithms. Physical Review A, 92 (4): 042303, 2015. 10.1103/​physreva.92.042303.

[4] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik. The theory of variational hybrid quantum-classical algorithms. New Journal of Physics, 18 (2): 023023, 2016. 10.1088/​1367-2630/​18/​2/​023023.

[5] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014.

[6] Edward Farhi and Hartmut Neven. Classification with Quantum Neural Networks on Near Term Processors. arXiv e-prints, art. arXiv:1802.06002, February 2018.

[7] Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa, and Keisuke Fujii. Quantum circuit learning. Physical Review A, 98 (3): 032309, 2018. 10.1103/​physreva.98.032309.

[8] Marcello Benedetti, Delfina Garcia-Pintos, Oscar Perdomo, Vicente Leyton-Ortega, Yunseong Nam, and Alejandro Perdomo-Ortiz. A generative modeling approach for benchmarking and training shallow quantum circuits. npj Quantum Information, 5 (1), May 2019a. ISSN 2056-6387. 10.1038/​s41534-019-0157-8. URL http:/​/​​10.1038/​s41534-019-0157-8.

[9] Jin-Guo Liu and Lei Wang. Differentiable learning of quantum circuit born machines. Physical Review A, 98 (6): 062324, 2018. 10.1103/​physreva.98.062324.

[10] Peter JJ O’Malley et al. Scalable quantum simulation of molecular energies. Physical Review X, 6 (3): 031007, 2016. 10.21236/​ada387360.

[11] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature, 549 (7671): 242, 2017a. 10.1038/​nature23879. URL https:/​/​​articles/​nature23879.

[12] Vojtěch Havlíček, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta. Supervised learning with quantum-enhanced feature spaces. Nature, 567 (7747): 209, 2019. 10.1038/​s41586-019-0980-2.

[13] Daiwei Zhu et al. Training of quantum circuits on a hybrid quantum computer. Science Advances, 5 (10): eaaw9918, 2019. 10.1126/​sciadv.aaw9918.

[14] G. Pagano, A. Bapat, P. Becker, K. S. Collins, A. De, P. W. Hess, H. B. Kaplan, A. Kyprianidis, W. L. Tan, C Baldwin, L T Brady, A Deshpande, F Liu, S Jordan, A V Gorshkov, and C Monroe. Quantum Approximate Optimization with a Trapped-Ion Quantum Simulator. 2019. URL http:/​/​​abs/​1906.02700.

[15] Vicente Leyton-Ortega, Alejandro Perdomo-Ortiz, and Oscar Perdomo. Robust implementation of generative modeling with parametrized quantum circuits. arXiv preprint arXiv:1901.08047, 2019.

[16] Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nat. Commun., 9 (1): 4812, 2018. ISSN 2041-1723. 10.1038/​s41467-018-07090-4. URL https:/​/​​10.1038/​s41467-018-07090-4.

[17] Tim Besard, Christophe Foket, and Bjorn De Sutter. Effective extensible programming: Unleashing julia on gpus. CoRR, abs/​1712.03112, 2017. 10.1109/​tpds.2018.2872064. URL http:/​/​​abs/​1712.03112.

[18] Guillermo García-Pérez, Matteo A. C. Rossi, and Sabrina Maniscalco. Ibm q experience as a versatile experimental testbed for simulating open quantum systems, 2019. URL https:/​/​​abs/​1906.07099. 10.1038/​s41534-019-0235-y.

[19] Differentiable Programming. https:/​/​​wiki/​Differentiable_programming, a.

[20] Karpathy, Andrej. Software 2.0. https:/​/​​@karpathy/​software-2-0-a64152b37c35.

[21] Tianqi Chen et al. Mxnet: A flexible and efficient machine learning library for heterogeneous distributed systems. arXiv preprint arXiv:1512.01274, 2015.

[22] Martín Abadi et al. Tensorflow: A system for large-scale machine learning. In 12th ${$USENIX$}$ Symposium on Operating Systems Design and Implementation (${$OSDI$}$ 16), pages 265–283, 2016.

[23] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d’ Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024–8035. Curran Associates, Inc., 2019. https:/​/​​abs/​1912.01703.

[24] Dougal Maclaurin, David Duvenaud, and Ryan P Adams. Autograd: Effortless gradients in numpy. In ICML 2015 AutoML Workshop, volume 238, 2015.

[25] Michael Innes, Elliot Saba, Keno Fischer, Dhairya Gandhi, Marco Concetto Rudilosso, Neethu Mariya Joy, Tejan Karmali, Avik Pal, and Viral Shah. Fashionable modelling with flux. CoRR, abs/​1811.01457, 2018. URL http:/​/​​abs/​1811.01457.

[26] Mike Innes, Alan Edelman, Keno Fischer, Chris Rackauckus, Elliot Saba, Viral B Shah, and Will Tebbutt. Zygote: A differentiable programming system to bridge machine learning and scientific computing. arXiv preprint arXiv:1907.07587, 2019.

[27] C. H. Bennett. Logical reversibility of computation. IBM Journal of Research and Development, 17 (6): 525–532, Nov 1973. ISSN 0018-8646. 10.1147/​rd.176.0525.

[28] Jin-Guo Liu, Yi-Hong Zhang, Yuan Wan, and Lei Wang. Variational quantum eigensolver with fewer qubits. Phys. Rev. Research, 1: 023025, Sep 2019a. 10.1103/​PhysRevResearch.1.023025. URL https:/​/​​doi/​10.1103/​PhysRevResearch.1.023025.

[29] Alexander S Green, Peter LeFanu Lumsdaine, Neil J Ross, Peter Selinger, and Benoı̂t Valiron. Quipper: a scalable quantum programming language. In ACM SIGPLAN Notices, volume 48, pages 333–342. ACM, 2013. 10.1145/​2491956.2462177.

[30] Damian S Steiger, Thomas Häner, and Matthias Troyer. Projectq: an open source software framework for quantum computing. arXiv preprint arXiv:1612.08091, 2016. 10.22331/​q-2018-01-31-49.

[31] Krysta Svore, Martin Roetteler, Alan Geller, Matthias Troyer, John Azariah, Christopher Granade, Bettina Heim, Vadym Kliuchnikov, Mariia Mykhailova, and Andres Paz. Q#: Enabling scalable quantum computing and development with a high-level dsl. Proceedings of the Real World Domain Specific Languages Workshop 2018 on – RWDSL2018, 2018. 10.1145/​3183895.3183901. URL http:/​/​​10.1145/​3183895.3183901.

[32] Cirq: A Python framework for creating, editing, and invoking noisy intermediate scale quantum (NISQ) circuits. https:/​/​​quantumlib/​Cirq.

[33] qulacs: Variational Quantum Circuit Simulator for Quantum Computation Research. https:/​/​​qulacs/​qulacs.

[34] Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, and Nathan Killoran. Pennylane: Automatic differentiation of hybrid quantum-classical computations. arXiv preprint arXiv:1811.04968, 2018.

[35] Héctor Abraham et al. Qiskit: An open-source framework for quantum computing, 2019.

[36] Tyson Jones, Anna Brown, Ian Bush, and Simon C. Benjamin. Quest and high performance simulation of quantum computers. Scientific Reports, 9 (1), Jul 2019. ISSN 2045-2322. 10.1038/​s41598-019-47174-9. URL http:/​/​​10.1038/​s41598-019-47174-9.

[37] Mark Fingerhuth, Tomáš Babej, and Peter Wittek. Open source software in quantum computing. PloS one, 13 (12): e0208561, 2018. 10.1371/​journal.pone.0208561.

[38] Ryan LaRose. Overview and Comparison of Gate Level Quantum Software Platforms. Quantum, 3: 130, March 2019. ISSN 2521-327X. 10.22331/​q-2019-03-25-130. URL https:/​/​​10.22331/​q-2019-03-25-130.

[39] Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini. Parameterized quantum circuits as machine learning models. Quantum Science and Technology, 4 (4): 043001, nov 2019b. 10.1088/​2058-9565/​ab4eb5. URL https:/​/​​10.1088.

[40] J. Bezanson. “Why is Julia fast? Can it be faster?” 2015, JuliaCon India. https:/​/​​watch?v=xUP3cSKb8sI.

[41] Jeff Bezanson, Stefan Karpinski, Viral B Shah, and Alan Edelman. Julia: A fast dynamic language for technical computing. arXiv preprint arXiv:1209.5145, 2012.

[42] Jarrod R. McClean et al. Openfermion: The electronic structure package for quantum computers, jun 2020. URL https:/​/​​10.1088/​2058-9565/​ab8ebc.

[43] D Coppersmith. An approximate fourier transform useful in quantum computing. Technical report, Technical report, IBM Research Division, 1994. https:/​/​​abs/​quant-ph/​0201067.

[44] Artur Ekert and Richard Jozsa. Quantum computation and shor’s factoring algorithm. Reviews of Modern Physics, 68 (3): 733, 1996. 10.1103/​RevModPhys.68.733.

[45] Richard Jozsa. Quantum algorithms and the fourier transform. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454 (1969): 323–337, 1998. 10.1098/​rspa.1998.0163.

[46] Peter J Karalekas, Nikolas A Tezak, Eric C Peterson, Colm A Ryan, Marcus P da Silva, and Robert S Smith. A quantum-classical cloud platform optimized for variational hybrid algorithms. Quantum Science and Technology, 5 (2): 024003, apr 2020. 10.1088/​2058-9565/​ab7559. URL https:/​/​​10.1088.

[47] Krylovkit.jl: Krylov methods for linear problems, eigenvalues, singular values and matrix functions. https:/​/​​Jutho/​KrylovKit.jl.

[48] Christopher Rackauckas and Qing Nie. Differentialequations.jl – a performant and feature-rich ecosystem for solving differential equations in julia. The Journal of Open Research Software, 5 (1), 2017. 10.5334/​jors.151. URL https:/​/​​details/​publication/​pub.1085583166 and http:/​/​​articles/​10.5334/​jors.151/​galley/​245/​download/​. Exported from https:/​/​ on 2019/​05/​05.

[49] Atilim Gunes Baydin, Barak A Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. Automatic differentiation in machine learning: a survey. Journal of machine learning research, 18 (153), 2018. https:/​/​​abs/​1502.05767.

[50] Andreas Griewank and Andrea Walther. Evaluating Derivatives. Society for Industrial and Applied Mathematics, jan 2008. 10.1137/​1.9780898717761. URL https:/​/​​10.1137.

[51] Aidan N Gomez, Mengye Ren, Raquel Urtasun, and Roger B Grosse. The reversible residual network: Backpropagation without storing activations. In Advances in neural information processing systems, pages 2214–2224, 2017.

[52] Tian Qi Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. In Advances in neural information processing systems, pages 6571–6583, 2018a.

[53] Akira Hirose. Complex-valued neural networks: theories and applications, volume 5. World Scientific, 2003. 10.1142/​5345.

[54] Mike Giles. An extended collection of matrix derivative results for forward and reverse mode algorithmic differentiation. Technical report, 2008. URL https:/​/​​gilesm/​files/​NA-08-01.pdf.

[55] Jin-Guo Liu, Liang Mao, Pan Zhang, and Lei Wang. Solving quantum statistical mechanics with variational autoregressive networks and quantum circuits. 2019b. URL http:/​/​​abs/​1912.11381.

[56] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L O’brien. A variational eigenvalue solver on a photonic quantum processor. Nat. Commun., 5: 4213, 2014b. 10.1038/​ncomms5213. URL https:/​/​​articles/​ncomms5213.

[57] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta. Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. Nature, 549 (7671): 242, 2017b. 10.1038/​nature23879.

[58] Gavin E Crooks. Gradients of parameterized quantum gates using the parameter-shift rule and gate decomposition. URL https:/​/​​abs/​1905.13311.

[59] Jun Li, Xiaodong Yang, Xinhua Peng, and Chang-Pu Sun. Hybrid quantum-classical approach to quantum optimal control. Phys. Rev. Lett., 118: 150503, Apr 2017. 10.1103/​physrevlett.118.150503. URL https:/​/​​doi/​10.1103/​PhysRevLett.118.150503.

[60] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran. Evaluating analytic gradients on quantum hardware. Phys. Rev. A, 99 (3): 032331, 2019. ISSN 24699934. 10.1103/​PhysRevA.99.032331.

[61] Ken M Nakanishi, Keisuke Fujii, and Synge Todo. Sequential minimal optimization for quantum-classical hybrid algorithms. 10.21236/​ada212800. URL https:/​/​​abs/​1903.12166.

[62] Shakir Mohamed, Mihaela Rosca, Michael Figurnov, and Andriy Mnih. Monte carlo gradient estimation in machine learning. URL https:/​/​​abs/​1906.10652.

[63] Chun-Liang Li, Wei-Cheng Chang, Yu Cheng, Yiming Yang, and Barnabás Póczos. MMD GAN: Towards Deeper Understanding of Moment Matching Network. URL http:/​/​​abs/​1705.08584.

[64] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13 (Mar): 723–773, 2012. URL http:/​/​​papers/​v13/​gretton12a.html.

[65] Michael A Nielsen and Isaac L Chuang. Quantum Computation and Quantum Information. Cambridge university press, 2010. 10.1017/​cbo9780511976667.016.

[66] William James Huggins, Piyush Patil, Bradley Mitchell, K Birgitta Whaley, and Miles Stoudenmire. Towards quantum machine learning with tensor networks. Quantum Science and Technology, 2018. 10.1088/​2058-9565/​aaea94.

[67] Frederica Darema, David A George, V Alan Norton, and Gregory F Pfister. A single-program-multiple-data computational model for epex/​fortran. Parallel Computing, 7 (1): 11–24, 1988. 10.1016/​0167-8191(88)90094-4.

[68] Statically sized arrays for Julia. https:/​/​​JuliaArrays/​StaticArrays.jl.

[69] A luxury sparse matrix package for julia. https:/​/​​QuantumBFS/​LuxurySparse.jl.

[70] Thomas Häner and Damian S Steiger. 0.5 petabyte simulation of a 45-qubit quantum circuit. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, page 33. ACM, 2017. 10.1145/​3126908.3126947.

[71] Igor L Markov and Yaoyun Shi. Simulating quantum computation by contracting tensor networks. SIAM Journal on Computing, 38 (3): 963–981, 2008. 10.1137/​050644756.

[72] Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh, Thomas Magerlein, Edgar Solomonik, and Robert Wisnieff. Breaking the 49-qubit barrier in the simulation of quantum circuits. arXiv preprint arXiv:1710.05867, 2017.

[73] Fang Zhang et al. Alibaba cloud quantum development kit: Large-scale classical simulation of quantum circuits. arXiv preprint arXiv:1907.11217, 2019.

[74] Pyquest-cffi: A python interface to the quest quantum simulator (cffi based). https:/​/​​HQSquantumsimulations/​PyQuEST-cffi.

[75] PennyLane is a cross-platform Python library for quantum machine learning, automatic differentiation, and optimization of hybrid quantum-classical computations. https:/​/​​XanaduAI/​pennylane, a.

[76] Review of PennyLane benchmark. https:/​/​​Roger-luo/​quantum-benchmarks/​pull/​7, b.

[77] Aer is a high performance simulator for quantum circuits that includes noise models. https:/​/​​Qiskit/​qiskit-aer, a.

[78] Terra provides the foundations for Qiskit. It allows the user to write quantum circuits easily, and takes care of the constraints of real hardware. https:/​/​​Qiskit/​qiskit-terra, b.

[79] py.test fixture for benchmarking code. https:/​/​​ionelmc/​pytest-benchmark.

[80] Jiahao Chen and Jarrett Revels. Robust benchmarking in noisy environments. arXiv preprint arXiv:1608.04295, 2016.

[81] Benchmarking Quantum Circuit Emulators For Your Daily Research Usage. https:/​/​​Roger-luo/​quantum-benchmarks.

[82] Frank Arute et al. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779): 505–510, 2019. 10.1038/​s41586-019-1666-5.

[83] CuYao.jl: CUDA extension for Yao.jl. https:/​/​​QuantumBFS/​CuYao.jl.

[84] Jinfeng Zeng, Yufeng Wu, Jin-Guo Liu, Lei Wang, and Jiangping Hu. Learning and inference on generative adversarial quantum circuits. Physical Review A, 99 (5): 052306, 2019. 10.1103/​physreva.99.052306.

[85] Weishi Wang, Jin-Guo Liu, and Lei Wang. A variational quantum state compression algorithm. to appear.

[86] Vivek V. Shende, Igor L. Markov, and Stephen S. Bullock. Minimal universal two-qubit controlled-not-based circuits. Phys. Rev. A, 69: 062321, Jun 2004. 10.1103/​PhysRevA.69.062321. URL https:/​/​​doi/​10.1103/​PhysRevA.69.062321.

[87] Michael Innes. Don’t unroll adjoint: Differentiating ssa-form programs. CoRR, abs/​1810.07951, 2018. URL http:/​/​​abs/​1810.07951.

[88] Andrew W Cross, Lev S Bishop, John A Smolin, and Jay M Gambetta. Open quantum assembly language. arXiv preprint arXiv:1707.03429, 2017.

[89] Xiang Fu et al. eqasm: An executable quantum instruction set architecture. In 2019 IEEE International Symposium on High Performance Computer Architecture (HPCA), pages 224–237. IEEE, 2019. 10.1109/​hpca.2019.00040.

[90] Robert S Smith, Michael J Curtis, and William J Zeng. A practical quantum instruction set architecture. arXiv preprint arXiv:1608.03355, 2016.

[91] RBNF: A DSL for modern parsing. https:/​/​​thautwarm/​RBNF.jl.

[92] Bidirectional transformation between Yao Quantum Block IR and QASM. https:/​/​​QuantumBFS/​YaoQASM.jl, a.

[93] YaoLang: The next DSL for Yao and quantum programs. https:/​/​​QuantumBFS/​YaoLang.jl, b.

[94] ZXCalculus.jl: An implementation of ZX-calculus in Julia. https:/​/​​QuantumBFS/​ZXCalculus.jl, c.

[95] Aleks Kissinger and John van de Wetering. PyZX: Large Scale Automated Diagrammatic Reasoning. In Bob Coecke and Matthew Leifer, editors, Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, USA., 10-14 June 2019, volume 318 of Electronic Proceedings in Theoretical Computer Science, pages 229–241. Open Publishing Association, 2020. 10.4204/​EPTCS.318.14.

[96] Raban Iten, David Sutter, and Stefan Woerner. Efficient template matching in quantum circuits. arXiv preprint arXiv:1909.05270, 2019.

[97] Dmitri Maslov, Gerhard W Dueck, D Michael Miller, and Camille Negrevergne. Quantum circuit simplification and level compaction. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 27 (3): 436–444, 2008. 10.1109/​tcad.2007.911334.

[98] Aleks Kissinger and John van de Wetering. Reducing T-count with the ZX-calculus. arXiv preprint arXiv:1903.10477, 2019. 10.1103/​PhysRevA.102.022406.

[99] Piotr Gawron, Dariusz Kurzyk, and Łukasz Pawela. Quantuminformation.jl—a julia package for numerical computation in quantum information theory. PLOS ONE, 13 (12): e0209358, Dec 2018. ISSN 1932-6203. 10.1371/​journal.pone.0209358. URL http:/​/​​10.1371/​journal.pone.0209358.

[100] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, and Hartmut Neven. Simulation of low-depth quantum circuits as complex undirected graphical models. arXiv preprint arXiv:1712.05384, 2017.

[101] Jianxin Chen, Fang Zhang, Mingcheng Chen, Cupjin Huang, Michael Newman, and Yaoyun Shi. Classical simulation of intermediate-size quantum circuits. arXiv preprint arXiv:1805.01450, 2018b.

[102] Chu Guo, Yong Liu, Min Xiong, Shichuan Xue, Xiang Fu, Anqi Huang, Xiaogang Qiang, Ping Xu, Junhua Liu, Shenggen Zheng, He-Liang Huang, Mingtang Deng, Dario Poletti, Wan-Su Bao, and Junjie Wu. General-purpose quantum circuit simulator with projected entangled-pair states and the quantum supremacy frontier. Phys. Rev. Lett., 123: 190501, Nov 2019. 10.1103/​PhysRevLett.123.190501. URL https:/​/​​doi/​10.1103/​PhysRevLett.123.190501.

[103] Feng Pan, Pengfei Zhou, Sujie Li, and Pan Zhang. Contracting arbitrary tensor networks: general approximate algorithm and applications in graphical models and quantum circuit simulations. Phys. Rev. Lett., 2020. 10.1103/​PhysRevLett.125.060503.

[104] Edwin Stoudenmire and David J Schwab. Supervised learning with tensor networks. pages 4799–4807, 2016. URL http:/​/​​paper/​6211-supervised-learning-with-tensor-networks.pdf.

[105] Zhao-Yu Han, Jun Wang, Heng Fan, Lei Wang, and Pan Zhang. Unsupervised generative modeling using matrix product states. Phys. Rev. X, 8: 031012, Jul 2018. 10.1103/​PhysRevX.8.031012. URL https:/​/​​doi/​10.1103/​PhysRevX.8.031012.

[106] Song Cheng, Lei Wang, Tao Xiang, and Pan Zhang. Tree tensor networks for generative modeling. Phys. Rev. B, 99: 155131, Apr 2019. 10.1103/​PhysRevB.99.155131. URL https:/​/​​doi/​10.1103/​PhysRevB.99.155131.

[107] Ivan Glasser, Ryan Sweke, Nicola Pancotti, Jens Eisert, and Ignacio Cirac. Expressive power of tensor-network factorizations for probabilistic modeling. In Advances in Neural Information Processing Systems, pages 1496–1508, 2019.

[108] Tai-Danae Bradley, E M Stoudenmire, and John Terilla. Modeling sequences with quantum states: a look under the hood. Machine Learning: Science and Technology, 1 (3): 035008, jul 2020. 10.1088/​2632-2153/​ab8731. URL https:/​/​​10.1088.

[109] YaoTensorNetwork: Dump a quantum circuit in Yao to a tensor network graph model. https:/​/​​QuantumBFS/​YaoTensorNetwork.jl, d.

[110] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, and Hartmut Neven. Characterizing quantum supremacy in near-term devices. Nature Physics, 14 (6): 595, 2018. 10.1038/​s41567-018-0124-x.

[111] Miriam Backens. The ZX-calculus is complete for stabilizer quantum mechanics. New Journal of Physics, 16 (9): 093021, sep 2014. 10.1088/​1367-2630/​16/​9/​093021. URL https:/​/​​10.1088.

[112] Multi-language suite for high-performance solvers of differential equations. https:/​/​​JuliaDiffEq/​DifferentialEquations.jl, b.

[113] General Permutation Matrix. https:/​/​​wiki/​Generalized_permutation_matrix.

[114] Thomas Häner, Damian S Steiger, Mikhail Smelyanskiy, and Matthias Troyer. High performance emulation of quantum circuits. In SC’16: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 866–874. IEEE, 2016. 10.1109/​sc.2016.73.

[115] Ryan LaRose, Arkin Tikku, Étude O’Neel-Judy, Lukasz Cincio, and Patrick J. Coles. Variational quantum state diagonalization. npj Quantum Information, 5 (1), Jun 2019. ISSN 2056-6387. 10.1038/​s41534-019-0167-6. URL http:/​/​​10.1038/​s41534-019-0167-6.

[116] Cristina Cirstoiu, Zoe Holmes, Joseph Iosue, Lukasz Cincio, Patrick J. Coles, and Andrew Sornborger. Variational fast forwarding for quantum simulation beyond the coherence time, 2019. 10.1038/​s41534-020-00302-0.

[117] Lukasz Cincio, Yiğit Subaşı, Andrew T Sornborger, and Patrick J Coles. Learning the quantum algorithm for state overlap. New Journal of Physics, 20 (11): 113022, Nov 2018. ISSN 1367-2630. 10.1088/​1367-2630/​aae94a. URL http:/​/​​10.1088/​1367-2630/​aae94a.

[118] Xiaoguang Wang, Zhe Sun, and Z. D. Wang. Operator fidelity susceptibility: An indicator of quantum criticality. Physical Review A, 79 (1), Jan 2009. ISSN 1094-1622. 10.1103/​physreva.79.012105. URL http:/​/​​10.1103/​PhysRevA.79.012105.

[119] Richard H Byrd, Peihuang Lu, Jorge Nocedal, and Ciyou Zhu. A limited memory algorithm for bound constrained optimization. SIAM Journal on Scientific Computing, 16 (5): 1190–1208, 1995. 10.2172/​204262. URL https:/​/​​10.1137/​0916069.

[120] Patrick Kofod Mogensen and Asbjørn Nilsen Riseth. Optim: A mathematical optimization package for Julia. Journal of Open Source Software, 3 (24): 615, 2018. 10.21105/​joss.00615.

Cited by

[1] Feng Pan, Pengfei Zhou, Sujie Li, and Pan Zhang, “Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations”, Physical Review Letters 125 6, 060503 (2020).

[2] Jin-Guo Liu, Liang Mao, Pan Zhang, and Lei Wang, “Solving Quantum Statistical Mechanics with Variational Autoregressive Networks and Quantum Circuits”, arXiv:1912.11381.

[3] Sirui Lu, Lu-Ming Duan, and Dong-Ling Deng, “Quantum adversarial machine learning”, Physical Review Research 2 3, 033212 (2020).

[4] Tatiana A. Bespalova and Oleksandr Kyriienko, “Hamiltonian operator approximation for energy measurement and ground state preparation”, arXiv:2009.03351.

[5] Tong Liu, Jin-Guo Liu, and Heng Fan, “Probabilistic Nonunitary Gate in Imaginary Time Evolution”, arXiv:2006.09726.

[6] Jin-Guo Liu, Lei Wang, and Pan Zhang, “Tropical Tensor Network for Ground States of Spin Glasses”, arXiv:2008.06888.

[7] Jin-Guo Liu and Taine Zhao, “Differentiate Everything with a Reversible Domain-Specific Language”, arXiv:2003.04617.

[8] Carsten Bauer, “Fast and stable determinant quantum Monte Carlo”, arXiv:2003.05286.

[9] Chen Zhao and Xiao-Shan Gao, “QDNN: DNN with Quantum Neural Network Layers”, arXiv:1912.12660.

[10] The Quingo Development Team, “Quingo: A Programming Framework for Heterogeneous Quantum-Classical Computing with NISQ Features”, arXiv:2009.01686.

[11] Andrea Mari, Thomas R. Bromley, and Nathan Killoran, “Estimating the gradient and higher-order derivatives on quantum hardware”, arXiv:2008.06517.

[12] Stavros Efthymiou, Sergi Ramos-Calderer, Carlos Bravo-Prieto, Adrián Pérez-Salinas, Diego García-Martín, Artur Garcia-Saez, José Ignacio Latorre, and Stefano Carrazza, “Qibo: a framework for quantum simulation with hardware acceleration”, arXiv:2009.01845.

[13] Vincent Paul Su, “Variational Preparation of the Sachdev-Ye-Kitaev Thermofield Double”, arXiv:2009.04488.

The above citations are from SAO/NASA ADS (last updated successfully 2020-10-16 04:52:30). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref’s cited-by service no data on citing works was found (last attempt 2020-10-16 04:52:29).


Continue Reading
Energy2 hours ago

$172 Million Worldwide Friction Stir Welding Equipment Industry to 2027 – Impact of COVID-19 on the Market

Energy2 hours ago

Three Verdant Power Tidal Turbines Deployed in New York City’s East River

Energy2 hours ago

Kennametal to Attend Baird 2020 Global Industrial Virtual Conference

Energy3 hours ago

Worldwide Thermal Energy Storage Industry to 2025 – Featuring Abengoa, Baltimore Aircoil & Brightsource Energy Among Others

AR/VR3 hours ago

Competition: Win Either Angry Birds VR or Acron: Attack of the Squirrels! for Oculus Quest

Cyber Security3 hours ago

How Comodo’s Auto-Containment Technology Is Helping an IT Company Provide Ransomware Protection to Clients

AR/VR4 hours ago

Beat Saber Multiplayer for PlayStation VR Arrives Early 2021

AR/VR5 hours ago

The VR Game Launch Roundup: A Horrifyingly Tasty Selection

Blockchain News5 hours ago

Microstrategy CEO Reveals BTC Purchase is Corporate Strategy to Adopt Bitcoin Standard

Esports5 hours ago

BOOBIE joins Yeah

Energy6 hours ago

EPRI Joins International Consortium to Overcome Barriers to Renewable Energy Integration

Energy6 hours ago

Global Boring Tools Industry (2020 to 2027) – Market Trajectory & Analytics

Esports6 hours ago

Betway Nine to Five 5 Swiss Stage Fantasy live with prizes

Energy7 hours ago

Antimicrobial Coatings Market Size is Anticipated To Reach USD 11.6 Billion By 2027 – Valuates Reports

Energy7 hours ago

Modular Uninterruptible Power Supply (UPS) Market worth $6.0 billion by 2025 – Exclusive Report by MarketsandMarkets™

AR/VR7 hours ago

HTC’s Cher Wang Given ‘Accenture VR Lifetime Achievement Award’ by AIXR

Energy7 hours ago

Global $3.4 Billion Aerosol Valves Market to 2027: Rise in Demand for Innovative Product Dispensing Technology & Product Differentiation

Crowdfunding7 hours ago

Taking LSD Could Help Your Career

Esports8 hours ago

Natus Vincere defeat Gambit to set up IEM New York CIS semi-final bout against

Energy9 hours ago

Global $6.7 Billion Automated Storage & Retrieval Systems Market to 2025

Energy9 hours ago

Duke Energy announces dividend payments to shareholders

Energy9 hours ago

Lighting Control System Market Size is Projected to Reach USD 29990 Million by 2026 – Valuates Reports

Energy9 hours ago

Surge Energy America Recognized on Houston Business Journal’s Best Place to Work List

Energy9 hours ago

WAAREE spreads its wings globally, opens franchisee in Africa

Ecommerce9 hours ago

Revuze, the first SaaS Consumer Insights eCommerce Platform

AR/VR10 hours ago

Create Games With Your Voice Inside the Anything World Beta

Blockchain News10 hours ago

Bitcoin Price Bull Run Sees Grayscale Investments add $300M AUM in One Day

Blockchain News11 hours ago

Blockchain Industry Leaders R3 and FORMS HK join Cyberport to Launch “Block AdVenture” Program

Blockchain11 hours ago

A senior BOJ official says the digital yen needs public support for it to become a reality.

Blockchain News11 hours ago

PayPal May Buy Digital Asset Custodian BitGo Following Crypto Market Entry

Blockchain12 hours ago

Japanese soccer star Keisuke Honda launches his own crypto

Blockchain News12 hours ago

Blockchain Allowed 17 Million People to Travel Between Macau and China During Coronavirus

Blockchain12 hours ago

Grayscale invests $300m in a day to grow its crypto portfolio

Blockchain12 hours ago

VeChain candlestick pattern suggests VET ready to explode above $0.015

Blockchain13 hours ago

Russia doesn’t need to be first with a digital currency, says state expert

Blockchain13 hours ago

Russian public officials are now required to declare their crypto holdings as income.

Blockchain15 hours ago

A ransomware attack targets the government systems of Georgia’s Hall County.

Blockchain16 hours ago

Michael Saylor claims the company will hold Bitcoin for ‘100 years’

Blockchain16 hours ago

Traders on Paxful sell $16.2M of Bitcoin for discounted gift cards each week

Blockchain16 hours ago

Payment giant PayPal plans to acquire bitcoin custody platform BitGo.