Algorithms and Quantum Algorithms Lecture Notes

Algorithms and Quantum Algorithms

What is an Algorithm?

• An algorithm is a well-defined, step-by-step procedure or set of rules designed to solve a specific problem or perform a particular task. It provides a systematic method that, when followed, guarantees a solution, if one exists.

• Problem: Each instance of a problem has a solution.

  • Example: Determining whether an integer $p$ is a prime number is a classic problem in number theory.

    • Instance: A specific integer chosen for primality testing, such as 7, 15, or 29.

    • Solution: A definitive answer of 'yes' or 'no,' indicating whether the given integer is prime or composite.

• Example algorithm: A program PRIMALITY($p$) that takes an integer $p ≥ 2$ as input and outputs 'yes' if $p$ is prime and 'no' otherwise. This program can be executed on a computer.

Computer

• A computer is a universal machine capable of implementing any algorithm, given sufficient memory and time. It follows instructions to manipulate data and perform computations.

• Turing Machine

  • A theoretical model of computation introduced by Alan Turing, consisting of an infinitely extendable tape divided into sections.

  • Each section may contain a symbol, typically 1 or 0, representing data, or it may be blank.

  • A tape head reads and writes symbols on the tape, moving along the tape to access different sections.

Computational Complexity

• Computational complexity is the study of the resources required to solve a problem using an algorithm. These resources include time (number of steps) and space (memory).

• Consider an algorithm that solves a specific problem.

• Question: How much computing power, typically measured in terms of time and space, is required to execute this algorithm for a given input size?

• Let $N$ be an integer that characterizes the size of the input instance.

  • Example: $N$ could represent the number of bits needed to represent the input in computer memory. For instance, if the input is an integer, $N$ might be the number of bits in its binary representation.

• How does the number of steps in our algorithm depend on $N$? The precise definition of a 'step' is somewhat arbitrary, but the choice typically does not affect the scaling behavior of the algorithm. We are primarily interested in how the number of steps grows as $N$ increases.

Complexity Classes

• Naively categorize problems:

  • P: The set of problems for which an algorithm exists that can solve them in polynomial time, i.e., the resources (time) required grow polynomially with the size of the problem ($N$). Problems in P are generally considered 'solvable' or 'tractable'.

    • Not the whole story: An algorithm that scales as $N^{100}$ is technically in P, but it is not practical for even moderately sized inputs.

    • Both DFT (Discrete Fourier Transform) and FFT (Fast Fourier Transform) are in P, but FFT requires significantly fewer resources in practice, especially for large inputs.

  • NP: The set of problems for which a 'guessed' solution can be verified in polynomial time. In other words, if someone gives you a potential solution, you can quickly check if it is correct.

    • Some problems in NP are used in cryptography for tasks such as data encryption and secure communication. The security of these methods relies on the presumed difficulty of solving certain NP problems.

  • $P = NP$ ? This is one of the most famous unsolved problems in computer science. If P = NP, it would mean that every problem whose solution can be quickly verified can also be quickly solved, which would have profound implications for cryptography and optimization.

Factoring

• Factoring: Given a composite number, find its prime factors. This is a fundamental problem in number theory and computer science.

• Considered a 'hard' problem in general, particularly when the number is the product of two large prime numbers. The difficulty of factoring large numbers is the basis for many cryptographic systems.

• The best-known classical factoring algorithm requires resources that grow exponentially with the size of the number (e.g., the General Number Field Sieve). The factorization of RSA-129, a 129-digit number, took 17 years using distributed computing.

• Example: Factor a 300-digit number

  • Best classical algorithm: Requires approximately $10^{24}$ steps.

  • On a computer operating at THz (terahertz) speed: Would take approximately 150,000 years.

• The difficulty of factoring is the foundation of the RSA encryption scheme, which is widely used for secure communication on the internet.

• Information security is of critical interest to both private and public sectors, as it protects sensitive data from unauthorized access.

• RSA-129 Example: Factoring $114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541$ = $349052951084765094914784961990389833417764638493387843990820577$ x $32769132993266709549961988190834461413177642967992942539798288533$

Quantum Algorithms

• Quantum algorithms are algorithms designed to run on a quantum computer. They leverage quantum mechanical phenomena such as superposition and entanglement to solve problems more efficiently than classical algorithms.

• Feynman (1982), Deutsch (1985): Pioneering work that suggested quantum systems could perform computations that classical computers struggle with.

