• ### Speeding-up the decision making of a learning agent using an ion trap quantum processor(1709.01366)

Dec. 19, 2018 quant-ph, cs.AI
We report a proof-of-principle experimental demonstration of the quantum speed-up for learning agents utilizing a small-scale quantum information processor based on radiofrequency-driven trapped ions. The decision-making process of a quantum learning agent within the projective simulation paradigm for machine learning is implemented in a system of two qubits. The latter are realized using hyperfine states of two frequency-addressed atomic ions exposed to a static magnetic field gradient. We show that the deliberation time of this quantum learning agent is quadratically improved with respect to comparable classical learning agents. The performance of this quantum-enhanced learning agent highlights the potential of scalable quantum processors taking advantage of machine learning.
• ### Faster quantum mixing for slowly evolving sequences of Markov chains(1503.01334)

Oct. 29, 2018 quant-ph, cs.AI, cs.DS
Markov chain methods are remarkably successful in computational physics, machine learning, and combinatorial optimization. The cost of such methods often reduces to the mixing time, i.e., the time required to reach the steady state of the Markov chain, which scales as $\delta^{-1}$, the inverse of the spectral gap. It has long been conjectured that quantum computers offer nearly generic quadratic improvements for mixing problems. However, except in special cases, quantum algorithms achieve a run-time of $\mathcal{O}(\sqrt{\delta^{-1}} \sqrt{N})$, which introduces a costly dependence on the Markov chain size $N,$ not present in the classical case. Here, we re-address the problem of mixing of Markov chains when these form a slowly evolving sequence. This setting is akin to the simulated annealing setting and is commonly encountered in physics, material sciences and machine learning. We provide a quantum memory-efficient algorithm with a run-time of $\mathcal{O}(\sqrt{\delta^{-1}} \sqrt[4]{N})$, neglecting logarithmic terms, which is an important improvement for large state spaces. Moreover, our algorithms output quantum encodings of distributions, which has advantages over classical outputs. Finally, we discuss the run-time bounds of mixing algorithms and show that, under certain assumptions, our algorithms are optimal.
• ### A note on state preparation for quantum machine learning(1804.00281)

April 1, 2018 quant-ph, stat.ML
The intersection between the fields of machine learning and quantum information processing is proving to be a fruitful field for the discovery of new quantum algorithms, which potentially offer an exponential speed-up over their classical counterparts. However, many such algorithms require the ability to produce states proportional to vectors stored in quantum memory. Even given access to quantum databases which store exponentially long vectors, the construction of which is considered a one-off overhead, it has been argued that the cost of preparing such amplitude-encoded states may offset any exponential quantum advantage. Here we argue that specifically in the context of machine learning applications it suffices to prepare a state close to the ideal state only in the $\infty$-norm, and that this can be achieved with only a constant number of memory queries.
• ### Neural Network Operations and Susuki-Trotter evolution of Neural Network States(1803.02118)

March 6, 2018 quant-ph
It was recently proposed to leverage the representational power of artificial neural networks, in particular Restricted Boltzmann Machines, in order to model complex quantum states of many-body systems [Science, 355(6325), 2017]. States represented in this way, called Neural Network States (NNSs), were shown to display interesting properties like the ability to efficiently capture long-range quantum correlations. However, identifying an optimal neural network representation of a given state might be challenging, and so far this problem has been addressed with stochastic optimization techniques. In this work we explore a different direction. We study how the action of elementary quantum operations modifies NNSs. We parametrize a family of many body quantum operations that can be directly applied to states represented by Unrestricted Boltzmann Machines, by just adding hidden nodes and updating the network parameters. We show that this parametrization contains a set of universal quantum gates, from which it follows that the state prepared by any quantum circuit can be expressed as a Neural Network State with a number of hidden nodes that grows linearly with the number of elementary operations in the circuit. This is a powerful representation theorem (which was recently obtained with different methods) but that is not directly useful, since there is no general and efficient way to extract information from this unrestricted description of quantum states. To circumvent this problem, we propose a step-wise procedure based on the projection of Unrestricted quantum states to Restricted quantum states. In turn, two approximate methods to perform this projection are discussed. In this way, we show that it is in principle possible to approximately optimize or evolve Neural Network States without relying on stochastic methods such as Variational Monte Carlo, which are computationally expensive.
• ### Active learning machine learns to create new quantum experiments(1706.00868)

