Learn about computational costs in both classical and quantum computing in this comprehensive video lesson that explores how classical computations can be executed through quantum circuits. Dive into key concepts including integer factorization, greatest common divisor, measuring computational costs, and circuit size and depth. Master the fundamentals of asymptotic notation, understand the differences between polynomial and exponential costs, and explore classical computations on quantum computers through topics like Toffoli gates and Boolean circuit simulation. Access additional learning materials including written content, Qiskit implementations, and PDF slides through IBM Quantum Learning platform to enhance your understanding of quantum algorithmic foundations.
Quantum Algorithmic Foundations: Understanding Quantum Information and Computation - Lesson 6
Overview
Syllabus
— Introduction
— Overview
— Integer factorization
— Greatest common divisor
— Measuring computational cost
— An abstract view of computation
— Encodings and input length
— Elementary operations
— Circuit size and depth
— Cost as a function of input length
— Example: integer addition
— Asymptotic notation
— Polynomial versus exponential cost
— Classical computations on quantum computers
— Toffoli gates
— Simulating Boolean gates
— Simulating Boolean circuits
— Conclusion
Taught by
Qiskit
