Connect with us

Quantum

Optimizing Quantum Error Correction Codes with Reinforcement Learning

Published

on


Hendrik Poulsen Nautrup1, Nicolas Delfosse2, Vedran Dunjko3, Hans J. Briegel1,4, and Nicolai Friis5,1

1Institute for Theoretical Physics, University of Innsbruck, Technikerstr. 21a, A-6020 Innsbruck, Austria
2Station Q Quantum Architectures and Computation Group, Microsoft Research, Redmond, WA 98052, USA
3LIACS, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
4Department of Philosophy, University of Konstanz, Konstanz 78457, Germany
5Institute for Quantum Optics and Quantum Information, Austrian Academy of Sciences, Boltzmanngasse 3, 1090 Vienna, Austria

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

Abstract

Quantum error correction is widely thought to be the key to fault-tolerant quantum computation. However, determining the most suited encoding for unknown error channels or specific laboratory setups is highly challenging. Here, we present a reinforcement learning framework for optimizing and fault-tolerantly adapting quantum error correction codes. We consider a reinforcement learning agent tasked with modifying a family of surface code quantum memories until a desired logical error rate is reached. Using efficient simulations with about 70 data qubits with arbitrary connectivity, we demonstrate that such a reinforcement learning agent can determine near-optimal solutions, in terms of the number of data qubits, for various error models of interest. Moreover, we show that agents trained on one setting are able to successfully transfer their experience to different settings. This ability for transfer learning showcases the inherent strengths of reinforcement learning and the applicability of our approach for optimization from off-line simulations to on-line laboratory settings.

Many promising quantum technologies, ranging from powerful quantum computers to ultra-sensitive measuring devices, are currently being developed and tested in small-scale experiments around the globe. These devices are all strongly affected by noise from their environment and have to be controlled very precisely. This can be done via a technique called quantum error correction. However, this typically requires significant additional resources which are scarce and expensive. It is therefore crucial to find effective error correction procedures that use as few resources as possible. Unfortunately, this is very difficult in many cases. This work presents a flexible and efficient method based on artificial intelligence techniques for determining the best error correction strategy given available resources.

We develop an approach to quantum error correction where a machine learning algorithm (or learning agent) learns to design good error correction tools (called codes) that use as few basic building elements (qubits) as possible. We provide extensive computer simulations of this method for various realistic situations with qubit numbers soon available in state-of-the art laboratories. Our results suggest that a learning agent can not only find near-optimal solutions for a variety of problems, but is also able to transfer its experience from one situation to another. This feature is particularly valuable because it facilitates pre-training learning agents on cheap simulations before deployment to the actual, expensive device. Our work thus provides a stepping-stone for connecting quantum technologies and artificial intelligence that can be vital for future quantum devices.

► BibTeX data

► References

[1] Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, U.K., 2000).

[2] Vedran Dunjko, Yimin Ge, and J. Ignacio Cirac, Computational Speedups Using Small Quantum Devices, Phys. Rev. Lett. 121, 250501 (2018), arXiv:1807.08970.
https:/​/​doi.org/​10.1103/​PhysRevLett.121.250501
arXiv:arXiv:1807.08970

[3] Earl Campbell, Ankur Khurana, and Ashley Montanaro, Applying quantum algorithms to constraint satisfaction problems, Quantum 3, 167 (2019), arXiv:1810.05582.
https:/​/​doi.org/​10.22331/​q-2019-07-18-167
arXiv:arXiv:1810.05582

[4] John Preskill, Fault-tolerant quantum computation, in Introduction to Quantum Computation, edited by H.-K. Lo, S. Popescu, and T. P. Spiller (World-Scientific, 1997) Chap. 8, pp. 213-269, arXiv:quant-ph/​9712048.
https:/​/​doi.org/​10.1142/​9789812385253_0008
arXiv:arXiv:quant-ph/9712048

[5] Daniel Gottesmann, Stabilizer Codes and Quantum Error Correction, Ph.D. thesis, Caltech (1997), arXiv:quant-ph/​9705052.
arXiv:quant-ph/9705052

[6] Barbara M. Terhal, Quantum error correction for quantum memories, Rev. Mod. Phys. 87, 307 (2015), arXiv:1302.3428.
https:/​/​doi.org/​10.1103/​RevModPhys.87.307
arXiv:arXiv:1302.3428

[7] David K. Tuckett, Stephen D. Bartlett, and Steven T. Flammia, Ultrahigh Error Threshold for Surface Codes with Biased Noise, Phys. Rev. Lett. 120, 050505 (2018), arXiv:1708.08474.
https:/​/​doi.org/​10.1103/​PhysRevLett.120.050505
arXiv:arXiv:1708.08474