• The concept of a quantum computer emerged as a universal device to execute quantum algorithms, capable of manipulating qubits to perform complex calculations.

• There may be quantum systems that cannot be simulated efficiently on a 'classical' computer, implying that quantum computers could solve problems that are intractable for classical computers.

• Proposed that machines using quantum processes might be able to perform computations that “classical” computers can only perform very poorly

Factoring with Quantum Systems

• Shor (1995): Quantum factoring algorithm

  • Shor's algorithm is a quantum algorithm for integer factorization, which can factor integers exponentially faster than the best-known classical algorithms.

  • To implement Shor’s algorithm, one could:

    • Run it as a program on a “universal quantum computer”.

    • Design a custom quantum chip with a hard-wired algorithm tailored specifically for factoring.

    • Find a quantum system that naturally performs factorization! (?)

  • Factor a 300-digit number:

    • Best classical algorithm: Requires approximately $10^{24}$ steps.

    • Shor’s quantum algorithm: Requires approximately $10^{10}$ steps.

    • On classical THz computer: Would take approximately 150,000 years.

    • On quantum THz computer: Could be completed in less than 1 second.

Implications

• Information security and e-commerce rely on the use of NP problems that are not in P. The security of these systems depends on the computational hardness of these problems.

  • The problems must be 'hard' (not in P) to ensure that the security is unbreakable. If an efficient algorithm were found for these problems, it would compromise the security of these systems.

  • Requires knowledge/assumptions about the algorithmic and computational power of your adversaries. It is crucial to understand the capabilities of potential attackers to design robust security measures.

• Quantum algorithms (e.g., Shor’s factoring algorithm) require us to reassess the security of such systems. The advent of quantum computers threatens the security of classical cryptographic systems.

• Lessons to be learned:

  • Algorithms and complexity classes can change! The landscape of computational complexity is not static, and new algorithms can shift the boundaries of what is considered 'hard' or 'easy'.

  • Information security is based on assumptions of what is hard and what is possible. It is essential to continually evaluate the validity of these assumptions in light of new algorithmic developments.

How Do Quantum Algorithms Work?

• What makes a quantum algorithm potentially faster than any classical one?

  • Quantum parallelism: By exploiting the principle of superposition, a quantum computer can explore multiple possibilities simultaneously, effectively executing an algorithm on all possible inputs at once.

  • Dimension of quantum Hilbert space: The state space for a quantum system grows exponentially with the number of qubits, allowing quantum computers to represent and manipulate vastly more complex states than classical computers.

  • Entanglement capability: Quantum entanglement allows qubits to be correlated in ways that are impossible in classical systems, enabling the creation of complex quantum states and algorithms.

• We don’t really know what makes quantum systems more powerful than a classical computer. Understanding the source of quantum computational advantage is an active area of research.

• Quantum algorithms are helping us understand the computational power of quantum vs classical systems.

Typical Quantum Algorithm Workflow:

• Problem definition (e.g., Traveling Salesman Problem)

• Quantum Algorithm: Design a quantum algorithm tailored to the problem.

• Quantum circuit: Represent the quantum algorithm as a sequence of quantum gates.

• Quantum compiler: Translate the high-level quantum circuit into a form suitable for execution on a specific quantum processor.

• Quantum processor: Execute the quantum algorithm on a physical quantum computer.

• Quantum simulator: Simulate the behavior of the quantum algorithm on a classical computer to verify its correctness.

• Full-stack: Integrate all components of the quantum computing system to solve real-world problems.

Quantum Algorithms

• Algorithms based on QFT (Quantum Fourier Transform)

• Algorithms based on QAA (Quantum Amplitude Amplification)

• Algorithms based on Quantum Simulation

• Adiabatic Algorithms

• Algorithms based on Quantum Walk

Quantum Fourier Transform

• Fourier transform decomposes a function of time into the frequencies that make it up

• QFT means by using a simple decomposition the discrete Fourier transform on amplitudes can be implemented as a quantum circuit consisting of only Hadamard gates and controlled phase shift gates. This quantum algorithm is a cornerstone in many other quantum algorithms.

• Shor introduced QFT for integer factorisation to make the factorisation process computationally feasible in deterministic time. It plays a critical role in the speedup achieved by Shor's algorithm.

Quantum Amplitude Amplification

• Amplification of amplitude using probabilistic technique

