**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Concept# Quantum algorithm

Résumé

In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.
Problems which are undecidable using classical computers remain undecidable using quantum computers. What makes quantum algorithms interesting is that they might be able to solve some problems faster than classical algorithms because the quantum superposition and quantum entanglement that quantum algorithms exploit probably cannot be efficiently simulated on classical computers (see Quantum supremacy).
The best-known algorithms are Shor's algorithm for factoring and Grover's algorithm for searching an unstructured database or an unordered list. Shor's algorithms runs much (almost exponentially) faster than the best-known classical algorithm for factoring, the general number field sieve. Grover's algorithm runs quadratically faster than the best possible classical algorithm for the same task, a linear search.
Quantum algorithms are usually described, in the commonly used circuit model of quantum computation, by a quantum circuit which acts on some input qubits and terminates with a measurement. A quantum circuit consists of simple quantum gates which act on at most a fixed number of qubits. The number of qubits has to be fixed because a changing number of qubits implies non-unitary evolution.

Source officielle

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (6)

Personnes associées (1)

Cours associés (21)

Concepts associés (30)

Quantum computing has received wide-spread attention lately due the possibility of a near-term breakthrough of quantum supremacy. This course acts as an introduction to the area of quantum computing.

After introducing the foundations of classical and quantum information theory, and quantum measurement, the course will address the theory and practice of digital quantum computing, covering fundament

Today one is able to manipulate matter at the nanoscale were quantum behavior becomes important and possibly information processing will have to take into account laws of quantum physics. We introduce

Porte quantique

En informatique quantique, et plus précisément dans le modèle de de calcul, une porte quantique (ou porte logique quantique) est un circuit quantique élémentaire opérant sur un petit nombre de qubits. Les portes quantiques sont les briques de base des circuits quantiques, comme le sont les portes logiques classiques pour des circuits numériques classiques. Contrairement à de nombreuses portes logiques classiques, les portes logiques quantique sont « réversibles ».

Quantum algorithm

In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer.

Algorithme de Shor

En arithmétique modulaire et en informatique quantique, l’algorithme de Shor est un algorithme quantique conçu par Peter Shor en 1994, qui factorise un entier naturel N en temps O et en espace . Beaucoup de cryptosystèmes à clé publique, tels que le RSA, deviendraient vulnérables si l'algorithme de Shor était un jour implanté dans un calculateur quantique pratique. Un message chiffré avec RSA peut être déchiffré par factorisation de sa clé publique N, qui est le produit de deux nombres premiers.

Séances de cours associées (209)

Délégation quantique de calcul

Couvre le concept de délégation quantique du calcul et la relation entre MIP et RE, en abordant les questions fréquentes et en discutant des matériaux utiles et des interactions avec les appareils quantiques.

Simulation quantique avec atomes froidsPHYS-744: Advanced Topics in Quantum Sciences and Technologies

Couvre les principes de la simulation quantique avec des atomes froids, y compris les potentiels dipôles optiques et les résonances de Feshbach.

Algorithmes NISQ et VQEPHYS-641: Quantum Computing

Explore les algorithmes NISQ, en mettant l'accent sur la méthode VQE et les techniques d'atténuation des erreurs.

Vincenzo Savona, Nathan Ramusat

Simulating the dynamics and the non-equilibrium steady state of an open quantum system are hard computational tasks on conventional computers. For the simulation of the time evolution, several efficient quantum algorithms have recently been developed. However, computing the non-equilibrium steady state as the long-time limit of the system dynamics is often not a viable solution, because of exceedingly long transient features or strong quantum correlations in the dynamics. Here, we develop an efficient quantum algorithm for the direct estimation of averaged expectation values of observables on the non-equilibrium steady state, thus bypassing the time integration of the master equation. The algorithm encodes the vectorized representation of the density matrix on a quantum register, and makes use of quantum phase estimation to approximate the eigenvector associated to the zero eigenvalue of the generator of the system dynamics. We show that the output state of the algorithm allows to estimate expectation values of observables on the steady state. Away from critical points, where the Liouvillian gap scales as a power law of the system size, the quantum algorithm performs with exponential advantage compared to exact diagonalization.

