1
|
He X, Zhao WT, Lv WC, Peng CH, Sun Z, Sun YN, Su QP, Yang CP. Experimental demonstration of deterministic quantum search for multiple marked states without adjusting the oracle. OPTICS LETTERS 2023; 48:4428-4431. [PMID: 37656520 DOI: 10.1364/ol.497599] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/14/2023] [Accepted: 07/30/2023] [Indexed: 09/03/2023]
Abstract
Grover's search algorithm is a well-known quantum algorithm that has been extensively studied and improved to increase its success rate and enhance its flexibility. However, most improved search algorithms require an adjustment of the oracle, which may not be feasible in practical problem-solving scenarios. In this work, we report an experimental demonstration of a deterministic quantum search for multiple marked states without adjusting the oracle. A linear optical setup is designed to search for two marked states, one in a 16-state database with an initial equal-superposition state and the other in an 8-state database with different initial nonequal-superposition states. The evolution of the probability of finding each state in the database is also measured and displayed. Our experimental results agree well with the theoretical predictions, thereby proving the feasibility of the search protocol and the implementation scheme. This work is a pioneering experimental demonstration of deterministic quantum search for multiple marked states without adjusting the oracle.
Collapse
|
2
|
Holbrook AJ. A quantum parallel Markov chain Monte Carlo. J Comput Graph Stat 2023; 32:1402-1415. [PMID: 38127472 PMCID: PMC10723820 DOI: 10.1080/10618600.2023.2195890] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/13/2022] [Accepted: 03/19/2023] [Indexed: 04/03/2023]
Abstract
We propose a novel hybrid quantum computing strategy for parallel MCMC algorithms that generate multiple proposals at each step. This strategy makes the rate-limiting step within parallel MCMC amenable to quantum parallelization by using the Gumbel-max trick to turn the generalized accept-reject step into a discrete optimization problem. When combined with new insights from the parallel MCMC literature, such an approach allows us to embed target density evaluations within a well-known extension of Grover's quantum search algorithm. Letting P d e n o t e t h e n u m b e r o f p r o p o s a l s i n a s i n g l e M C M C i t e r a t i o n , t h e c o m b i n e d s t r a t e g y r e d u c e s t h e n u m b e r o f t a r g e t e v a l u a t i o n s r e q u i r e d f r o m 𝒪 ( P ) t o 𝒪 P 1 / 2 . In the following, we review the rudiments of quantum computing, quantum search and the Gumbel-max trick in order to elucidate their combination for as wide a readership as possible.
Collapse
|
3
|
Liu Y, Meitei OR, Chin ZE, Dutt A, Tao M, Chuang IL, Van Voorhis T. Bootstrap Embedding on a Quantum Computer. J Chem Theory Comput 2023; 19:2230-2247. [PMID: 37001026 DOI: 10.1021/acs.jctc.3c00012] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 04/03/2023]
Abstract
We extend molecular bootstrap embedding to make it appropriate for implementation on a quantum computer. This enables solution of the electronic structure problem of a large molecule as an optimization problem for a composite Lagrangian governing fragments of the total system, in such a way that fragment solutions can harness the capabilities of quantum computers. By employing state-of-art quantum subroutines including the quantum SWAP test and quantum amplitude amplification, we show how a quadratic speedup can be obtained over the classical algorithm, in principle. Utilization of quantum computation also allows the algorithm to match─at little additional computational cost─full density matrices at fragment boundaries, instead of being limited to 1-RDMs. Current quantum computers are small, but quantum bootstrap embedding provides a potentially generalizable strategy for harnessing such small machines through quantum fragment matching.
Collapse
Affiliation(s)
- Yuan Liu
- Department of Physics, Co-Design Center for Quantum Advantage, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, United States
| | - Oinam R. Meitei
- Department of Chemistry, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, United States
| | - Zachary E. Chin
- Department of Physics, Co-Design Center for Quantum Advantage, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, United States
| | - Arkopal Dutt
- Department of Mechanical Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, United States
| | - Max Tao
- Department of Physics, Co-Design Center for Quantum Advantage, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, United States
| | - Isaac L. Chuang
- Department of Physics, Co-Design Center for Quantum Advantage, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, United States
- Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, United States
| | - Troy Van Voorhis
- Department of Chemistry, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, United States
| |
Collapse
|
4
|
Weidner FM, Schwab JD, Wölk S, Rupprecht F, Ikonomi N, Werle SD, Hoffmann S, Kühl M, Kestler HA. Leveraging quantum computing for dynamic analyses of logical networks in systems biology. PATTERNS (NEW YORK, N.Y.) 2023; 4:100705. [PMID: 36960443 PMCID: PMC10028428 DOI: 10.1016/j.patter.2023.100705] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Received: 09/06/2022] [Revised: 12/12/2022] [Accepted: 02/09/2023] [Indexed: 03/12/2023]
Abstract
The dynamics of cellular mechanisms can be investigated through the analysis of networks. One of the simplest but most popular modeling strategies involves logic-based models. However, these models still face exponential growth in simulation complexity compared with a linear increase in nodes. We transfer this modeling approach to quantum computing and use the upcoming technique in the field to simulate the resulting networks. Leveraging logic modeling in quantum computing has many benefits, including complexity reduction and quantum algorithms for systems biology tasks. To showcase the applicability of our approach to systems biology tasks, we implemented a model of mammalian cortical development. Here, we applied a quantum algorithm to estimate the tendency of the model to reach particular stable conditions and further revert dynamics. Results from two actual quantum processing units and a noisy simulator are presented, and current technical challenges are discussed.
Collapse
Affiliation(s)
- Felix M. Weidner
- Institute of Medical Systems Biology, Ulm University, 89081 Ulm, Germany
- International Graduate School of Molecular Medicine, Ulm University, 89081 Ulm, Germany
| | - Julian D. Schwab
- Institute of Medical Systems Biology, Ulm University, 89081 Ulm, Germany
| | - Sabine Wölk
- Institute of Quantum Technologies, DLR Ulm, 89081 Ulm, Germany
| | - Felix Rupprecht
- Institute of Quantum Technologies, DLR Ulm, 89081 Ulm, Germany
| | - Nensi Ikonomi
- Institute of Medical Systems Biology, Ulm University, 89081 Ulm, Germany
- International Graduate School of Molecular Medicine, Ulm University, 89081 Ulm, Germany
| | - Silke D. Werle
- Institute of Medical Systems Biology, Ulm University, 89081 Ulm, Germany
| | - Steve Hoffmann
- Leibniz Institute on Aging, Fritz Lipmann Institute, 07745 Jena, Germany
| | - Michael Kühl
- Institute of Biochemistry and Molecular Biology, Ulm University, 89081 Ulm, Germany
| | - Hans A. Kestler
- Institute of Medical Systems Biology, Ulm University, 89081 Ulm, Germany
- Corresponding author
| |
Collapse
|
5
|
Delgado F, Cardoso-Isidoro C. Non-Local Parallel Processing and Database Settlement Using Multiple Teleportation Followed by Grover Post-Selection. ENTROPY (BASEL, SWITZERLAND) 2023; 25:376. [PMID: 36832742 PMCID: PMC9955167 DOI: 10.3390/e25020376] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 09/14/2022] [Revised: 12/04/2022] [Accepted: 12/22/2022] [Indexed: 06/18/2023]
Abstract
Quantum information applications emerged decades ago, initially introducing a parallel development that mimicked the approach and development of classical computer science. However, in the current decade, novel computer-science concepts were rapidly extended to the fields of quantum processing, computation, and communication. Thus, areas such as artificial intelligence, machine learning, and neural networks have their quantum versions; furthermore, the quantum brain properties of learning, analyzing, and gaining knowledge are discussed. Quantum properties of matter conglomerates have been superficially explored in such terrain; however, the settlement of organized quantum systems able to perform processing can open a new pathway in the aforementioned domains. In fact, quantum processing involves certain requisites as the settlement of copies of input information to perform differentiated processing developed far away or in situ to diversify the information stored there. Both tasks at the end provide a database of outcomes with which to perform either information matching or final global processing with at least a subset of those outcomes. When the number of processing operations and input information copies is large, parallel processing (a natural feature in quantum computation due to the superposition) becomes the most convenient approach to accelerate the database settlement of outcomes, thus affording a time advantage. In the current study, we explored certain quantum features to realize a speed-up model for the entire task of processing based on a common information input to be processed, diversified, and finally summarized to gain knowledge, either in pattern matching or global information availability. By using superposition and non-local properties, the most valuable features of quantum systems, we realized parallel local processing to set a large database of outcomes and subsequently used post-selection to perform an ending global processing or a matching of information incoming from outside. We finally analyzed the details of the entire procedure, including its affordability and performance. The quantum circuit implementation, along with tentative applications, were also discussed. Such a model could be operated between large processing technological systems using communication procedures and also on a moderately controlled quantum matter conglomerate. Certain interesting technical aspects involving the non-local control of processing via entanglement were also analyzed in detail as an associated but notable premise.
Collapse
Affiliation(s)
- Francisco Delgado
- Tecnologico de Monterrey, School of Engineering and Science, Atizapan 52926, Mexico
| | | |
Collapse
|
6
|
Zhu Y. Quantum-Solving Algorithm for d'Alembert Solutions of the Wave Equation. ENTROPY (BASEL, SWITZERLAND) 2022; 25:62. [PMID: 36673203 PMCID: PMC9858167 DOI: 10.3390/e25010062] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 11/04/2022] [Revised: 12/19/2022] [Accepted: 12/20/2022] [Indexed: 06/17/2023]
Abstract
When faced with a quantum-solving problem for partial differential equations, people usually transform such problems into Hamiltonian simulation problems or quantum-solving problems for linear equation systems. In this paper, we propose a third approach to solving partial differential equations that differs from the two approaches. By using the duality quantum algorithm, we construct a quantum-solving algorithm for solving the first-order wave equation, which represents a typical class of partial differential equations. Numerical results of the quantum circuit have high precision consistency with the theoretical d'Alembert solution. Then the routine is applied to the wave equation with either a dissipation or dispersion term. As shown by complexity analysis for all these cases of the wave equation, our algorithm has a quadratic acceleration for each iteration compared to the classical algorithm.
Collapse
Affiliation(s)
- Yuanye Zhu
- Center on Frontiers of Computing Studies and School of Computer Science, Peking University, Beijing 100871, China;
- State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, China;
| |
Collapse
|
7
|
Fixed-point oblivious quantum amplitude-amplification algorithm. Sci Rep 2022; 12:14339. [PMID: 35995929 PMCID: PMC9395401 DOI: 10.1038/s41598-022-15093-x] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/17/2022] [Accepted: 06/17/2022] [Indexed: 11/24/2022] Open
Abstract
The quantum amplitude amplification algorithms based on Grover’s rotation operator need to perform phase flips for both the initial state and the target state. When the initial state is oblivious, the phase flips will be intractable, and we need to adopt oblivious amplitude amplification algorithm to handle. Without knowing exactly how many target items there are, oblivious amplitude amplification also suffers the “soufflé problem”, in which iterating too little “undercooks” the state and too much “overcooks” the state, both resulting in a mostly non-target final state. In this work, we present a fixed-point oblivious quantum amplitude-amplification (FOQA) algorithm by introducing damping based on methods proposed by A. Mizel. Moreover, we construct the quantum circuit to implement our algorithm under the framework of duality quantum computing. Our algorithm can avoid the “soufflé problem”, meanwhile keep the square speedup of quantum search, serving as a subroutine to improve the performance of quantum algorithms containing oblivious amplitude amplification procedure.
Collapse
|
8
|
Qu D, Marsh S, Wang K, Xiao L, Wang J, Xue P. Deterministic Search on Star Graphs via Quantum Walks. PHYSICAL REVIEW LETTERS 2022; 128:050501. [PMID: 35179941 DOI: 10.1103/physrevlett.128.050501] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 05/27/2021] [Revised: 10/29/2021] [Accepted: 01/10/2022] [Indexed: 06/14/2023]
Abstract
We propose a novel algorithm for quantum spatial search on a star graph using interleaved continuous-time quantum walks and marking oracle queries. Initializing the system in the star's central vertex, we determine the optimal quantum walk times to reach full overlap with the marked state using ⌈(π/4)sqrt[N]-(1/2)⌉ oracle queries, matching the well-known lower bound of Grover's search. We implement the deterministic search in a database of size seven on photonic quantum hardware, and demonstrate the effective scaling of the approach up to size 115. This is the first experimental demonstration of quantum walk-based search on the highly noise-resistant star graph, which provides new evidence for the applications of quantum walk in quantum algorithms and quantum information processing.
Collapse
Affiliation(s)
- Dengke Qu
- Beijing Computational Science Research Center, Beijing 100084, China
- Department of Physics, Southeast University, Nanjing 211189, China
| | - Samuel Marsh
- Department of Physics, The University of Western Australia, Perth 6009, Australia
| | - Kunkun Wang
- Beijing Computational Science Research Center, Beijing 100084, China
| | - Lei Xiao
- Beijing Computational Science Research Center, Beijing 100084, China
| | - Jingbo Wang
- Department of Physics, The University of Western Australia, Perth 6009, Australia
| | - Peng Xue
- Beijing Computational Science Research Center, Beijing 100084, China
| |
Collapse
|
9
|
Zhu Y, Wang Z, Yan B, Wei S. Robust Quantum Search with Uncertain Number of Target States. ENTROPY 2021; 23:e23121649. [PMID: 34945955 PMCID: PMC8700126 DOI: 10.3390/e23121649] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 11/03/2021] [Revised: 11/30/2021] [Accepted: 12/04/2021] [Indexed: 11/25/2022]
Abstract
The quantum search algorithm is one of the milestones of quantum algorithms. Compared with classical algorithms, it shows quadratic speed-up when searching marked states in an unsorted database. However, the success rates of quantum search algorithms are sensitive to the number of marked states. In this paper, we study the relation between the success rate and the number of iterations in a quantum search algorithm of given λ=M/N, where M is the number of marked state and N is the number of items in the dataset. We develop a robust quantum search algorithm based on Grover–Long algorithm with some uncertainty in the number of marked states. The proposed algorithm has the same query complexity ON as the Grover’s algorithm, and shows high tolerance of the uncertainty in the ratio M/N. In particular, for a database with an uncertainty in the ratio M±MN, our algorithm will find the target states with a success rate no less than 96%.
Collapse
Affiliation(s)
- Yuanye Zhu
- State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, China; (Y.Z.); (Z.W.); (B.Y.)
| | - Zeguo Wang
- State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, China; (Y.Z.); (Z.W.); (B.Y.)
| | - Bao Yan
- State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, China; (Y.Z.); (Z.W.); (B.Y.)
- State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China
| | - Shijie Wei
- State Key Laboratory of Low-Dimensional Quantum Physics and Department of Physics, Tsinghua University, Beijing 100084, China; (Y.Z.); (Z.W.); (B.Y.)
- Beijing Academy of Quantum Information Sciences, Beijing 100193, China
- Correspondence:
| |
Collapse
|
10
|
Hamann A, Dunjko V, Wölk S. Quantum-accessible reinforcement learning beyond strictly epochal environments. QUANTUM MACHINE INTELLIGENCE 2021; 3:22. [PMID: 34723097 PMCID: PMC8550166 DOI: 10.1007/s42484-021-00049-7] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 08/27/2020] [Accepted: 05/07/2021] [Indexed: 06/13/2023]
Abstract
In recent years, quantum-enhanced machine learning has emerged as a particularly fruitful application of quantum algorithms, covering aspects of supervised, unsupervised and reinforcement learning. Reinforcement learning offers numerous options of how quantum theory can be applied, and is arguably the least explored, from a quantum perspective. Here, an agent explores an environment and tries to find a behavior optimizing some figure of merit. Some of the first approaches investigated settings where this exploration can be sped-up, by considering quantum analogs of classical environments, which can then be queried in superposition. If the environments have a strict periodic structure in time (i.e. are strictly episodic), such environments can be effectively converted to conventional oracles encountered in quantum information. However, in general environments, we obtain scenarios that generalize standard oracle tasks. In this work, we consider one such generalization, where the environment is not strictly episodic, which is mapped to an oracle identification setting with a changing oracle. We analyze this case and show that standard amplitude-amplification techniques can, with minor modifications, still be applied to achieve quadratic speed-ups. In addition, we prove that an algorithm based on Grover iterations is optimal for oracle identification even if the oracle changes over time in a way that the "rewarded space" is monotonically increasing. This result constitutes one of the first generalizations of quantum-accessible reinforcement learning.
Collapse
Affiliation(s)
- A. Hamann
- Institut für Theoretische Physik, Universität Innsbruck, Technikerstraße 21a, 6020 Innsbruck, Austria
| | - V. Dunjko
- LIACS, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
| | - S. Wölk
- Institut für Theoretische Physik, Universität Innsbruck, Technikerstraße 21a, 6020 Innsbruck, Austria
- Present Address: Institute of Quantum Technologies, German Aerospace Center (DLR), D-89077 Ulm, Germany
| |
Collapse
|
11
|
Experimental quantum speed-up in reinforcement learning agents. Nature 2021; 591:229-233. [PMID: 33692560 PMCID: PMC7612051 DOI: 10.1038/s41586-021-03242-7] [Citation(s) in RCA: 23] [Impact Index Per Article: 7.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/12/2020] [Accepted: 01/15/2021] [Indexed: 11/10/2022]
Abstract
As the field of artificial intelligence advances, the demand for
algorithms that can learn quickly and efficiently increases. An important
paradigm within artificial intelligence is reinforcement learning [1], where decision-making entities called
agents interact with environments and learn by updating their behaviour based on
obtained feedback. The crucial question for practical applications is how fast
agents learn [2]. While various works have
made use of quantum mechanics to speed up the agent’s decision-making
process [3, 4], a reduction in learning time has not been demonstrated yet.
Here, we present a reinforcement learning experiment where the learning process
of an agent is sped up by utilizing a quantum communication channel with the
environment. We further show that combining this scenario with classical
communication enables the evaluation of such an improvement, and additionally
allows for optimal control of the learning progress. We implement this learning
protocol on a compact and fully tuneable integrated nanophotonic processor. The
device interfaces with telecom-wavelength photons and features a fast active
feedback mechanism, allowing us to demonstrate the agent’s systematic
quantum ad-vantage in a setup that could be readily integrated within future
large-scale quantum communication networks.
Collapse
|
12
|
Byrnes T, Forster G, Tessler L. Generalized Grover's Algorithm for Multiple Phase Inversion States. PHYSICAL REVIEW LETTERS 2018; 120:060501. [PMID: 29481268 DOI: 10.1103/physrevlett.120.060501] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 07/01/2016] [Revised: 11/13/2017] [Indexed: 06/08/2023]
Abstract
Grover's algorithm is a quantum search algorithm that proceeds by repeated applications of the Grover operator and the Oracle until the state evolves to one of the target states. In the standard version of the algorithm, the Grover operator inverts the sign on only one state. Here we provide an exact solution to the problem of performing Grover's search where the Grover operator inverts the sign on N states. We show the underlying structure in terms of the eigenspectrum of the generalized Hamiltonian, and derive an appropriate initial state to perform the Grover evolution. This allows us to use the quantum phase estimation algorithm to solve the search problem in this generalized case, completely bypassing the Grover algorithm altogether. We obtain a time complexity of this case of sqrt[D/M^{α}], where D is the search space dimension, M is the number of target states, and α≈1, which is close to the optimal scaling.
Collapse
Affiliation(s)
- Tim Byrnes
- State Key Laboratory of Precision Spectroscopy, School of Physical and Material Sciences, East China Normal University, Shanghai 200062, China
- New York University Shanghai, 1555 Century Ave, Pudong, Shanghai 200122, China
- NYU-ECNU Institute of Physics at NYU Shanghai, 3663 Zhongshan Road North, Shanghai 200062, China
- National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
- Department of Physics, New York University, New York, New York 10003, USA
| | - Gary Forster
- National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan
- Department of Physics, University of Bath, Bath BA2 7AY, United Kingdom
| | - Louis Tessler
- New York University Shanghai, 1555 Century Ave, Pudong, Shanghai 200122, China
- CEMS, RIKEN, Wako-shi, Saitama 351-0198, Japan
| |
Collapse
|
13
|
Low GH, Chuang IL. Optimal Hamiltonian Simulation by Quantum Signal Processing. PHYSICAL REVIEW LETTERS 2017; 118:010501. [PMID: 28106413 DOI: 10.1103/physrevlett.118.010501] [Citation(s) in RCA: 42] [Impact Index Per Article: 6.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/08/2016] [Indexed: 06/06/2023]
Abstract
The physics of quantum mechanics is the inspiration for, and underlies, quantum computation. As such, one expects physical intuition to be highly influential in the understanding and design of many quantum algorithms, particularly simulation of physical systems. Surprisingly, this has been challenging, with current Hamiltonian simulation algorithms remaining abstract and often the result of sophisticated but unintuitive constructions. We contend that physical intuition can lead to optimal simulation methods by showing that a focus on simple single-qubit rotations elegantly furnishes an optimal algorithm for Hamiltonian simulation, a universal problem that encapsulates all the power of quantum computation. Specifically, we show that the query complexity of implementing time evolution by a d-sparse Hamiltonian H[over ^] for time-interval t with error ε is O[td∥H[over ^]∥_{max}+log(1/ε)/loglog(1/ε)], which matches lower bounds in all parameters. This connection is made through general three-step "quantum signal processing" methodology, comprised of (i) transducing eigenvalues of H[over ^] into a single ancilla qubit, (ii) transforming these eigenvalues through an optimal-length sequence of single-qubit rotations, and (iii) projecting this ancilla with near unity success probability.
Collapse
Affiliation(s)
- Guang Hao Low
- Department of Physics, Center for Ultracold Atoms, and Research Laboratory of Electronics Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
| | - Isaac L Chuang
- Department of Physics, Center for Ultracold Atoms, and Research Laboratory of Electronics Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
| |
Collapse
|
14
|
Dunjko V, Taylor JM, Briegel HJ. Quantum-Enhanced Machine Learning. PHYSICAL REVIEW LETTERS 2016; 117:130501. [PMID: 27715099 DOI: 10.1103/physrevlett.117.130501] [Citation(s) in RCA: 34] [Impact Index Per Article: 4.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/15/2016] [Indexed: 06/06/2023]
Abstract
The emerging field of quantum machine learning has the potential to substantially aid in the problems and scope of artificial intelligence. This is only enhanced by recent successes in the field of classical machine learning. In this work we propose an approach for the systematic treatment of machine learning, from the perspective of quantum information. Our approach is general and covers all three main branches of machine learning: supervised, unsupervised, and reinforcement learning. While quantum improvements in supervised and unsupervised learning have been reported, reinforcement learning has received much less attention. Within our approach, we tackle the problem of quantum enhancements in reinforcement learning as well, and propose a systematic scheme for providing improvements. As an example, we show that quadratic improvements in learning efficiency, and exponential improvements in performance over limited time periods, can be obtained for a broad class of learning problems.
Collapse
Affiliation(s)
- Vedran Dunjko
- Institut für Theoretische Physik, Universität Innsbruck, Technikerstraße 21a, A-6020 Innsbruck, Austria
| | - Jacob M Taylor
- Joint Quantum Institute, National Institute of Standards and Technology, Gaithersburg, Maryland 20899, USA
- Joint Center for Quantum Information and Computer Science, University of Maryland, College Park, Maryland 20742, USA
| | - Hans J Briegel
- Institut für Theoretische Physik, Universität Innsbruck, Technikerstraße 21a, A-6020 Innsbruck, Austria
| |
Collapse
|