**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Lecture# Quantum Computation: Grover Algorithm

Description

This lecture covers the Grover algorithm, a quantum search algorithm that provides a quadratic speedup over classical algorithms for unstructured search problems. The algorithm's principles, implementation, and applications are discussed, focusing on how it achieves a significant speedup in searching unsorted databases.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

In course

CS-308: Quantum computation

The course introduces teh paradigm of quantum computation in an axiomatic way. We introduce the notion of quantum bit, gates, circuits and we treat the most important quantum algorithms. We also touch

Instructors (3)

Related concepts (100)

Grover's algorithm

In quantum computing, Grover's algorithm, also known as the quantum search algorithm, refers to a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just evaluations of the function, where is the size of the function's domain. It was devised by Lov Grover in 1996. The analogous problem in classical computation cannot be solved in fewer than evaluations (because, on average, one has to check half of the domain to get a 50% chance of finding the right input).

Search algorithm

In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values. Although search engines use search algorithms, they belong to the study of information retrieval, not algorithmics. The appropriate search algorithm to use often depends on the data structure being searched, and may also include prior knowledge about the data.

Controlled NOT gate

In computer science, the controlled NOT gate (also C-NOT or CNOT), controlled-X gate, controlled-bit-flip gate, Feynman gate or controlled Pauli-X is a quantum logic gate that is an essential component in the construction of a gate-based quantum computer. It can be used to entangle and disentangle Bell states. Any quantum circuit can be simulated to an arbitrary degree of accuracy using a combination of CNOT gates and single qubit rotations. The gate is sometimes named after Richard Feynman who developed an early notation for quantum gate diagrams in 1986.

Quantum logic gate

In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate (or simply quantum gate) is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits. Unlike many classical logic gates, quantum logic gates are reversible. It is possible to perform classical computing using only reversible gates.

Bell state

The Bell's states or EPR pairs are specific quantum states of two qubits that represent the simplest examples of quantum entanglement; conceptually, they fall under the study of quantum information science. The Bell's states are a form of entangled and normalized basis vectors. This normalization implies that the overall probability of the particle being in one of the mentioned states is 1: . Entanglement is a basis-independent result of superposition.

Related lectures (62)

Quantum Random Number GenerationPHYS-758: Advanced Course on Quantum Communication

Explores quantum random number generation, discussing the challenges and implementations of generating good randomness using quantum devices.

Scaling in Quantum Field Theory

Explores scaling in quantum field theory, emphasizing primary operators and conformal transformations.

Understanding Chaos in Quantum Field Theories

Explores chaos in quantum field theories, focusing on conformal symmetry, OPE coefficients, and random matrix universality.

Quantum Source CodingPHYS-758: Advanced Course on Quantum Communication

Covers entropic notions in quantum sources, Shannon entropy, Von Neumann entropy, and source coding.

Quantum EntanglementPHYS-758: Advanced Course on Quantum Communication

Explores quantum entanglement, Bell inequalities, and self-testing in quantum systems.