[8] Keisuke Fujii and Yuuki Tokunaga, Error and loss tolerances of surface codes with general lattice structures, Phys. Rev. A 86, 020303(R) (2012), arXiv:1202.2743.
https:/​/​doi.org/​10.1103/​PhysRevA.86.020303
arXiv:arXiv:1202.2743

[9] Thomas Monz, Philipp Schindler, Julio T. Barreiro, Michael Chwalla, Daniel Nigg, William A. Coish, Maximilian Harlander, Wolfgang Hänsel, Markus Hennrich, and Rainer Blatt, 14-Qubit Entanglement: Creation and Coherence, Phys. Rev. Lett. 106, 130506 (2011), arXiv:1009.6126.
https:/​/​doi.org/​10.1103/​PhysRevLett.106.130506
arXiv:arXiv:1009.6126

[10] Philipp Schindler, Daniel Nigg, Thomas Monz, J. T. Barreiro, Esteban Martinez, S. X. Wang, Stephan Quint, M. F. Brandl, Volckmar Nebendahl, Christian F. Roos, Michael Chwalla, M. Hennrich, and Rainer Blatt, A quantum information processor with trapped ions, New J. Phys. 15, 123012 (2013), arXiv:1308.3096.
https:/​/​doi.org/​10.1088/​1367-2630/​15/​12/​123012
arXiv:arXiv:1308.3096

[11] Vedran Dunjko and Hans J. Briegel, Machine learning & artificial intelligence in the quantum domain: a review of recent progress, Rep. Prog. Phys. 81, 074001 (2018), arXiv:1709.02779.
https:/​/​doi.org/​10.1088/​1361-6633/​aab406
arXiv:arXiv:1709.02779

[12] Giacomo Torlai and Roger G. Melko, Neural Decoder for Topological Codes, Phys. Rev. Lett. 119, 030501 (2017), arXiv:1610.04238.
https:/​/​doi.org/​10.1103/​PhysRevLett.119.030501
arXiv:arXiv:1610.04238

[13] Stefan Krastanov and Liang Jiang, Deep Neural Network Probabilistic Decoder for Stabilizer Codes, Sci. Rep. 7, 11003 (2017), arXiv:1705.09334.
https:/​/​doi.org/​10.1038/​s41598-017-11266-1
arXiv:arXiv:1705.09334

[14] Savvas Varsamopoulos, Ben Criger, and Koen Bertels, Decoding small surface codes with feedforward neural networks, Quant. Sci. Techn. 3, 015004 (2017), arXiv:1705.00857.
https:/​/​doi.org/​10.1088/​2058-9565/​aa955a
arXiv:arXiv:1705.00857

[15] Paul Baireuther, Thomas E. O’Brien, Brian Tarasinski, and Carlo W. J. Beenakker, Machine-learning-assisted correction of correlated qubit errors in a topological code, Quantum 2, 48 (2018), arXiv:1705.07855.
https:/​/​doi.org/​10.22331/​q-2018-01-29-48
arXiv:arXiv:1705.07855

[16] Nikolas P. Breuckmann and Xiaotong Ni, Scalable Neural Network Decoders for Higher Dimensional Quantum Codes, Quantum 2, 68 (2018), arXiv:1710.09489.
https:/​/​doi.org/​10.22331/​q-2018-05-24-68
arXiv:arXiv:1710.09489

[17] Christopher Chamberland and Pooya Ronagh, Deep neural decoders for near term fault-tolerant experiments, Quant. Sci. Techn. 3, 044002 (2018), arXiv:1802.06441.
https:/​/​doi.org/​10.1088/​2058-9565/​aad1f7
arXiv:arXiv:1802.06441

[18] Ryan Sweke, Markus S. Kesselring, Evert P. L. van Nieuwenburg, and Jens Eisert, Reinforcement learning decoders for fault-tolerant quantum computation, (2018), arXiv:1810.07207.
arXiv:arXiv:1810.07207

[19] Paul Baireuther, M. D. Caio, B. Criger, Carlo W. J. Beenakker, and Thomas E. O’Brien, Neural network decoder for topological color codes with circuit level noise, New J. Phys. 21, 013003 (2019), arXiv:1804.02926.
https:/​/​doi.org/​10.1088/​1367-2630/​aaf29e
arXiv:arXiv:1804.02926

[20] Xiaotong Ni, Neural network decoders for large-distance 2d toric codes, (2018), arXiv:1809.06640.
arXiv:arXiv:1809.06640

[21] Nishad Maskara, Aleksander Kubica, and Tomas Jochym-O’Connor, Advantages of versatile neural-network decoding for topological codes, Phys. Rev. A 99, 052351 (2019), arXiv:1802.08680.
https:/​/​doi.org/​10.1103/​PhysRevA.99.052351
arXiv:arXiv:1802.08680