• Primarily used in Grover search algorithm to find out a data item from unsorted database in polynomial time within $O(<br>\sqrt{N})$ iterations. Grover's algorithm provides a quadratic speedup compared to classical search algorithms for unsorted databases.

• Hadamard transform is applied on all qubits, followed by performing ORACLE diffusion operator iteratively. The Oracle identifies the target item, and the diffusion operator amplifies the probability of measuring the target item.

• $N - \sqrt{N}$ (Quadratic), representing the reduction in the number of iterations needed compared to classical search.

Quantum Simulation Algorithms

• Simulate a given Hamiltonian by breaking it down into a sum of simpler ones. This is crucial for simulating quantum systems in various fields, including chemistry and materials science.

• Quantum simulator would efficiently generate qubit string states that closely approximates physical states obtained from a broad class of dynamic evolutions.

• Implementation: To calculate molecular, ground state energy on an NMR(Nuclear Magnetic Resonance) for simulating a Hydrogen molecule. This demonstrates the application of quantum simulation in computational chemistry.

• NMR interferometry (Interference of waves, mainly light waves) is used to measure phase shift and iterate the process to get a high precision. This technique allows for precise measurements of quantum properties.

Quantum Adiabatic Algorithms

• It relies on the adiabatic theorems to do calculations. Adiabatic quantum computation is a paradigm for quantum computation that differs significantly from gate-based quantum computation.

• Main idea is to encode the solution to a hard problem into a ground state of a Hamiltonian to make it easier to simulate. The algorithm slowly evolves the system from a simple initial Hamiltonian to a final Hamiltonian whose ground state encodes the solution to the problem.

• Application: To solve computationally infeasible satisfiability problems and give it an optimization. This approach is particularly useful for solving complex optimization problems.

Random Walk

• A random walk is the simulation of the random movement of a particle around a graph

• Time dependency of random walk

  • Discrete-time random walk: The particle moves at discrete time intervals.

  • Continuous-time random walk: The particle moves continuously in time.

• Quantum walk – Quantum analogue of classical random walk

  • Discrete-time quantum random walk

  • Continuous-time quantum random walk

Physical Intuition Behind A Classical Random Walk

• Illustrates the probability at different vertices (1, 2, 3, 4) over time (0 to 6). This visualization helps understand how the probability distribution evolves over time.

Discrete-Time Quantum Walk

• Drunkard’s Walk: A simple example of a random walk, where a person randomly moves left or right.

  • At each discrete-time interval, the quantum walker is affected by:

    • Unitary coin operator (H): Determines the direction the walker will move.

    • Conditional Shift operator: Moves the walker to the next position based on the coin value.

Discrete-Time Quantum Walk on a Line

• Walker is replaced by a quantum particle carrying a 2-state quantum system for the coin. This quantum particle can exist in a superposition of states.

• Coin toss is effected by unitary operator: Determines the direction the quantum particle will move, analogous to flipping a coin.

• Basis state of a quantum walk is an ordered pair \x, C\rangle:

  • $x$ = position: The location of the quantum particle on the line.

  • $C \in {0,1}$ = state of the coin: Determines the direction of movement.

• Simplest coin operator is Hadamard

  • H\x, 0\rangle = \frac{1}{\sqrt{2}}(\x, 0\rangle + \x, 1\rangle): Applies the Hadamard gate to the coin state 0.

  • H\x, 1\rangle = \frac{1}{\sqrt{2}}(\x, 0\rangle - \x, 1\rangle): Applies the Hadamard gate to the coin state 1.

• Shift operation S acts on the basis state as

  • S\x, 0\rangle = \x - 1, 0\rangle: Shifts the particle to the left if the coin state is 0.

  • S\x, 1\rangle = \x + 1, 1\rangle: Shifts the particle to the right if the coin state is 1.

Mathematical Calculation of First 3 Steps Involved In Discrete Quantum Walk

• (SH)\0,0\rangle: The first step in the quantum walk.

• (SH)^2 \0,0\rangle: The second step in the quantum walk.

• (SH)^3 \0,0\rangle: The third step in the quantum walk.

Diagrammatic Representation

• Visual representation of the walk with Hadamard transforms (HT) applied at each step. This diagram provides an intuitive understanding of the quantum walk.

Triangle Finding Problem