Feb. 8, 2018 quant-ph, cs.AI, stat.ML
How useful can machine learning be in a quantum laboratory? Here we raise the question of the potential of intelligent machines in the context of scientific research. A major motivation for the present work is the unknown reachability of various entanglement classes in quantum experiments. We investigate this question by using the projective simulation model, a physics-oriented approach to artificial intelligence. In our approach, the projective simulation system is challenged to design complex photonic quantum experiments that produce high-dimensional entangled multiphoton states, which are of high interest in modern quantum experiments. The artificial intelligence system learns to create a variety of entangled states, and improves the efficiency of their realization. In the process, the system autonomously (re)discovers experimental techniques which are only now becoming standard in modern quantum optical experiments - a trait which was not explicitly demanded from the system but emerged through the process of learning. Such features highlight the possibility that machines could have a significantly more creative role in future research.
• ### Machine learning \& artificial intelligence in the quantum domain(1709.02779)

Sept. 8, 2017 quant-ph, cs.AI, cs.CV
Quantum information technologies, and intelligent learning systems, are both emergent technologies that will likely have a transforming impact on our society. The respective underlying fields of research -- quantum information (QI) versus machine learning (ML) and artificial intelligence (AI) -- have their own specific challenges, which have hitherto been investigated largely independently. However, in a growing body of recent work, researchers have been probing the question to what extent these fields can learn and benefit from each other. QML explores the interaction between quantum computing and ML, investigating how results and techniques from one field can be used to solve the problems of the other. Recently, we have witnessed breakthroughs in both directions of influence. For instance, quantum computing is finding a vital application in providing speed-ups in ML, critical in our "big data" world. Conversely, ML already permeates cutting-edge technologies, and may become instrumental in advanced quantum technologies. Aside from quantum speed-up in data analysis, or classical ML optimization used in quantum experiments, quantum enhancements have also been demonstrated for interactive learning, highlighting the potential of quantum-enhanced learning agents. Finally, works exploring the use of AI for the very design of quantum experiments, and for performing parts of genuine research autonomously, have reported their first successes. Beyond the topics of mutual enhancement, researchers have also broached the fundamental issue of quantum generalizations of ML/AI concepts. This deals with questions of the very meaning of learning and intelligence in a world that is described by quantum mechanics. In this review, we describe the main ideas, recent developments, and progress in a broad spectrum of research investigating machine learning and artificial intelligence in the quantum domain.
• ### Flexible resources for quantum metrology(1610.09999)

June 30, 2017 quant-ph
Quantum metrology offers a quadratic advantage over classical approaches to parameter estimation problems by utilizing entanglement and nonclassicality. However, the hurdle of actually implementing the necessary quantum probe states and measurements, which vary drastically for different metrological scenarios, is usually not taken into account. We show that for a wide range of tasks in metrology, 2D cluster states (a particular family of states useful for measurement-based quantum computation) can serve as flexible resources that allow one to efficiently prepare any required state for sensing, and perform appropriate (entangled) measurements using only single qubit operations. Crucially, the overhead in the number of qubits is less than quadratic, thus preserving the quantum scaling advantage. This is ensured by using a compression to a logarithmically sized space that contains all relevant information for sensing. We specifically demonstrate how our method can be used to obtain optimal scaling for phase and frequency estimation in local estimation problems, as well as for the Bayesian equivalents with Gaussian priors of varying widths. Furthermore, we show that in the paradigmatic case of local phase estimation 1D cluster states are sufficient for optimal state preparation and measurement.
• ### Skill Learning by Autonomous Robotic Playing using Active Learning and Creativity(1706.08560)

June 26, 2017 cs.RO
We treat the problem of autonomous acquisition of manipulation skills where problem-solving strategies are initially available only for a narrow range of situations. We propose to extend the range of solvable situations by autonomous playing with the object. By applying previously-trained skills and behaviours, the robot learns how to prepare situations for which a successful strategy is already known. The information gathered during autonomous play is additionally used to learn an environment model. This model is exploited for active learning and the creative generation of novel preparatory behaviours. We apply our approach on a wide range of different manipulation tasks, e.g. book grasping, grasping of objects of different sizes by selecting different grasping strategies, placement on shelves, and tower disassembly. We show that the creative behaviour generation mechanism enables the robot to solve previously-unsolvable tasks, e.g. tower disassembly. We use success statistics gained during real-world experiments to simulate the convergence behaviour of our system. Experiments show that active improves the learning speed by around 9 percent in the book grasping scenario.
• ### Quantum-enhanced machine learning(1610.08251)