[22] Ye-Hua Liu and David Poulin, Neural Belief-Propagation Decoders for Quantum Error-Correcting Codes, Phys. Rev. Lett. 122, 200501 (2019), arXiv:1811.07835.
https:/​/​doi.org/​10.1103/​PhysRevLett.122.200501
arXiv:arXiv:1811.07835

[23] Amarsanaa Davaasuren, Yasunari Suzuki, Keisuke Fujii, and Masato Koashi, General framework for constructing fast and near-optimal machine-learning-based decoder of the topological stabilizer codes, (2018), arXiv:1801.04377.
arXiv:arXiv:1801.04377

[24] Philip Andreasson, Joel Johansson, Simon Liljestrand, and Mats Granath, Quantum error correction for the toric code using deep reinforcement learning, Quantum 3, 183 (2019), arXiv:1811.12338.
https:/​/​doi.org/​10.22331/​q-2019-09-02-183
arXiv:arXiv:1811.12338

[25] Savvas Varsamopoulos, Koen Bertels, and Carmen G. Almudever, Comparing neural network based decoders for the surface code, IEEE T. Comput. (2019a), 10.1109/​TC.2019.2948612, arXiv:1811.12456.
https:/​/​doi.org/​10.1109/​TC.2019.2948612
arXiv:arXiv:1811.12456

[26] Savvas Varsamopoulos, Koen Bertels, and Carmen G. Almudever, Decoding surface code with a distributed neural network based decoder, (2019b), arXiv:1901.10847.
arXiv:arXiv:1901.10847

[27] Laia Domingo Colomer, Michalis Skotiniotis, and Ramon Muñoz-Tapia, Reinforcement learning for optimal error correction of toric codes, (2019), arXiv:1911.02308.
arXiv:arXiv:1911.02308

[28] Thomas Wagner, Hermann Kampermann, and Dagmar Bruß, Symmetries for a High Level Neural Decoder on the Toric Code, (2019), arXiv:1910.01662.
arXiv:arXiv:1910.01662

[29] Chaitanya Chinni, Abhishek Kulkarni, Dheeraj M. Pai, Kaushik Mitra, and Pradeep Kiran Sarvepalli, Neural Decoder for Topological Codes using Pseudo-Inverse of Parity Check Matrix, (2019), arXiv:1901.07535.
arXiv:arXiv:1901.07535

[30] Milap Sheth, Sara Zafar Jafarzadeh, and Vlad Gheorghiu, Neural ensemble decoding for topological quantum error-correcting codes, (2019), arXiv:1905.02345.
arXiv:arXiv:1905.02345

[31] Nicolas Delfosse, Pavithran Iyer, and David Poulin, A linear-time benchmarking tool for generalized surface codes, (2016), arXiv:1611.04256.
arXiv:arXiv:1611.04256

[32] Nicolas Delfosse and Pavithran Iyer, Squab – a fast benchmarking software for surface quantum computing architectures, (2016), [Online; accessed 13-December-2019].
http:/​/​quantum-squab.com/​

[33] Nicolas Delfosse and Naomi H. Nickerson, Almost-linear time decoding algorithm for topological codes, (2017), arXiv:1709.06218.
arXiv:arXiv:1709.06218

[34] Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction (MIT press, Cambridge, 1998).

[35] Nicolai Friis, Oliver Marty, Christine Maier, Cornelius Hempel, Milan Holzäpfel, Petar Jurcevic, Martin B. Plenio, Marcus Huber, Christian Roos, Rainer Blatt, and Ben Lanyon, Observation of Entangled States of a Fully Controlled 20-Qubit System, Phys. Rev. X 8, 021012 (2018), arXiv:1711.11092.
https:/​/​doi.org/​10.1103/​PhysRevX.8.021012
arXiv:arXiv:1711.11092

[36] Jiehang Zhang, Guido Pagano, Paul W. Hess, Antonis Kyprianidis, Patrick Becker, Harvey Kaplan, Alexey V. Gorshkov, Zhexuan Gong, and Christopher Monroe, Observation of a many-body dynamical phase transition with a 53-qubit quantum simulator, Nature 551, 601 (2017), arXiv:1708.01044.
https:/​/​doi.org/​10.1038/​nature24654
arXiv:arXiv:1708.01044

[37] Hannes Bernien, Sylvain Schwartz, Alexander Keesling, Harry Levine, Ahmed Omran, Hannes Pichler, Soonwon Choi, Alexander S. Zibrov, Manuel Endres, Markus Greiner, Vladan Vuletić, and Mikhail D. Lukin, Probing many-body dynamics on a 51-atom quantum simulator, Nature 551, 579 (2017), arXiv:1707.04344.
https:/​/​doi.org/​10.1038/​nature24622
arXiv:arXiv:1707.04344

