Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Deutsch-Jozsa Algorithm

Description

This lecture covers the Deutsch-Jozsa algorithm, which determines if a function is constant or balanced with a single query. It explains the quantum oracle, the Deutsch algorithm, and the Deutsch-Jozsa algorithm step by step, highlighting the difference between classical and quantum computing.

Official source

Ontological neighbourhood

Theoretical computer science

Theory of computation: Quantum computing

Related concepts (32)

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.

Quantum computing

A quantum computer is a computer that exploits quantum mechanical phenomena. At small scales, physical matter exhibits properties of both particles and waves, and quantum computing leverages this behavior, specifically quantum superposition and entanglement, using specialized hardware that supports the preparation and manipulation of quantum states. Classical physics cannot explain the operation of these quantum devices, and a scalable quantum computer could perform some calculations exponentially faster than any modern "classical" computer.

Quantum complexity theory

Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical (i.e., non-quantum) complexity classes. Two important quantum complexity classes are BQP and QMA.

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).

Shor's algorithm

Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical (that is, non-quantum) algorithms. On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future.

Related lectures (55)

The Deutsch and Deutsch-Jozsa Algorithms

Covers the Deutsch and Deutsch-Jozsa algorithms in quantum computing, explaining the principles behind them and their implications.

Deutsch Algorithm

Covers the Deutsch Algorithm for determining if a function is constant or balanced using quantum computing.

Quantum Computing: NISQ and Grover's Algorithm

Covers NISQ computing, error correction, quantum algorithm complexity, and Grover's search algorithm.

Quantum computing: basics

Introduces the basics of quantum computing, covering qubits, superposition, entanglement, quantum gates, and algorithms, highlighting the efficiency of quantum computation.

Quantum Computing: Hardware Technologies and Applications