• Problem:

  • Decision-making problem to decide whether a graph contains a cycle or not. The goal is to determine if there are any triangles in the graph.

  • Undirected simple graph G with and edge-set {E} is driven by an ORACLE function f such that for any 2 nodes v and w:

  • $f(v, w) = 1$ if $(v, w) \in {E}$, otherwise $f(v, w) = 0$: The Oracle function determines if an edge exists between two nodes.

• Classical triangle finding problem has complexity of $O(n^α)$. The exact value of α depends on the specific classical algorithm used.

• The existing classical algorithm is well-suited for sparse graphs but not for dense graphs. Quantum algorithms offer potential speedups for dense graphs.

Different Approaches

• Two new quantum algorithms are theoretically used for finding triangles in a graph.

  • The first algorithm uses combinatorial ideas with Grover search and makes $O(n^{10/7})$ quantum queries. This algorithm combines combinatorial techniques with Grover's search for an efficient quantum solution.

  • The second algorithm uses $O(n^{13/10})$ queries by incorporating the benefits of quantum walk into Grover search. This algorithm leverages the advantages of both quantum walks and Grover's search.

• Combinatorial approach uses only $O(log(n))$ qubits in its quantum subroutine, but the second one uses $O(n)$ qubits. There is a trade-off between the number of qubits required and the query complexity.

Continuous-Time Quantum Walk

• Fixed transition probability or hopping rate to move from one vertex to another. The particle moves continuously in time, with a fixed probability of transitioning between vertices.

• If H be Hamiltonian, dynamics of a system can be
  

$\frac{d(\varphi(t))}{dt} = \sum<em>{a'}{K</em>{aa'}\varphi<em>{a'}(t)}$ where K{aa'} = \begin{cases}