[38] Héctor Bombín and Miguel Angel Martin-Delgado, Quantum measurements and gates by code deformation, J. Phys. A: Math. Theor. 42, 095302 (2009), arXiv:0704.2540.
https:/​/​doi.org/​10.1088/​1751-8113/​42/​9/​095302
arXiv:arXiv:0704.2540

[39] Sergey Bravyi and Alexei Kitaev, Quantum codes on a lattice with boundary, (1998), arXiv:quant-ph/​9811052.
arXiv:arXiv:quant-ph/9811052

[40] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill, Topological quantum memory, J. Math. Phys. 43, 4452 (2002), arXiv:quant-ph/​0110143.
https:/​/​doi.org/​10.1063/​1.1499754
arXiv:arXiv:quant-ph/0110143

[41] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland, Surface codes: Towards practical large-scale quantum computation, Phys. Rev. A 86, 032324 (2012), arXiv:1208.0928.
https:/​/​doi.org/​10.1103/​PhysRevA.86.032324
arXiv:arXiv:1208.0928

[42] Hans J. Briegel and Gemma De las Cuevas, Projective simulation for artificial intelligence, Sci. Rep. 7, 400 (2012), arXiv:1104.3787.
https:/​/​doi.org/​10.1038/​srep00400
arXiv:arXiv:1104.3787

[43] Julian Mautner, Adi Makmal, Daniel Manzano, Markus Tiersch, and Hans J. Briegel, Projective Simulation for Classical Learning Agents: A Comprehensive Investigation, New Gener. Comput. 33, 69 (2015), arXiv:1305.1578.
https:/​/​doi.org/​10.1007/​s00354-015-0102-0
arXiv:arXiv:1305.1578

[44] Alexey A. Melnikov, Adi Makmal, Vedran Dunjko, and Hans J. Briegel, Projective simulation with generalization, Sci. Rep. 7, 14430 (2017), arXiv:1504.02247.
https:/​/​doi.org/​10.1038/​s41598-017-14740-y
arXiv:arXiv:1504.02247

[45] Alexey A. Melnikov, Adi Makmal, and Hans J. Briegel, Benchmarking projective simulation in navigation problems, IEEE Access 6, 64639 (2018a), arXiv:1804.08607.
https:/​/​doi.org/​10.1109/​ACCESS.2018.2876494
arXiv:arXiv:1804.08607

[46] Simon Hangl, Emre Ugur, Sandor Szedmak, and Justus Piater, Robotic playing for hierarchical complex skill learning, in 2016 IEEE/​RSJ International Conference on Intelligent Robots and Systems (IROS) (2016) pp. 2799-2804, arXiv:1603.00794.
https:/​/​doi.org/​10.1109/​IROS.2016.7759434
arXiv:arXiv:1603.00794

[47] Alexey A. Melnikov, Hendrik Poulsen Nautrup, Mario Krenn, Vedran Dunjko, Markus Tiersch, Anton Zeilinger, and Hans J. Briegel, Active learning machine learns to create new quantum experiments, Proc. Natl. Acad. Sci. U.S.A. 115, 1221 (2018b), arXiv:1706.00868.
https:/​/​doi.org/​10.1073/​pnas.1714936115
arXiv:arXiv:1706.00868

[48] Sebastian Thrun, Is learning the n-th thing any easier than learning the first? in Advances in Neural Information Processing Systems 8, edited by D. S. Touretzky, M. C. Mozer, and M. E. Hasselmo (MIT Press, 1996) pp. 640-646.
http:/​/​papers.nips.cc/​paper/​1034-is-learning-the-n-th-thing-any-easier-than-learning-the-first.pdf

[49] Karl Weiss, Taghi M. Khoshgoftaar, and DingDing Wang, A survey of transfer learning, Journal of Big Data 3, 9 (2016).
https:/​/​doi.org/​10.1186/​s40537-016-0043-6

[50] Nicolas Delfosse and Gilles Zémor, Linear-Time Maximum Likelihood Decoding of Surface Codes over the Quantum Erasure Channel, (2017), arXiv:1703.01517.
arXiv:arXiv:1703.01517

[51] Rami Barends, Julian Kelly, Anthony Megrant, Andrzej Veitia, Daniel Sank, Evan Jeffrey, Ted C. White, Josh Mutus, Austin G. Fowler, B. Campbell, Yu Chen, Zijun Chen, Ben Chiaro, Andrew Dunsworth, Charles Neill, Peter O’Malley, Pedram Roushan, Amit Vainsencher, Jim Wenner, Alexander N. Korotkov, Andrew N. Cleland, and John M. Martinis, Superconducting quantum circuits at the surface code threshold for fault tolerance, Nature 508, 500 (2014), arXiv:1402.4848.
https:/​/​doi.org/​10.1038/​nature13171
arXiv:arXiv:1402.4848

