{"id":295748,"date":"2016-09-22T12:47:02","date_gmt":"2016-09-22T19:47:02","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-event&p=295748"},"modified":"2018-11-08T15:29:05","modified_gmt":"2018-11-08T23:29:05","slug":"workshop-on-quantum-algorithms-and-devices","status":"publish","type":"msr-event","link":"https:\/\/www.microsoft.com\/en-us\/research\/event\/workshop-on-quantum-algorithms-and-devices\/","title":{"rendered":"Workshop on Quantum Algorithms and Devices"},"content":{"rendered":"

Venue:<\/strong>\u00a0Sonora Room, Microsoft Conference Center\u00a0(Building 33)<\/p>\n

The Quantum Algorithms and Devices Workshop was part of the Microsoft Research Faculty Summit 2016<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

The workshop highlighted recent advances in quantum algorithms, quantum devices, control systems, and quantum error correction.<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"msr_startdate":"2016-07-15","msr_enddate":"","msr_location":"Redmond, WA, USA","msr_expirationdate":"","msr_event_recording_link":"","msr_event_link":"","msr_event_link_redirect":false,"msr_event_time":"8:30 AM \u2013 5:30 PM","msr_hide_region":false,"msr_private_event":false,"footnotes":""},"research-area":[243138],"msr-region":[197900],"msr-event-type":[197944],"msr-video-type":[],"msr-locale":[268875],"msr-program-audience":[],"msr-post-option":[],"msr-impact-theme":[],"class_list":["post-295748","msr-event","type-msr-event","status-publish","hentry","msr-research-area-quantum","msr-region-north-america","msr-event-type-hosted-by-microsoft","msr-locale-en_us"],"msr_about":"Venue:<\/strong>\u00a0Sonora Room, Microsoft Conference Center\u00a0(Building 33)\r\n\r\nThe Quantum Algorithms and Devices Workshop was part of the Microsoft Research Faculty Summit 2016<\/a>.","tab-content":[{"id":0,"name":"About","content":"In 1981, Richard Feynman proposed a device called a \u201cquantum computer\u201d that would take advantage of\u00a0methods founded on the laws of quantum physics and promise computational speed-ups over classical\u00a0methods. In the last three decades, quantum algorithms have been developed that offer fast solutions to\u00a0problems in a variety of fields including number theory, optimization, database search, chemistry, and\u00a0physics. For quantum devices, this past year marks significant progress towards scalable quantum bits and\u00a0gates. The workshop highlighted recent advances in quantum algorithms, quantum devices, control\u00a0systems, and quantum error correction. For a comprehensive list of the topics covered, see the \"Abstracts\" tab."},{"id":1,"name":"Agenda","content":"\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n
Time<\/th>\r\nSession<\/th>\r\nSpeaker<\/th>\r\n<\/tr>\r\n<\/thead>\r\n
\r\n
8:30 \u2013 9:00<\/div><\/td>\r\n
\r\n
Quantum Monte Carlo vs Tunneling in Adiabatic Optimization<\/div><\/td>\r\n
Aram Harrow<\/td>\r\n<\/tr>\r\n
\r\n
9:05 \u2013 9:35<\/div><\/td>\r\n
\r\n
Adiabatic Optimization vs Diffusion Monte Carlo<\/div><\/td>\r\n
Stephen Jordan<\/td>\r\n<\/tr>\r\n
9:40\u00a0\u2013 10:10<\/td>\r\n\r\n
Quantum Speed-ups for Semidefinite Programming<\/div><\/td>\r\n
Fernando Brandao<\/td>\r\n<\/tr>\r\n
10:15 \u2013 10:30<\/td>\r\n\r\n
Coffee Break<\/div><\/td>\r\n
<\/td>\r\n<\/tr>\r\n
\r\n
10:35 \u2013 11:05<\/div><\/td>\r\n
\r\n
How to Program a Trapped Ions Quantum Computer<\/div><\/td>\r\n
Dmitri Maslov<\/td>\r\n<\/tr>\r\n
\r\n
11:10\u00a0\u2013 11:40<\/div><\/td>\r\n
\r\n
Photonic Quantum Computing<\/div><\/td>\r\n
Jeremy O\u2019Brien & Terry Rudolph<\/td>\r\n<\/tr>\r\n
11:45 \u2013 12:00<\/td>\r\n\r\n
LIQUI|> Coding Challenge Winners<\/div><\/td>\r\n
<\/td>\r\n<\/tr>\r\n
12:00 \u2013 1:00<\/td>\r\n\r\n
Lunch<\/div><\/td>\r\n
<\/td>\r\n<\/tr>\r\n
1:05 \u2013 1:35<\/td>\r\n\r\n
Local Decoders and Their Performance for 2D and\u00a04D Toric Codes<\/div><\/td>\r\n
Barbara Terhal<\/td>\r\n<\/tr>\r\n
1:40 \u2013 2:10<\/td>\r\n\r\n
Fault-Tolerant Quantum Memory for Non-Abelian Anyons<\/div><\/td>\r\n
David Poulin<\/td>\r\n<\/tr>\r\n
2:15 \u2013 2:45<\/td>\r\nQuantum Supremacy<\/td>\r\nScott Aaronson<\/td>\r\n<\/tr>\r\n
2:50\u00a0\u2013 3:05<\/td>\r\n\r\n
Coffee Break<\/div><\/td>\r\n
<\/td>\r\n<\/tr>\r\n
3:10 \u2013 3:40<\/td>\r\n\r\n
Topology of Local Hamiltonians and Robust Quantum Entanglement<\/div><\/td>\r\n
Lior Eldar<\/td>\r\n<\/tr>\r\n
3:45 \u2013 4:15<\/td>\r\n\r\n
Quantum Simulations of Continuous-Variable Quantum Systems<\/div><\/td>\r\n
Rolando Somma<\/td>\r\n<\/tr>\r\n
4:20 \u2013 4:50<\/td>\r\n\r\n
Investigating Biological Nitrogen Fixation Using a Quantum Computer<\/div><\/td>\r\n
Nathan Wiebe<\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>"},{"id":2,"name":"Abstracts","content":"[accordion]\r\n\r\n[panel header=\"Quantum Monte Carlo vs Tunneling in Adiabatic Optimization\"]\r\n\r\nSpeaker:<\/strong>\u00a0Aram Harrow\r\n\r\nCan quantum computers solve optimization problems much more quickly than\u00a0classical computers? One major piece of evidence for this proposition has been the fact that\u00a0Quantum Annealing (QA, also known as adiabatic optimization) finds the minimum of some cost\u00a0functions exponentially more quickly than Simulated Annealing (SA), which is arguably a classical\u00a0analogue of QA. These include a toy model, called \"Hamming weight with a spike\", where SA\u00a0gets stuck in a local minimum and QA uses quantum mechanical tunneling to find the correct\u00a0answer.\r\n\r\nOur work considers a classical algorithm known as Simulated Quantum Annealing (SQA) which\u00a0relates certain quantum systems to classical Markov chains. By proving that these chains mix\u00a0rapidly, we show that SQA runs in polynomial time on the Hamming weight with spike problem\u00a0in much of the parameter regime where QA achieves exponential\u00a0advantage over SA. While our analysis only covers this toy model, it\u00a0can be seen as evidence against the prospect of exponential quantum speedup using tunneling.\r\n\r\nThis is based on arXiv:1601.03030, which is joint work with Elizabeth Crosson.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Adiabatic optimization vs diffusion Monte Carlo\"]\r\n\r\nSpeaker:<\/strong>\u00a0Stephen Jordan\r\n\r\nMost experimental and theoretical studies of adiabatic optimization use stoquastic\u00a0Hamiltonians, whose ground states are expressible using only real nonnegative amplitudes. This\u00a0raises a question as to whether classical Monte Carlo methods can simulate stoquastic adiabatic\u00a0algorithms with polynomial overhead. Here, we analyze diffusion Monte Carlo algorithms. We\u00a0argue that, based on differences between L1 and L2 normalized states, these algorithms suffer\u00a0from certain obstructions preventing them from efficiently simulating stoquastic adiabatic\u00a0evolution in generality. In practice however, we obtain good performance by introducing a\u00a0method that we call Substochastic Monte Carlo. In fact, our simulations are good classical\u00a0optimization heuristics in their own right, competitive with the best previously known heuristic\u00a0solvers for MAX-k-SAT at k=2,3,4.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Quantum Speed-ups for Semidefinite Programming\"]\r\n\r\nSpeaker:<\/strong>\u00a0Fernando Brandao\r\n\r\nIn this talk I presented a quantum algorithm for solving semidefinite programs (SDPs).\u00a0It has worst case running time O((nm)^1\/2 r), with n and r the dimension and sparsity\u00a0of the input matrices, respectively, and m the number of constraints. In contrast any\u00a0classical method requires at least Omesdfsdfnm) time to solve the problem. I discussed how for some instances the algorithm might offer even exponential speed-ups, if the\u00a0quantum Gibbs states of Hamiltonians given by linear combinations of the input matrices\u00a0of the SDP can be prepared efficiently on a quantum computer.\r\n\r\nAs an application I showed how the Goemans-Williamson SDP for approximating max-cut\u00a0can be solved quantum-mechanically in time linear in the number of vertices of the graph.\u00a0This gives a speed-up over the best classical method, which requires linear time in the number\u00a0of edges.\r\n\r\nBased on joint work with Krysta Svore.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"How to program a trapped ions quantum computer\"]\r\n\r\nSpeaker:<\/strong>\u00a0Dmitri Maslov\r\n\r\nIn this talk, I discussed ion-trap quantum computing, and specifically, how to\u00a0program and efficiently compile physical-level experiments for an ion-trap quantum machine\u00a0developed by the researchers at the University of Maryland. I reported a complete strategy,\u00a0consisting of the full set of steps taken to sequentially decompose a quantum algorithm\/circuit\u00a0from a higher-level specification into progressively lower-level specifications until physical-level\u00a0specification is reached. The different stages are structured so as to best assist with the\u00a0optimization of the resulting physical-level implementation and while taking into account\u00a0numerous optimization criteria, including minimizing the number of expensive two-qubit gates,\u00a0minimizing the number of less expensive single-qubit gates, optimizing the runtime, minimizing\u00a0the overall circuit error, as well as optimizing classical control sequences. There were furthermore\u00a0two types of compilation discussed: first allows executing a given quantum algorithm most\u00a0efficiently via selecting physical qubits to work with, and second provides a fully parametrized\u00a0physical-level circuit that can be executed on any set of qubits (moreover, sometimes, those\u00a0parametrized circuits have free parameters that can be set arbitrarily). I illustrated the\r\nefficiency of this compilation approach via comparing to the previously known results. I also\u00a0reported the results of some physical-level experiments, providing a strong motivation for further\u00a0study of and the development of tools for the trapped ions quantum information processing\u00a0platform.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Photonic quantum computing\"]\r\n\r\nSpeakers:<\/strong>\u00a0Jeremy O\u2019Brien and Terry Rudolph\r\n\r\nOf the various approaches to quantum computing, photons are appealing for their\u00a0low-noise properties and ease of manipulation at the single photon level; while the challenge of\u00a0entangling interactions between photons can be met via measurement induced non-linearities.\u00a0However, the real excitement with this architecture is the promise of ultimate manufacturability:\u00a0All of the components\u2014inc. sources, detectors, filters, switches, delay lines\u2014have been\u00a0implemented on chip, and increasingly sophisticated integration of these components is being\u00a0achieved. We discussed the opportunities and challenges of a fully integrated photonic\u00a0quantum computer.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Local Decoders and Their Performance for 2D and 4D Toric Codes\"]\r\n\r\nSpeaker:<\/strong>\u00a0Barbara Terhal\r\n\r\nWe discussed the need for fast and parallel decoding in implementing quantum error\u00a0correction.\u00a0We reviewed the issue of local decoding from the perspective of self-correction. We reported on an\u00a0optimized implementation\u00a0of the local Harrington decoder for the 2D toric code where we observe a threshold of\u00a00.14% for noiseless parity checks and a threshold of 0.086% for equal-rate qubit and parity\u00a0check errors.\u00a0We reported on an implementation of a local decoder for the 4D toric code, exhibiting a threshold\u00a0of 2.1% for\u00a0noiseless parity checks and a threshold of 1.6% for equal-rate qubit and parity check errors.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Fault-tolerant quantum memory for non-abelian anyons\"]\r\n\r\nSpeaker:<\/strong>\u00a0David Poulin\r\n\r\nNon-abelian anyons have drawn much interest due to their suspected existence in\u00a0two-dimensional condensed matter systems and for their potential applications in quantum\u00a0computation. In particular, a quantum computation can in principle be realized by braiding and\u00a0fusing certain non-abelian anyons. These operations are expected to be intrinsically robust due\u00a0to their topological nature. Provided the system is kept at a temperature T lower than the\u00a0spectral gap, the density of thermal excitations is suppressed by an exponential Boltzman factor.\u00a0In contrast to the topological protection however, this thermal protection is not scalable:\u00a0thermal excitations do appear at constant density for any non-zero temperature and so their\u00a0presence is unavoidable as the size of the computation increases. Thermally activated anyons\u00a0can corrupt the encoded data by braiding or fusing with the computational anyons.\r\n\r\nIn the present work, we generalize a fault-tolerant scheme introduced by Harrington for the\u00a0toric-code to the setting of non-cyclic modular anyons. We prove that the quantum information\u00a0encoded in the fusion space of a non-abelian anyon system can be preserved for arbitrarily long\u00a0times with poly-log overhead.\u00a0In particular, our model accounts for noise processes which lead to the creation of anyon pairs\u00a0from the vacuum, anyon diffusion, anyon fusion as well as errors in topological charge\r\nmeasurements.\r\n\r\nBased on joint work with Guillaume Dauphinais.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Quantum Supremacy\"]\r\n\r\nSpeaker:<\/strong>\u00a0Scott Aaronson\r\n\r\nIn the near future, it will likely become possible to perform special-purpose quantum computations that, while not immediately useful for anything, are plausibly hard to simulate\u00a0using a classical computer. These experiments will be a scientific milestone, but they raise\u00a0urgent challenges for theoretical computer science: in particular, on what grounds should we\u00a0believe that a given quantum system really is hard to simulate classically? does classical\u00a0simulation become easier as a quantum system becomes noisier? and how do we verify the\u00a0results of such an experiment?\r\n\r\nI discussed recent results and open problems about these questions, focusing on random\u00a0quantum circuits and general results about the complexity of quantum sampling, while also\u00a0mentioning progress on my and Alex Arkhipov's BosonSampling proposal.\r\n\r\nBased partly on joint\u00a0work with Lijie Chen and with Daniel Brod.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Topology of local Hamiltonians and robust quantum entanglement\"]\r\n\r\nSpeaker<\/strong>:\u00a0Lior Eldar\r\n\r\nQuantum entanglement is considered as the \"source\" of quantum algorithmic speedup,\u00a0yet it is very fragile and hard to maintain\u00a0in the presence of noise. In this work we ask what kind of interaction topology is sufficient\u00a0as the underlying topology of\u00a0a locally-defined quantum system (local Hamiltonian), so that it has a robust form of quantum\u00a0entanglement in a well-defined sense,\u00a0or quantum hardness-of-approximation [NLTS. Freedman, Hastings, '13].\r\n\r\nWe focused on topologies with a large iso-perimetric constant (namely \"expanding\"), and\u00a0showed that while topologies that are strong enough for classical hardness-of-approximation\u00a0(namely expander graphs) are not necessarily quantum-robust, a certain high-dimensional\u00a0variant called systole\/co-systole expander [Evra,Kaufman '16], which is intensively studied in\u00a0algebraic topology nowadays, will in fact allow to establish quantum hardness-ofapproximation,\u00a0if it exists.\r\n\r\nJoint work with Aram Harrow.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Quantum simulations of continuous-variable quantum systems\"]\r\n\r\nSpeaker:<\/strong>\u00a0Rolando Somma\r\n\r\nOne of the best-known problems that a quantum computer is expected to solve more\u00a0efficiently than a classical one is the simulation of quantum systems. While significant work has\u00a0considered the case of discrete, finite dimensional quantum systems, the study of fast quantum\u00a0simulation methods for continuous-variable systems has only received little attention. In this\u00a0talk, I presented quantum methods to simulate the time evolution of certain continuous variable\u00a0quantum systems. Building up on recent results about product formulas for Lie groups, I first described a way to simulate the time evolution of the quantum harmonic oscillator\u00a0(QHO) that results in a superpolynomial speedup over the corresponding classical method. Our\u00a0algorithms can also be used to prepare eigenstates of the QHO and may be of independent\u00a0interest. I then considered the simulation of more complex quantum systems, such as the\u00a0quartic potential. In those cases, our method results in a polynomial quantum speedup.\u00a0Generalizations and connections between our results and the so-called fractional Fourier\u00a0transform, which is a generalization of the Fourier transform used in signal analysis, was also discussed.\r\n\r\n[\/panel]\r\n\r\n[panel header=\"Investigating Biological Nitrogen Fixation Using a Quantum Computer\"]\r\n\r\nSpeaker:<\/strong>\u00a0Nathan Wiebe\r\n\r\nWe showed how a quantum computer can be employed to elucidate reaction\u00a0mechanisms in complex chemical systems, using the open problem of biological nitrogen\u00a0fixation in nitrogenase as an example. We discussed how quantum computers can augment\u00a0classical-computer simulations for such problems, to significantly increase their accuracy and\u00a0enable hitherto intractable simulations. Detailed resource estimates show that, even when taking\u00a0into account the substantial overhead of quantum error correction, and the need to compile into\u00a0discrete gate sets, the necessary computations can be performed in reasonable time on small\u00a0quantum computers. This demonstrates that quantum computers will realistically be able to\u00a0tackle important problems in chemistry that are both scientifically and economically significant.\r\n\r\n[\/panel]\r\n\r\n[\/accordion]"}],"msr_startdate":"2016-07-15","msr_enddate":"","msr_event_time":"8:30 AM \u2013 5:30 PM","msr_location":"Redmond, WA, USA","msr_event_link":"","msr_event_recording_link":"","msr_startdate_formatted":"July 15, 2016","msr_register_text":"Watch now","msr_cta_link":"","msr_cta_text":"","msr_cta_bi_name":"","featured_image_thumbnail":null,"event_excerpt":"The workshop highlighted recent advances in quantum algorithms, quantum devices, control systems, and quantum error correction.","msr_research_lab":[199565],"related-researchers":[],"msr_impact_theme":[],"related-academic-programs":[],"related-groups":[],"related-projects":[],"related-opportunities":[],"related-publications":[],"related-videos":[],"related-posts":[],"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/295748"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-event"}],"version-history":[{"count":2,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/295748\/revisions"}],"predecessor-version":[{"id":549393,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event\/295748\/revisions\/549393"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=295748"}],"wp:term":[{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=295748"},{"taxonomy":"msr-region","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-region?post=295748"},{"taxonomy":"msr-event-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event-type?post=295748"},{"taxonomy":"msr-video-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-video-type?post=295748"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=295748"},{"taxonomy":"msr-program-audience","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-program-audience?post=295748"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=295748"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=295748"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}