Introduction To Quantum Computing Day 2 - Quantum Algorithms
Introduction to Quantum ComputingDay 2 - Quantum AlgorithmsMengoni Riccardo, PhD22 June 2021
Quantum Computing @ CINECACINECA: Italian HPC centerCINECA Quantum Computing Lab:- Research with Universities, Industries and QC startups- Internship programs, Courses and Conference mengoni@cineca.it
Recap of Quantum Computing
Linear Algebra RecapVectorsKet:Complex NumberBra:ComplexConjugate
Linear Algebra RecapScalar ProductComplex Number
Linear Algebra RecapScalar ProductComplex NumberThe scalar product induces a norm
Linear Algebra RecapOuter ProductDimension n x n
Linear Algebra RecapTensor ProductDimension 𝑛2
Linear Algebra RecapTensor ProductCompact form:Dimension 𝑛2
Postulates of Quantum Computing (1)1. Unit of Information
Postulates of Quantum Computing (1)ClassicallyUnit of classical information is the bitState of a bit:
Postulates of Quantum Computing (1)QuantumlyTo a closed quantum system is associated a space of states H which is aHilbert space. The pure state of the system is then represented by aunit norm vector on such Hilbert space.The unit of quantum information is the quantum bit a.k.a. QubitState of a qubit:
Postulates of Quantum Computing (1)Space of states:State of a qubit:
Postulates of Quantum Computing (1)Space of states:bitState of a qubit:qubitCan be parametrized as:bit
Postulates of Quantum Computing (2)2. Composite systems
Postulates of Quantum Computing (2)ClassicallyState of N bits:
Postulates of Quantum Computing (2)QuantumlyThe space of states of a composite system is the tensorproduct of the spaces of the subsystemsState of N qubits:
Postulates of Quantum Computing (2)Quantum EntanglementStates that can be written as tensor productare called factorable or product states
Postulates of Quantum Computing (2)Quantum EntanglementStates that can NOT be written as tensor productare called entangled states
Postulates of Quantum Computing (2)Quantum EntangledBell’s states
Postulates of Quantum Computing (3)3. State Change
Postulates of Quantum Computing (3)Classically: logic gates
Postulates of Quantum Computing (3)QuantumlyThe state change of a closed quantum system isdescribed by a unitary operatorSchrodinger Equation
Postulates of Quantum Computing (3)Quantumly: Quantum Gates
Postulates of Quantum Computing (4)4. Measurement
Postulates of Quantum Computing (4)ClassicallyMeasuring returns the state of a bit with certainty 0ۧMeasureOutcome 1ۧMeasureOutcome 1ۧMeasurements do not affect the state of a bit
Postulates of Quantum Computing (4)QuantumlyMeasuring returns the bit state with some probabilityOutcomeMeasure 0ۧwithPr 𝛼2 1ۧwithPr 𝛽2Measurement affects the state of a qubit
Postulates of Quantum Computing (4)Quantumly To any observable physical quantity is associated an hermitian operator O A measurement outcomes are the possibile eigenvalues 𝑜𝑖 .The probability of obtaining 𝑜𝑖 as a result of the measurement isThe effect of the measure is to change the state 𝜓ۧ into the eigenvector of O
Quantum Algorithms
Quantum AlgorithmsQuantum Algorithm Quantum CircuitA quantum circuit with n input qubits and n output qubits isdefined by a unitary transformation
Quantum Algorithms
Quantum Algorithms: Gates
Quantum Algorithms: GatesSingle Qubit GatesGeneric singlequbit rotation:Pauli matrices:Identity:
Quantum Algorithms: GatesSingle Qubit Gates: Hadamard
Quantum Algorithms: GatesSingle Qubit Gates: Phase
Quantum Algorithms: GatesTwo Qubit Gates: SWAP
Quantum Algorithms: GatesTwo Qubit Gates: Control Not
Quantum Algorithms: GatesTwo Qubit Gates: Control UnitaryControl Phase
Quantum Algorithms: GatesThree Qubit Gates: Toffoli
Quantum Algorithms: Universality
Quantum Algorithms: UniversalityUniversal set of Quantum GatesWe can exactly build any unitaryon n qubitsby means of single qubit gates and Control-Not
Quantum Algorithms: UniversalityUniversal set of Quantum GatesWe can exactly build any unitaryon n qubitsby means of single qubit gates and Control-Not
Quantum Algorithms: UniversalityUniversal set of Quantum GatesGiven,approximatesifwithin
Quantum Algorithms: UniversalityUniversal set of Quantum GatesGiven,approximatesifwhereandwithin
Quantum Algorithms: UniversalityUniversal set of Quantum GatesWe can approximate any unitaryby means of the following gateson n qubits
Quantum Algorithms: basics
Quantum Algorithms: basicsMultiple Hadamard gates
Quantum Algorithms: basicsSingle Qubit Gates: Hadamard
Quantum Algorithms: basicsMultiple Hadamard gates
Quantum Algorithms: basicsMultiple Hadamard gates
Quantum Algorithms: basicsMultiple Hadamard gatesKronecker delta
Quantum Algorithms: basicsMultiple Hadamard gatesKronecker delta
Quantum Algorithms: basicsFunction evaluationGiven a function, an algorithm to evaluatesuch function is given by the unitarywhere
Deutsch Jozsa Algorithm
Deutsch Jozsa AlgorithmD-J ProblemConsider a functionwith the premise thatit is either constant (returns 0 on all inputs or 1 on allinputs) or balanced (returns 1 for half of the inputs and 0 forthe other half).constantbalanced
Deutsch Jozsa AlgorithmHow many evaluations («queries») of the function are neededto determine with certainty if such function is balanced orconstant?
Deutsch Jozsa AlgorithmHow many evaluations («queries») of the function are neededto determine with certainty if such function is balanced orconstant?ClassicallySince the possible input strings are 2𝑁 , we need to check onaverage (half 1) strings, i.e. 2𝑁 1 1 stringsClassical Query Complexity
Deutsch Jozsa AlgorithmQuantum Solutionand
Deutsch Jozsa AlgorithmStep by step analysis
Deutsch Jozsa AlgorithmStep by step analysis
Deutsch Jozsa AlgorithmStep by step analysis
Deutsch Jozsa AlgorithmStep by step analysis
Deutsch Jozsa AlgorithmStep by step analysis
Deutsch Jozsa AlgorithmStep by step analysis
Deutsch Jozsa AlgorithmStep by step analysis
Deutsch Jozsa AlgorithmStep by step analysis
Deutsch Jozsa AlgorithmStep by step analysis
Deutsch Jozsa AlgorithmStep by step analysis
Deutsch Jozsa AlgorithmStep by step analysis
Deutsch Jozsa AlgorithmStep by step analysis
Deutsch Jozsa AlgorithmStep by step analysis𝛿𝑧𝑥
Deutsch Jozsa AlgorithmStep by step analysis𝛿𝑧𝑥
Deutsch Jozsa AlgorithmStep by step analysis𝛿𝑧𝑥
Deutsch Jozsa AlgorithmStep by step analysis
Deutsch Jozsa AlgorithmStep by step analysisOutcomewith
Deutsch Jozsa AlgorithmStep by step analysisOutcomeconstant(returns 0 on all inputsor 1 on all inputs)with
Deutsch Jozsa AlgorithmStep by step analysisOutcomeconstant(returns 0 on all inputsor 1 on all inputs)with
Deutsch Jozsa AlgorithmStep by step analysisOutcomebalanced(returns 1 for half of the inputsand 0 for the other half)with
Deutsch Jozsa AlgorithmStep by step analysisOutcomebalanced(returns 1 for half of the inputsand 0 for the other half)with
Deutsch Jozsa AlgorithmHow many evaluations («queries») of the function are needed todetermine with certainty if the function is balanced or constant?
Deutsch Jozsa AlgorithmHow many evaluations («queries») of the function are needed todetermine with certainty if the function is balanced or constant?Quantum Query Complexity 1Classical Query Complexity
Bernstein Vazirani Algorithm
Bernstein Vazirani AlgorithmB-V ProblemConsider a functionsuch thatThe task is to find the string w
Bernstein Vazirani AlgorithmClassical Solution Classically weneed N evaluationsof the function torecover w
Bernstein Vazirani AlgorithmQuantum Solutionand(same circuit)
Bernstein Vazirani AlgorithmStep by step analysis
Bernstein Vazirani AlgorithmStep by step analysis
Bernstein Vazirani AlgorithmStep by step analysis
Bernstein Vazirani AlgorithmStep by step analysis
Bernstein Vazirani AlgorithmStep by step analysis
Bernstein Vazirani AlgorithmStep by step analysis
Bernstein Vazirani AlgorithmStep by step analysis
Bernstein Vazirani AlgorithmStep by step analysis
Bernstein Vazirani AlgorithmStep by step analysisOutcomewith probability
Bernstein Vazirani AlgorithmStep by step analysisOutcomewith probabilityQuantumly we need 1 evaluation of the function to recover w(classically it was N)
Simon Algorithm
Simon AlgorithmSimon ProblemConsider a functionsuch thatThe task is to find the string p
Simon AlgorithmSimon Problem𝑝 ?
Simon AlgorithmSimon Problem𝑝 110
Simon AlgorithmClassical SolutionConsider M stringswithand check if, if soThe total number of checks using M strings is
Simon AlgorithmClassical SolutionThe probability of finding p using M strings is henceIf we want at leastthis means thatM scalesexponentially
Simon AlgorithmQuantum Solutionand(not the same circuit)
Simon AlgorithmStep by step analysis
Simon AlgorithmStep by step analysis
Simon AlgorithmStep by step analysis
Simon AlgorithmStep by step analysis
Simon AlgorithmStep by step analysisand measure the second registerSuppose we measure, the state after the measurement is
Simon AlgorithmStep by step analysis
Simon AlgorithmStep by step analysis
Simon AlgorithmStep by step analysis
Simon AlgorithmStep by step analysisOutcome string y with probability
Simon AlgorithmStep by step analysis
Simon AlgorithmStep by step analysisIfwe get
Simon AlgorithmStep by step analysisIfwe getWe always find a string s.t.
Simon AlgorithmStep by step analysisIfTo recover pwe need tosolve thislinear systemwe getWe always find a string s.t.
Simon AlgorithmStep by step analysisThe probability of havingindependent is:linearlywith
Simon AlgorithmStep by step analysisThe probability of havingindependent is:linearlywithIn order to be sure to find a L.i. set, we have to repeat thealgorithm a number of times equal to
Simon AlgorithmStep by step analysisThe probability of havingindependent is:linearlywithIn order to be sure to find a L.i. set, we have to repeat thealgorithm a number of times equal toComplexity of the SimonAlgorithm scales like 𝟐𝐍(classically it was 𝟐𝑵/𝟐)
Quantum Fourier Transform
Quantum Fourier TransformDiscrete Fourier TransformGiven a functionwhere, the DFT is defined as
Quantum Fourier TransformQuantum Fourier TransformGiven a basis statewhere, the QFT is defined as
Quantum Fourier TransformQuantum Fourier TransformGiven a state, the QFT is defined aswhere
Quantum Fourier TransformQuantum Fourier TransformSupposei.e. the dimension of the space isThe QFT in this case becomesIs it possible to realize such transformationefficiently on a Quantum Computer?
Quantum Fourier TransformQFT CircuitIt is possible to rewrite the previus equation as follows
Quantum Fourier TransformQFT CircuitIt is possible to rewrite the previus equation as follows
Quantum Fourier TransformQFT Circuit ProofRecall that we can write in binary form as follows,
Quantum Fourier TransformQFT CircuitComplexity:
Quantum Phase Estimation
Quantum Phase EstimationQPE problemGiven a Unitaryand a quantum stateThe task is to estimatesuch that
Quantum Phase EstimationQPE circuit
Quantum Phase EstimationQPE circuit analysis
Quantum Phase EstimationQPE circuit analysis
Quantum Phase EstimationQPE circuit analysis
Quantum Phase EstimationQPE circuit analysis
Quantum Phase EstimationQPE circuit analysisThe probability of measuring j
Quantum Phase EstimationQPE circuit analysisThe probability of measuring jIfthe probability becomesState after measurement:
Shor Algorithm
Shor AlgorithmFacorization ProblemGiven, find the two prime numbers such that
Shor AlgorithmFacorization ProblemGiven, find the two prime numbers such thatClassically: Findingsolution requiresexponential timeUsed in theRSA cryptosystemRSA
Shor AlgorithmModified version of QPE to solvefactorization in polynomial time
Shor AlgorithmExponentialspeedupTime to factor a2048-digits number billions of years* seconds** Assuming we have a fault-tolerant quantum computer capable of executing Shor’s algorithm byapplying gates at the speed of current quantum computers based on superconducting circuits
Grover Search
Grover SearchSearching ProblemWe have access to an unstructured database of 𝟐𝑵elements, the task is to find theelementAssume to have a functionsuch that
Grover SearchSearching ProblemWe have access to an unstructured database of 𝟐𝑵elements, the task is to find theelementAssume to have a functionsuch thatClassically, in order to find thesearched element, we have toevaluate this function on 2𝑁 1inputs (on average)
Grover SearchGrover AlgorithmObtained viathe unitary
Grover SearchGrover AlgorithmRepeat times
Grover SearchGrover AlgorithmRepeat times
Grover SearchGrover AlgorithmRepeat times
Grover SearchGrover Algorithm:geometrical analysisRepeat times
Grover SearchGrover Algorithm:geometrical analysisRepeat timesEqual superpositionof all possibleelements
Grover SearchGrover Algorithm:geometrical analysisRepeat timesAmplitude of thesearched elementbecomes negative
Grover SearchGrover Algorithm:geometrical analysisRepeat timesAmplitudeamplification ofsearched element
Grover SearchGrover AlgorithmRepeat times𝝅 𝟐𝑵Optimally𝟒Quadratic speedup wrt the classical case, wherewe have to evaluate this function 2𝑁 1 times
Quantum Computing @ CINECACINECA: Italian HPC centerCINECA Quantum Computing Lab:- Research with Universities, Industries and QC startups- Internship programs, Courses and Conference mengoni@cineca.it
Postulates of Quantum Computing (1) To a closed quantum system is associated a space of states H which is a Hilbert space. The pure state of the system is then represented by a unit norm vector on such Hilbert space. The unit of quantum information is the quantum bit a.k.a. Qubit State of a qubit: Quantumly
1. Quantum bits In quantum computing, a qubit or quantum bit is the basic unit of quantum information—the quantum version of the classical binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, one of the simplest quantum systems displaying the peculiarity of quantum mechanics.
Quantum computing with photons: introduction to the circuit model, the one-way quantum computer, and the fundamental principles of photonic experiments . quantum computing are presented and the quantum circuit model as well as measurement-based models of quantum computing are introduced. Furthermore, it is shown how these concepts can
Quantum computing is a subfield of quantum information science— including quantum networking, quantum sensing, and quantum simulation—which harnesses the ability to generate and use quantum bits, or qubits. Quantum computers have the potential to solve certain problems much more quickly t
Topics History of Computing What are classical computers made of? Moore's Law (Is it ending?) High Performance computing Quantum Computing Quantum Computers Quantum Advantage The Qubit (Information in superposition) Information storage Different kinds of quantum computers Superconducting vs Ion Traps Annealing vs Universal/Gate quantum computers
Keywords—machine learning, quantum computing, deep learning, quantum machine intelligence I. INTRODUCTION There is currently considerable interest in quantum computing. In the U.S. in January 2019, the National Quantum Initiative Act authorized 1.2 billion investment over the next 5-10 years (Rep Smith, 2019). A quantum computing race is ongoing
According to the quantum model, an electron can be given a name with the use of quantum numbers. Four types of quantum numbers are used in this; Principle quantum number, n Angular momentum quantum number, I Magnetic quantum number, m l Spin quantum number, m s The principle quantum
Quantum effects - superposition, interference, and entanglement NISQ - Noisy Intermediate-Scale Quantum technology, often refers in the context of modern very noisy quantum computers QASM - Quantum Assembly used for programming quantum computers Quantum supremacy - demonstration of that a programmable quantum
the quantum operations which form basic building blocks of quantum circuits are known as quantum gates. Quantum algorithms typically describe a quantum circuit de ning the evolution of multiple qubits using basic quantum gates. Compiler Implications: This theoretical background guides the design of an e ective quantum compiler. Some of