[52] Torsten Karzig, Christina Knapp, Roman M. Lutchyn, Parsa Bonderson, Matthew B. Hastings, Chetan Nayak, Jason Alicea, Karsten Flensberg, Stephan Plugge, Yuval Oreg, Charles M. Marcus, and Michael H. Freedman, Scalable designs for quasiparticle-poisoning-protected topological quantum computation with Majorana zero modes, Phys. Rev. B 95, 235305 (2017), arXiv:1610.05289.
https:/​/​doi.org/​10.1103/​PhysRevB.95.235305
arXiv:arXiv:1610.05289

[53] Jason M. Amini, Hermann Uys, Janus H. Wesenberg, Signe Seidelin, Joseph Britton, John J. Bollinger, Dietrich Leibfried, Christian Ospelkaus, Aaron P. VanDevender, and David J. Wineland, Toward scalable ion traps for quantum information processing, New J. Phys. 12, 033031 (2010), arXiv:0909.2464.
https:/​/​doi.org/​10.1088/​1367-2630/​12/​3/​033031
arXiv:arXiv:0909.2464

[54] Ryan Bowler, John Gaebler, Y. Lin, T. R. Tan, D. Hanneke, J. D. Jost, J. P. Home, Dietrich Leibfried, and David J. Wineland, Coherent Diabatic Ion Transport and Separation in a Multizone Trap Array, Phys. Rev. Lett. 109, 080502 (2012), arXiv:1206.0780.
https:/​/​doi.org/​10.1103/​PhysRevLett.109.080502
arXiv:arXiv:1206.0780

[55] Sergey Bravyi and Robert König, Classification of Topologically Protected Gates for Local Stabilizer Codes, Phys. Rev. Lett. 110, 170503 (2013), arXiv:1206.1609.
https:/​/​doi.org/​10.1103/​PhysRevLett.110.170503
arXiv:arXiv:1206.1609

[56] Fernando Pastawski and Beni Yoshida, Fault-tolerant logical gates in quantum error-correcting codes, Phys. Rev. A 91, 012305 (2015), arXiv:1408.1720.
https:/​/​doi.org/​10.1103/​PhysRevA.91.012305
arXiv:arXiv:1408.1720

[57] Danna Rosenberg, David Kim, Rabi Das, Donna Yost, Simon Gustavsson, David Hover, Philip Krantz, Alexander Melville, Livia Racz, Gabriel O. Samach, Steven J. Weber, Fei Yan, Jonilyn L. Yoder, Andrew J. Kerman, and William D. Oliver, 3d integrated superconducting qubits, npj Quantum Information 3, 42 (2017), arXiv:1706.04116.
https:/​/​doi.org/​10.1038/​s41534-017-0044-0
arXiv:arXiv:1706.04116

[58] Charles H. Bennett, David P. DiVincenzo, and John A. Smolin, Capacities of Quantum Erasure Channels, Phys. Rev. Lett. 78, 3217 (1997), arXiv:quant-ph/​9701015.
https:/​/​doi.org/​10.1103/​PhysRevLett.78.3217
arXiv:arXiv:quant-ph/9701015

[59] Markus Grassl, Thomas Beth, and Thomas Pellizzari, Codes for the quantum erasure channel, Phys. Rev. A 56, 33 (1997), arXiv:quant-ph/​9610042.
https:/​/​doi.org/​10.1103/​PhysRevA.56.33
arXiv:arXiv:quant-ph/9610042

[60] Scott Kirkpatrick, C. Daniel Gelatt, and Mario P. Vecchi, Optimization by Simulated Annealing, Science 220, 671 (1983).
https:/​/​doi.org/​10.1126/​science.220.4598.671

[61] Michael Reimpell and Reinhard F. Werner, Iterative Optimization of Quantum Error Correcting Codes, Phys. Rev. Lett. 94, 080501 (2005), arXiv:quant-ph/​0307138.
https:/​/​doi.org/​10.1103/​PhysRevLett.94.080501
arXiv:arXiv:quant-ph/0307138

[62] Robert L. Kosut and Daniel A. Lidar, Quantum error correction via convex optimization, Quant. Inf. Proc. 8, 443 (2009), arXiv:quant-ph/​0606078.
https:/​/​doi.org/​10.1007/​s11128-009-0120-2
arXiv:arXiv:quant-ph/0606078

[63] Peter D. Johnson, Jonathan Romero, Jonathan Olson, Yudong Cao, and Alán Aspuru-Guzik, QVECTOR: an algorithm for device-tailored quantum error correction, (2017), arXiv:1711.02249.
arXiv:arXiv:1711.02249