Oct. 26, 2016 quant-ph, cs.AI, cs.LG
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.
• ### Entanglement generation secure against general attacks(1610.01907)

Oct. 6, 2016 quant-ph
We present a security proof for establishing private entanglement by means of recurrence-type entanglement distillation protocols. We consider protocols where the apparatus is imperfect, and show that nonetheless a secure quantum channel can be established, and used to e.g. perform distributed quantum computation in a secure manner. We assume an ultimately powerful eavesdropper distributing all pairs used in a subsequent distillation process by Alice and Bob, and show that even if the apparatus leaks the information about all noise processes that are realized during execution of the protocol to the eavesdropper - which arguably is the most general setting besides device independence - private entanglement is still achievable. We provide a proof of security under general quantum attacks without assuming asymptotic scenarios, by reducing such a general situation to an i.i.d. setting. Our approach relies on non-trivial properties of distillation protocols which are used in conjunction with de-Finetti and post-selection-type techniques. As a side result, we also provide entanglement distillation protocols for non-i.i.d. input states.
• ### Blind quantum computing with two almost identical states(1604.01586)

April 6, 2016 quant-ph, cs.CR
The question of whether a fully classical client can delegate a quantum computation to an untrusted quantum server while fully maintaining privacy (blindness) is one of the big open questions in quantum cryptography. Both yes and no answers have important practical and theoretical consequences, and the question seems genuinely hard. The state-of-the-art approaches to securely delegating quantum computation, without exception, rely on granting the client modest quantum powers, or on additional, non-communicating, quantum servers. In this work, we consider the single server setting, and push the boundaries of the minimal devices of the client, which still allow for blind quantum computation. Our approach is based on the observation that, in many blind quantum computing protocols, the "quantum" part of the protocol, from the clients perspective, boils down to the establishing classical-quantum correlations (independent from the computation) between the client and the server, following which the steering of the computation itself requires only classical communication. Here, we abstract this initial preparation phase, specifically for the Universal Blind Quantum Computation protocol of Broadbent, Fitzsimons and Kashefi. We identify sufficient criteria on the powers of the client, which still allow for secure blind quantum computation. We work in a universally composable framework, and provide a series of protocols, where each step reduces the number of differing states the client needs to be able to prepare. As the limit of such reductions, we show that the capacity to prepare just two pure states, which have an arbitrarily high overlap (thus are arbitrarily close to identical), suffices for efficient and secure blind quantum computation.
• ### Meta-learning within Projective Simulation(1602.08017)

Feb. 25, 2016 cs.AI, cs.LG, stat.ML
• ### Experimental demonstration of kilometer-range quantum digital signatures(1509.07827)

Sept. 25, 2015 quant-ph
We present an experimental realization of a quantum digital signature protocol which, together with a standard quantum key distribution link, increases transmission distance to kilometre ranges, three orders of magnitude larger than in previous realizations. The bit-rate is also significantly increased compared with previous quantum signature demonstrations. This work illustrates that quantum digital signatures can be realized with optical components similar to those used for quantum key distribution, and could be implemented in existing optical fiber networks.
• ### Framework for learning agents in quantum environments(1507.08482)

July 30, 2015 quant-ph, cs.AI, cs.LG
In this paper we provide a broad framework for describing learning agents in general quantum environments. We analyze the types of classically specified environments which allow for quantum enhancements in learning, by contrasting environments to quantum oracles. We show that whether or not quantum improvements are at all possible depends on the internal structure of the quantum environment. If the environments are constructed and the internal structure is appropriately chosen, or if the agent has limited capacities to influence the internal states of the environment, we show that improvements in learning times are possible in a broad range of scenarios. Such scenarios we call luck-favoring settings. The case of constructed environments is particularly relevant for the class of model-based learning agents, where our results imply a near-generic improvement.
• ### On optimising quantum communication in verifiable quantum computing(1506.06943)

June 23, 2015 quant-ph
In the absence of any efficient classical schemes for verifying a universal quantum computer, the importance of limiting the required quantum resources for this task has been highlighted recently. Currently, most of efficient quantum verification protocols are based on cryptographic techniques where an almost classical verifier executes her desired encrypted quantum computation remotely on an untrusted quantum prover. In this work we present a new protocol for quantum verification by incorporating existing techniques in a non-standard composition to reduce the required quantum communications between the verifier and the prover.
• ### Projective simulation with generalization(1504.02247)