The enormous advancements in the ability to detect and manipulate single quantum states have lead to the emerging field of quantum technologies. Among these, quantum computation is the most far-reaching and challenging, aiming to solve problems that the classic computers could never address because of the exponential scaling, while quantum sensing exploits the ability to address single quantum states to realize ultra-sensitive and precise detectors. Defect centers in semiconductors play a primary role in these fields. The possibility to store information in the spin of their ground state, manipulate it through microwaves, and read it optically allows to use them as qubits. In addition, the very sharp dependence of their properties on temperature, strain and magnetic fields makes them very promising quantum sensors. In this Thesis we aim at contributing to the progress of quantum technologies both at the hardware and software level. From a hardware point of view, we study a key property of defect centers in semiconductors, the phonon-assisted luminescence, which can be measured to perform the readout of the information stored in a quantum bit, or to detect temperature variations. We predict the luminescence and study the exciton-phonon couplings within a rigorous many-body perturbation theory framework,an analysis that has never been performed for defect centers.In particular, we study the optical emission of the negatively-charged boron vacancy in 2D hexagonal boron nitride, which currently stands out among defect centers in 2D materials thanks to its promise for applications in quantum information and quantum sensing. We show that phonons are responsible for the observed luminescence, which otherwise would be dark due to symmetry. We also show that the symmetry breaking induced by the static Jahn-Teller effect is not able to describe the presence of the experimentally observed peak at 1.5 eV.The knowledge of the coupling between electrons and phonons is fundamental for the accurate prediction of all the features of the photoluminescence spectrum. However, the large number of atoms in a defect supercell hinders the possibility use density functional perturbation theory to study this coupling. In this work we present a finite-differences technique to calculate the electron-phonon matrix elements, which exploits the symmetries of the defect in such a way to use the very same set of displacement needed for the calculation of phonons. The computation of electron-phonon coupling thus becomes a simple post-processing of the finite-differences phonons calculation. On the quantum software side, we propose an improved quantum algorithm to calculate the Green's function through real-time propagation, and use it to compute the retarded Green's function for the 2-, 3- and 4-site Hubbard models. This novel protocol significantly reduces the number of controlled operations when compared to those previously suggested in literature. Such reduction is quite remarkable when considering the 2-site Hubbard model, for which we show that it is possible to obtain the exact time propagation of the $\ket{N\pm 1}$ states by exponentiating one single Pauli component of the Hamiltonian, allowing us to perform the calculations on an actual superconducting quantum processor.

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small fraction of edges of the graph controlled by a proximity parameter to get connected components of size independent of n. An important tool for sublinear algorithms and property testing for such classes is the partition oracle, introduced by the seminal work of Hassidim-Kelner-Nguyen-Onak (FOCS 2009). A partition oracle is a local procedure that gives consistent access to a hyperfinite decomposition, without any preprocessing. Given a query vertex v, the partition oracle outputs the component containing v in time independent of n. All the answers are consistent with a single hyperfinite decomposition. The partition oracle of Hassidim et al. runs in time exponential in the proximity parameter per query. They pose the open problem of whether partition oracles which run in time polynomial in reciprocal of proximity parameter can be built. Levi-Ron (ICALP 2013) give a refinement of the previous approach, to get a partition oracle that runs in quasipolynomial time per query. In this paper, we resolve this open problem and give polynomial time partition oracles (in reciprocal of proximity parameter) for bounded degree graphs in any minor-closed family. Unlike the previous line of work based on combinatorial methods, we employ techniques from spectral graph theory. We build on a recent spectral graph theoretical toolkit for minor-closed graph families, introduced by the authors to develop efficient property testers. A consequence of our result is an efficient property tester for any monotone and additive with running time property of minor-closed families (such as bipartite planar graphs). Our result also gives query efficient algorithms for additive approximations for problems such as maximum matching, minimum vertex cover, maximum independent set, and minimum dominating set for these graph families.