[64] Anonymous, Improving Exploration of Deep Reinforcement Learning using Planning for Policy Search, in Submitted to International Conference on Learning Representations (2020) under double-blind review [Online at https:/​/​openreview.net/​forum?id=rJe7CkrFvS; accessed 13-December-2019].
https:/​/​openreview.net/​forum?id=rJe7CkrFvS

[65] Sergey Levine and Vladlen Koltun, Guided Policy Search, in Proceedings of the 30th International Conference on International Conference on Machine Learning – Volume 28, ICML’13 (JMLR.org, 2013) pp. III-1-III-9.
http:/​/​dl.acm.org/​citation.cfm?id=3042817.3042937

[66] Richard Cleve and Daniel Gottesman, Efficient computations of encodings for quantum error correction, Phys. Rev. A 56, 76 (1997), arXiv:quant-ph/​9607030.
https:/​/​doi.org/​10.1103/​PhysRevA.56.76
arXiv:arXiv:quant-ph/9607030

[67] Scott Aaronson and Daniel Gottesman, Improved simulation of stabilizer circuits, Phys. Rev. A 70, 052328 (2004), arXiv:quant-ph/​0406196.
https:/​/​doi.org/​10.1103/​PhysRevA.70.052328
arXiv:arXiv:quant-ph/0406196

[68] David P. DiVincenzo and Peter W. Shor, Fault-Tolerant Error Correction with Efficient Quantum Codes, Phys. Rev. Lett. 77, 3260 (1996), arXiv:quant-ph/​9605031.
https:/​/​doi.org/​10.1103/​PhysRevLett.77.3260
arXiv:arXiv:quant-ph/9605031

[69] Simon Anders and Hans J. Briegel, Fast simulation of stabilizer circuits using a graph-state representation, Phys. Rev. A 73, 022334 (2006), arXiv:quant-ph/​0504117.
https:/​/​doi.org/​10.1103/​PhysRevA.73.022334
arXiv:arXiv:quant-ph/0504117

[70] Lorenza Saitta and Jean-Daniel Zucker, Abstraction in Artificial Intelligence and Complex Systems (Springer, New York, USA, 2013).

[71] Novi Patricia and Barbara Caputo, Learning to Learn, from Transfer Learning to Domain Adaptation: A Unifying Perspective, in 2014 IEEE Conference on Computer Vision and Pattern Recognition (2014) pp. 1442-1449.
https:/​/​doi.org/​10.1109/​CVPR.2014.187

[72] Tatiana Tommasi and Barbara Caputo, The more you know, the less you learn: from knowledge transfer to one-shot learning of object categories, in Proceedings of the British Machine Vision Conference, edited by A. Cavallaro, S. Prince, and D. Alexander (BMVA Press, 2009) pp. 80.1-80.11.
https:/​/​doi.org/​10.5244/​C.23.80

[73] Tatiana Tommasi, Francesco Orabona, and Barbara Caputo, Safety in numbers: Learning categories from few examples with multi model knowledge transfer, in 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (2010) pp. 3081-3088.
https:/​/​doi.org/​10.1109/​CVPR.2010.5540064

[74] Yusuf Aytar and Andrew Zisserman, Tabula rasa: Model transfer for object category detection, in 2011 International Conference on Computer Vision (2011) pp. 2252-2259.
https:/​/​doi.org/​10.1109/​ICCV.2011.6126504

[75] Panos Aliferis, Frederico Brito, David P. DiVincenzo, John Preskill, Matthias Steffen, and Barbara M. Terhal, Fault-tolerant computing with biased-noise superconducting qubits: a case study, New J. Phys. 11, 013061 (2009), arXiv:0806.0383.
https:/​/​doi.org/​10.1088/​1367-2630/​11/​1/​013061
arXiv:arXiv:0806.0383

[76] Michael D. Shulman, Oliver E. Dial, Shannon P. Harvey, Hendrik Bluhm, Vladimir Umansky, and Amir Yacoby, Demonstration of Entanglement of Electrostatically Coupled Singlet-Triplet Qubits, Science 336, 202 (2012), arXiv:1202.1828.
https:/​/​doi.org/​10.1126/​science.1217692
arXiv:arXiv:1202.1828

[77] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis, Human-level control through deep reinforcement learning, Nature 518, 529 (2015).
https:/​/​doi.org/​10.1038/​nature14236

[78] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis, Mastering the game of Go without human knowledge, Nature 550, 354 (2017).
https:/​/​doi.org/​10.1038/​nature24270

[79] Will Knight, Reinforcement learning – by experimenting, computers are figuring out how to do things that no programmer could teach them, (2017), [Online; accessed 13-December-2019].
https:/​/​www.technologyreview.com/​s/​603501/​10-breakthrough-technologies-2017-reinforcement-learning/​