April 9, 2015 cs.AI, cs.LG, stat.ML
The ability to generalize is an important feature of any intelligent agent. Not only because it may allow the agent to cope with large amounts of data, but also because in some environments, an agent with no generalization ability is simply doomed to fail. In this work we outline several criteria for generalization, and present a dynamic and autonomous machinery that enables projective simulation agents to meaningfully generalize. Projective simulation, a novel, physical, approach to artificial intelligence, was recently shown to perform well, in comparison with standard models, on both simple reinforcement learning problems, as well as on more complicated canonical tasks, such as the "grid world" and the "mountain car problem". Both the basic projective simulation model and the presented generalization machinery are based on very simple principles. This simplicity allows us to provide a full analytical analysis of the agent's performance and to illustrate the benefit the agent gains by generalizing. Specifically, we show how such an ability allows the agent to learn in rather extreme environments, in which learning is otherwise impossible.
• ### Quantum mixing of Markov chains for special distributions(1502.05511)

Feb. 19, 2015 quant-ph, cs.DS
The preparation of the stationary distribution of irreducible, time-reversible Markov chains is a fundamental building block in many heuristic approaches to algorithmically hard problems. It has been conjectured that quantum analogs of classical mixing processes may offer a generic quadratic speed-up in realizing such stationary distributions. Such a speed-up would also imply a speed-up of a broad family of heuristic algorithms. However, a true quadratic speed up has thus far only been demonstrated for special classes of Markov chains. These results often presuppose a regular structure of the underlying graph of the Markov chain, and also a regularity in the transition probabilities. In this work, we demonstrate a true quadratic speed-up for a class of Markov chains where the restriction is only on the form of the stationary distribution, rather than directly on the Markov chain structure itself. In particular, we show efficient mixing can be achieved when it is beforehand known that the distribution is monotonically decreasing relative to a known order on the state space. Following this, we show that our approach extends to a wider class of distributions, where only a fraction of the shape of the distribution is known to be monotonic. Our approach is built on the Szegedy-type quantization of transition operators.
• ### Quantum-enhanced deliberation of learning agents using trapped ions(1407.2830)