(\alpha|H|\alpha') & \text{if } a \neq a', aa' \in G \

-\delta(a) & \text{if } a = a' \

0 & \text{otherwise}

\end{cases}

• Considering overall time evolution on the system $\frac{dp<em>a(t)}{dt} = \sum</em>{a'}{K<em>{aa'}P</em>{a'}(t)}$ where

  • $\varphi(t)$: determining factor

  • $a$ = present state,

  • $a'$ adjacent vertices to a

• No coin operation. Continuous-time quantum walks do not use a coin operator.

Random Welding on the BWT

• Two Quantum operators, ORACLE & TIMESTEP:

  • 1st tree

  • 2nd tree

Binary Welded Tree Algorithm

• Input to the system: The initial conditions and parameters required to run the algorithm.

  • ORACLE operator and ENTRANCE node: The starting point for the algorithm.

• Objective: The desired outcome of the algorithm.

  • To determine the name of the EXIT node or GOAL: The algorithm aims to find the exit node in the welded tree.

• Example: Welding specified previously to the system, ${(1,2), (3,7), (4,8), (5,11), (6,9), (10,13), (12,14)}$

Disadvantage of Existing Algorithm:

• Nature of welding state: STATIC. The welding configuration does not change during the algorithm.

• Case-specific approach - not generalized. The algorithm is tailored to a specific type of welded tree.

• Approach towards the problem: The approach used to solve the problem.

  • Introduction of multi-controlled Toffoli gates instead of C* NOT gates: Using multi-controlled Toffoli gates for graph traversal.

• Input to the system: The parameters and data required to run the algorithm.

  • Number of qubits: The number of qubits required to represent the graph.

  • Welding or pairs of all the adjacent vertices: The connections between vertices in the graph.

• Output from the system: The result of running the algorithm.

  • Set of MCTs for granh traversal: The set of multi-controlled Toffoli gates used to traverse the graph.

Input Instance:

• Number of qubits

• Welding or pairs of all the adjacent vertices

• SYSTEM

Output Instance:

• Number of qubits

• Welding or pairs of all the adjacent vertices

• SYSTEM Generation of Multi- Controlled Tofolli Gates dynamically at runtime

Importance of Quantum Computing in Machine Learning

• Quantum recommendation systems: These systems use quantum algorithms to provide recommendations based on user preferences.

  • Netflix problem: Given a set of m users and n films, where the goal is to recommend a film to a user which they have not watched. This is a classic recommendation problem.

  • Users' preferences are represented by a matrix P of dimension m x n where the (i,j)-th entry means the i-th user's rating of the j-th film. The matrix P represents the user-item interaction data.

• Classical algorithm: $O(poly(mn))$. The runtime of classical recommendation algorithms is polynomial in the number of users and films.

• Quantum algorithm: $O(poly log(mn))$. Quantum algorithms can achieve an exponential speedup compared to classical algorithms.

• Thus, exponential speed up is achieved using quantum machine learning. Quantum machine learning has the potential to revolutionize various machine-learning tasks.

Classical Perceptron Model

• Given: N labelled linearly separable data points. The data points can be separated by a hyperplane.

• Output: To find a separating hyperplane. The goal is to find a hyperplane that correctly classifies all data points.

• Classical algorithm: $O(\frac{1}{\gamma^2})$ where, $\gamma$ is the margin or the shortest distance between a training point and a separating hyperplane. The runtime of the classical perceptron algorithm depends on the margin.

• Quantum algorithm: $O(\frac{1}{\gamma})$ ( exploiting Grover's search algorithm). Quantum algorithms can achieve a quadratic speedup compared to classical algorithms.

• Thus, quadratic speed up is achieved using quantum machine learning. Quantum machine learning can improve the performance of classical machine learning algorithms.

Model for supervised machine learning SVM (Support Vector Machine).

• Machine learning model used for data classification and regression. SVM is a powerful and versatile machine learning algorithm.

• For least square SVM:

• Classical algorithm: $O(\log^{\frac{1}{\epsilon}} poly(d,N))$- where, N = number of training examples; d = corresponding dimension;$\epsilon$ = accuracy. The runtime of the classical SVM algorithm depends on the number of training examples, the dimension, and the desired accuracy.

• Quantum algorithm: $O(\frac{1}{\epsilon} \log(d, N))$

• Thus, exponential speed up is achieved in Support Vector Machine. Quantum SVM algorithms can achieve exponential speedups compared to classical SVM algorithms

• For unsupervised learning also, quantum algorithms provide speed up over their classical counterparts.

• All the three cases mentioned above use HHL (Harrow Hassidim Lloyd) algorithm as a subroutine corresponding to quantum linear systems. The HHL algorithm is a key component of many quantum machine learning algorithms.

Introduction to HHL

• Solving a system of linear equations is computationally infeasible using a classical computer for large systems. Classical algorithms for solving linear systems require a large amount of computational resources.

• Quantum version corresponding to the classical counterpart: Quantum Linear System Algorithm (QLSA) Or Harrow-Hassidim-Lloyd (HHL) Algorithm. The HHL algorithm is a quantum algorithm for solving linear systems.

• Quantum states are taken as input and also produced as output. The HHL algorithm operates on quantum states rather than classical data.

• Exponential speed up over classical version: CG (Conjugate Gradient method). The HHL algorithm can achieve exponential speedups compared to classical algorithms for solving linear systems.

Subroutines Used In HHL:

• Quantum Fourier Transform

• Quantum Simulation

• Quantum Phase Estimation

• Quantum Phase Kickback

• Quantum Amplitude Amplification

• Uncomputation trick

Deutsch–Jozsa Algorithm

• quantum algorithm proposed by David Deutsch and Richard Jozsa in 1992 with improvements by Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca in 1998. This algorithm is one of the earliest examples of a quantum algorithm that outperforms classical algorithms.

• Although of little current practical use, it is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. The Deutsch-Jozsa algorithm demonstrates the potential of quantum computers to solve certain problems much faster than classical computers.

Problem Statement:

• We are given a black-box function f, which takes as input a string of bits (x), and returns either 0 or 1, that is:

• $ƒ({x<em>0,x</em>1, x_2, … }) → 0 or 1$ where x is 0 or 1

• The property of the given Boolean function is that it is guaranteed to either be balanced or constant.

• A constant function returns all 0 's or all 1's for any input, while a balanced function returns 0 's for exactly half of all inputs and 1's for the other half.

• Our task is to determine whether the given function is balanced or constant. The goal is to determine the property of the function with minimal queries.

• the Deutsch-Jozsa problem is an n – bit extension of the single bit Deutsch problem.

The Classical Solution:

• Classically, in the best case, two queries to the oracle can determine if the hidden Boolean function, f(x), is balanced: e.g. if we get both $f(0,0,0, …) → 0$ and $ƒ (1,0,0, …) → 0$, then we know the function is balanced as we have obtained the two different outputs.

• In the worst case, if we continue to see the same output for each input we try, we will have to check exactly half of all possible inputs plus one in order to be certain that f(x) is constant. Since the total number of possible inputs is $2^n$, this implies that we need $2^{n-1} + 1$ trial inputs to be certain that f(x) is constant in the worst case.

• For example, for a 4 - bit string, if we checked 8 out of the 16 possible combinations, getting all O's, it is still possible that the 9th input returns a 1 and f(x) is balanced.

• Probabilistically, this is a very unlikely event. In fact, if we get the same result continually in succession, we can express the probability that the function is constant as a function of k inputs as:

• $P_{\text{constant}}(k) = 1 - \frac{1}{2^{k-1}}$, for 1<k≤2^{n-1}

• Realistically, we could opt to truncate our classical algorithm early, say if we were over x% confident. But if we want to be 100% confident, we would need to check $2^{n-1} + 1$ inputs.

The Quantum Solution:

• Using a quantum computer, we can solve this problem with 100% confidence after only one call to the function f(x), provided we have the function f implemented as a quantum oracle, which maps the state \x\rangle\y\rangle to \x\rangle\y ⊕ f(x)\rangle, where $\oplus$ is addition modulo 2. This demonstrates the power of quantum computers to solve certain problems with absolute certainty and with minimal queries

• The steps of the algorithm are as follows:

  1. Prepare two quantum registers. The first is an n-qubit register initialized to \0\rangle, and the second is a one-qubit register initialized to \1\rangle. These registers will be used to perform the quantum computation.

  2. Apply a Hadamard gate to each qubit. The Hadamard gate creates a superposition of states, which is a key element of quantum algorithms

  3. Apply the quantum oracle \x\rangle\y\rangle to \x\rangle\y ⊕ f(x)\rangle. The oracle evaluates the function f(x) in superposition

  4. Apply a Hadamard gate to each qubit in the first register. This step is crucial for extracting the global property of the function

  5. Measure the first register. The measurement reveals whether the function is balanced or constant.

Circuit Implementation

• Generic circuit for the Deutsch-Jozsa algorithm illustrated with stages:

  • Input states: The initial quantum states of the qubits.

  • Hadamard gates applied: Creates superposition

  • Oracle (Uf) application: Implementation of the function as a quantum oracle.

  • Hadamard gates applied again: Transforms the state for measurement

  • Measurement: Extracts the result

Example:

• Specific example for a two bit balanced function:

  1. The first register of two qubits is initialized to \00\rangle and the second register qubit to \1\rangle

  2. Apply a Hadamard gate to all qubits:

     • \psi1\rangle = \00\rangle{12} \otimes \1\rangle_3: Initialization of the quantum state.

     • \psi2\rangle = \frac{1}{2} (\00\rangle +\01\rangle +\10\rangle +\11\rangle){12} \otimes \frac{1}{\sqrt{2}} (\0\rangle - \1\rangle)_3: Applying Hadamard gates to create superposition.

  3. The oracle function can be implemented as $Q<em>f = CX</em>{13}CX_{23}$: The oracle function is implemented using controlled-NOT gates.

• Subsequent mathematical operations and simplifications are detailed.

…Continued:

• Continues the mathematical simplification from the previous step, eventually leading to:

• \psi3\rangle = \1\rangle1\otimes\1\rangle2\otimes(\frac{\0\rangle - \1\rangle}{\sqrt{2}})3

• Measuring the first two qubits will give the non-zero 11, indicating a balanced function.

Quantum Advantage:

• Number of queries required (quantum) < (No. of queries) Classical counterpart: Quantum algorithms can solve certain problems with significantly fewer queries than classical algorithms

• Linear combination of states (unlike classical, we can store all at a time). Quantum superposition allows for the storage of multiple states simultaneously

• Quantum Parallelism: Computation of a function in exactly 1 quantum register where # for states in the quantum register

Measurement (to extract) the required result

• Diagram showing Input register and target register and how measurement extracts desired results. Measurement is essential for obtaining the result of the quantum computation.

• Deutsch Algorithm:

  • Input: 1 qubit (0 or 1)

  • Function is either constant or balanced

  • Classical :- 2 queries

Under Calculation

• Step by step diagrammatic and mathematical representation of Deutsch Algorithm using Hadamard gate and Oracle operations. Provides a detailed breakdown of the algorithm's execution.

#

• Expanding the i/p in 2-qubit form.

Now,

• Mathematical proof of the constant or balanced function

.: The 1st register after ORACLE