[80] Lenka Zdeborová, New tool in the box, Nat. Phys. 13, 420 (2017).
https:/​/​doi.org/​10.1038/​nphys4053

[81] Raban Iten, Tony Metger, Henrik Wilming, Lidia del Rio, and Renato Renner, Discovering physical concepts with neural networks, Phys. Rev. Lett. (accepted, 2019), arXiv:1807.10300.
arXiv:arXiv:1807.10300
https:/​/​journals.aps.org/​prl/​accepted/​9e07eY09T2e1fd7f88ae46166090ef41fa6ad4c34

[82] Thomas Fösel, Petru Tighineanu, Talitha Weiss, and Florian Marquardt, Reinforcement Learning with Neural Networks for Quantum Feedback, Phys. Rev. X 8, 031084 (2018), arXiv:1802.05267.
https:/​/​doi.org/​10.1103/​PhysRevX.8.031084
arXiv:arXiv:1802.05267

[83] Moritz August and José Miguel Hernández-Lobato, Taking Gradients Through Experiments: LSTMs and Memory Proximal Policy Optimization for Black-Box Quantum Control, in High Performance Computing, edited by Rio Yokota, Michèle Weiland, John Shalf, and Sadaf Alam (Springer International Publishing, Cham, 2018) arXiv:1802.04063.
https:/​/​doi.org/​10.1007/​978-3-030-02465-9_43
arXiv:arXiv:1802.04063

[84] Matthew R. Kretchmar, Parallel reinforcement learning, in The 6th World Conference on Systematics, Cybernetics, and Informatics (2002) pp. 165-170.

[85] Enda Barrett, Jim Duggan, and Enda Howley, A parallel framework for bayesian reinforcement learning, Connect. Sci. 26, 7 (2014).
https:/​/​doi.org/​10.1080/​09540091.2014.885268

[86] Sepp Hochreiter and Jürgen Schmidhuber, Long Short-Term Memory, Neural Comput. 9, 1735 (1997).
https:/​/​doi.org/​10.1162/​neco.1997.9.8.1735

[87] Hendrik Poulsen Nautrup, Nicolai Friis, and Hans J. Briegel, Fault-tolerant interface between quantum memories and quantum processors, Nat. Commun. 8, 1321 (2017), arXiv:1609.08062.
https:/​/​doi.org/​10.1038/​s41467-017-01418-2
arXiv:arXiv:1609.08062

[88] Dorit Aharonov, Alexei Kitaev, and John Preskill, Fault-Tolerant Quantum Computation with Long-Range Correlated Noise, Phys. Rev. Lett. 96, 050504 (2006), arXiv:quant-ph/​0510231.
https:/​/​doi.org/​10.1103/​PhysRevLett.96.050504
arXiv:arXiv:quant-ph/0510231

[89] Hui Khoon Ng and John Preskill, Fault-tolerant quantum computation versus Gaussian noise, Phys. Rev. A 79, 032318 (2009), arXiv:0810.4953.
https:/​/​doi.org/​10.1103/​PhysRevA.79.032318
arXiv:arXiv:0810.4953

[90] Austin G. Fowler and John M. Martinis, Quantifying the effects of local many-qubit errors and nonlocal two-qubit errors on the surface code, Phys. Rev. A 89, 032316 (2014), arXiv:1401.2466.
https:/​/​doi.org/​10.1103/​PhysRevA.89.032316
arXiv:arXiv:1401.2466

[91] Naomi H. Nickerson and Benjamin J. Brown, Analysing correlated noise on the surface code using adaptive decoding algorithms, Quantum 3, 131 (2019), arXiv:1712.00502.
https:/​/​doi.org/​10.22331/​q-2019-04-08-131
arXiv:arXiv:1712.00502

[92] Adi Makmal, Alexey A. Melnikov, Vedran Dunjko, and Hans J. Briegel, Meta-learning within Projective Simulation, IEEE Access 4, 2110 (2016), arXiv:1602.08017.
https:/​/​doi.org/​10.1109/​ACCESS.2016.2556579
arXiv:arXiv:1602.08017

Cited by

[1] Giuseppe Carleo, Ignacio Cirac, Kyle Cranmer, Laurent Daudet, Maria Schuld, Naftali Tishby, Leslie Vogt-Maranto, and Lenka Zdeborová, “Machine learning and the physical sciences*”, Reviews of Modern Physics 91 4, 045002 (2019).

[2] Xiao-Ming Zhang, Zezhu Wei, Raza Asad, Xu-Chen Yang, and Xin Wang, “When does reinforcement learning stand out in quantum control? A comparative study on state preparation”, npj Quantum Information 5, 85 (2019).

[3] Jun-Jie Chen and Ming Xue, “Manipulation of Spin Dynamics by Deep Reinforcement Learning Agent”, arXiv:1901.08748.