Jan. 31, 2015 quant-ph
A scheme that successfully employs quantum mechanics in the design of autonomous learning agents has recently been reported in the context of the projective simulation (PS) model for artificial intelligence. In that approach, the key feature of a PS agent, a specific type of memory which is explored via random walks, was shown to be amenable to quantization. In particular, classical random walks were substituted by Szegedy-type quantum walks, allowing for a speed-up. In this work we propose how such classical and quantum agents can be implemented in systems of trapped ions. We employ a generic construction by which the classical agents are `upgraded' to their quantum counterparts by nested coherent controlization, and we outline how this construction can be realized in ion traps. Our results provide a flexible modular architecture for the design of PS agents. Furthermore, we present numerical simulations of simple PS agents which analyze the robustness of our proposal under certain noise models.
• ### Enhanced delegated computing using coherence(1501.06730)

Jan. 27, 2015 quant-ph
A long-standing question is whether it is possible to delegate computational tasks securely. Recently, both a classical and a quantum solution to this problem were found. Here, we study the interplay of classical and quantum approaches and show how coherence can be used as a tool for secure delegated classical computation. We show that a client with limited computational capacity - restricted to an XOR gate - can perform universal classical computation by manipulating information carriers that may occupy superpositions of two states. Using single photonic qubits or coherent light, we experimentally implement secure delegated classical computations between an independent client and a server. The server has access to the light sources and measurement devices, whereas the client may use only a restricted set of passive optical devices to manipulate the light beams. Thus, our work highlights how minimal quantum and classical resources can be combined and exploited for classical computing.
• ### Quantum digital signatures with quantum key distribution components(1403.5551)

Nov. 22, 2014 quant-ph
Digital signatures guarantee the authenticity and transferability of messages, and are widely used in modern communication. The security of currently used classical digital signature schemes, however, relies on computational assumptions. In contrast, quantum digital signature (QDS) schemes offer information-theoretic security guaranteed by the laws of quantum mechanics. We present two QDS protocols which have the same experimental requirements as quantum key distribution, which is already commercially available. We also present the first security proof for any QDS scheme against coherent forging attacks.
• ### Composable security of delegated quantum computation(1301.3662)

Sept. 13, 2014 quant-ph, cs.IT, math.IT, cs.CR
Delegating difficult computations to remote large computation facilities, with appropriate security guarantees, is a possible solution for the ever-growing needs of personal computing power. For delegated computation protocols to be usable in a larger context---or simply to securely run two protocols in parallel---the security definitions need to be composable. Here, we define composable security for delegated quantum computation. We distinguish between protocols which provide only blindness---the computation is hidden from the server---and those that are also verifiable---the client can check that it has received the correct result. We show that the composable security definition capturing both these notions can be reduced to a combination of several distinct "trace-distance-type" criteria---which are, individually, non-composable security definitions. Additionally, we study the security of some known delegated quantum computation protocols, including Broadbent, Fitzsimons and Kashefi's Universal Blind Quantum Computation protocol. Even though these protocols were originally proposed with insufficient security criteria, they turn out to still be secure given the stronger composable definitions.
• ### Quantum speedup for active learning agents(1401.4997)

July 14, 2014 quant-ph
Can quantum mechanics help us in building intelligent robots and agents? One of the defining characteristics of intelligent behavior is the capacity to learn from experience. However, a major bottleneck for agents to learn in any real-life situation is the size and complexity of the corresponding task environment. Owing to, e.g., a large space of possible strategies, learning is typically slow. Even for a moderate task environment, it may simply take too long to rationally respond to a given situation. If the environment is impatient, allowing only a certain time for a response, an agent may then be unable to cope with the situation and to learn at all. Here we show that quantum physics can help and provide a significant speed-up for active learning as a genuine problem of artificial intelligence. We introduce a large class of quantum learning agents for which we show a quadratic boost in their active learning efficiency over their classical analogues. This result will be particularly relevant for applications involving complex task environments.
• ### Entanglement of $\pi$-LME states and the SAT problem(1405.7429)

May 29, 2014 quant-ph
In this paper we investigate the entanglement properties of the class of $\pi$-locally maximally entanglable ($\pi$-LME) states, which are also known as the "real equally weighted states" or the "hypergraph states". The $\pi$-LME states comprise well-studied classes of quantum states (e.g. graph states) and exhibit a large degree of symmetry. Motivated by the structure of LME states, we show that the capacity to (efficiently) determine if a $\pi$-LME state is entangled would imply an efficient solution to the boolean satisfiability (SAT) problem. More concretely, we show that this particular problem of entanglement detection, phrased as a decision problem, is $\mathsf{NP}$-complete. The restricted setting we consider yields a technically uninvolved proof, and illustrates that entanglement detection, even when quantum states under consideration are highly restricted, still remains difficult.
• ### Quantum-enhanced Secure Delegated Classical Computing(1405.4558)

May 18, 2014 quant-ph
We present a quantumly-enhanced protocol to achieve unconditionally secure delegated classical computation where the client and the server have both limited classical and quantum computing capacity. We prove the same task cannot be achieved using only classical protocols. This extends the work of Anders and Browne on the computational power of correlations to a security setting. Concretely, we present how a client with access to a non-universal classical gate such as a parity gate could achieve unconditionally secure delegated universal classical computation by exploiting minimal quantum gadgets. In particular, unlike the universal blind quantum computing protocols, the restriction of the task to classical computing removes the need for a full universal quantum machine on the side of the server and makes these new protocols readily implementable with the currently available quantum technology in the lab.
• ### Realization of Quantum Digital Signatures without the requirement of quantum memory(1311.5760)

May 14, 2014 quant-ph
Digital signatures are widely used to provide security for electronic communications, for example in financial transactions and electronic mail. Currently used classical digital signature schemes, however, only offer security relying on unproven computational assumptions. In contrast, quantum digital signatures (QDS) offer information-theoretic security based on laws of quantum mechanics (e.g. Gottesman and Chuang 2001). Here, security against forging relies on the impossibility of perfectly distinguishing between non-orthogonal quantum states. A serious drawback of previous QDS schemes is however that they require long-term quantum memory, making them unfeasible in practice. We present the first realisation of a scheme (Dunjko et al 2013) that does not need quantum memory, and which also uses only standard linear optical components and photodetectors. To achieve this, the recipients measure the distributed quantum signature states using a new type of quantum measurement, quantum state elimination (e.g. Barnett 2009, Bandyopadhyay et al 2013). This significantly advances QDS as a quantum technology with potential for real applications.