[4] Kai-Wen Zhao, Wen-Han Kao, Kai-Hsin Wu, and Ying-Jer Kao, “Generation of ice states through deep reinforcement learning”, Physical Review E 99 6, 062106 (2019).

[5] Riccardo Porotti, Dario Tamascelli, Marcello Restelli, and Enrico Prati, “Coherent transport of quantum states by deep reinforcement learning”, Communications Physics 2 1, 61 (2019).

[6] Chaitanya Chinni, Abhishek Kulkarni, Dheeraj M. Pai, Kaushik Mitra, and Pradeep Kiran Sarvepalli, “Neural Decoder for Topological Codes using Pseudo-Inverse of Parity Check Matrix”, arXiv:1901.07535.

[7] Julius Wallnöfer, Alexey A. Melnikov, Wolfgang Dür, and Hans J. Briegel, “Machine learning for long-distance quantum communication”, arXiv:1904.10797.

[8] Natalie C. Brown and Kenneth R. Brown, “Leakage mitigation for quantum error correction using a mixed qubit scheme”, Physical Review A 100 3, 032325 (2019).

[9] Alexey A. Melnikov, Leonid E. Fedichkin, and Alexander Alodjants, “Predicting quantum advantage by quantum walk with convolutional neural networks”, arXiv:1901.10632.

[10] Samuel Yen-Chi Chen, Chao-Han Huck Yang, Jun Qi, Pin-Yu Chen, Xiaoli Ma, and Hsi-Sheng Goan, “Variational Quantum Circuits for Deep Reinforcement Learning”, arXiv:1907.00397.

[11] Laia Domingo Colomer, Michalis Skotiniotis, and Ramon Muñoz-Tapia, “Reinforcement learning for optimal error correction of toric codes”, arXiv:1911.02308.

[12] J. Darulová, S. J. Pauka, N. Wiebe, K. W. Chan, G. C. Gardener, M. J. Manfra, M. C. Cassidy, and M. Troyer, “Autonomous tuning and charge state detection of gate defined quantum dots”, arXiv:1911.10709.

[13] Fulvio Flamini, Arne Hamann, Sofiène Jerbi, Lea M. Trenkwalder, Hendrik Poulsen Nautrup, and Hans J. Briegel, “Photonic architecture for reinforcement learning”, arXiv:1907.07503.

[14] Hamza Jaffali and Luke Oeding, “Learning Algebraic Models of Quantum Entanglement”, arXiv:1908.10247.

[15] Jens Clausen, Walter L. Boyajian, Lea M. Trenkwalder, Vedran Dunjko, and Hans J. Briegel, “On the convergence of projective-simulation-based reinforcement learning in Markov decision processes”, arXiv:1910.11914.

[16] Sofiene Jerbi, Hendrik Poulsen Nautrup, Lea M. Trenkwalder, Hans J. Briegel, and Vedran Dunjko, “A framework for deep energy-based reinforcement learning with quantum speed-up”, arXiv:1910.12760.

[17] Katja Ried, Benjamin Eva, Thomas Müller, and Hans J. Briegel, “How a minimal learning agent can infer the existence of unobserved variables in a complex environment”, arXiv:1910.06985.

[18] Sathwik Chadaga, Mridul Agarwal, and Vaneet Aggarwal, “Encoders and Decoders for Quantum Expander Codes Using Machine Learning”, arXiv:1909.02945.

[19] Zhikang T. Wang, Yuto Ashida, and Masahito Ueda, “Deep Reinforcement Learning Control of Quantum Cartpoles”, arXiv:1910.09200.

[20] Xiaosi Xu, Simon C. Benjamin, and Xiao Yuan, “Variational circuit compiler for quantum error correction”, arXiv:1911.05759.

The above citations are from SAO/NASA ADS (last updated successfully 2020-01-22 14:35:20). 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-01-22 14:35:18).

Source: https://quantum-journal.org/papers/q-2019-12-16-215/

Quantum

Sense, sensibility, and superconductors

Published

on

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

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

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

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

With chip

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

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

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

Old cover

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

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

Sea monsters

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

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

Green cover

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

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

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

Continue Reading

Quantum

Approximating Hamiltonian dynamics with the Nyström method

Published

on

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

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

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

Abstract

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

► BibTeX data

► References

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cited by

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

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

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

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

Could not fetch Crossref cited-by data during last attempt 2020-02-20 15:40:34: Could not fetch cited-by data for 10.22331/q-2020-02-20-234 from Crossref. This is normal if the DOI was registered recently.

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

Continue Reading

Quantum

Extension of the Alberti-Ulhmann criterion beyond qubit dichotomies

Published

on

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

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

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

Abstract

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

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

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

► BibTeX data

► References

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cited by

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

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

Continue Reading

Trending