Learning Outcomes
On successful completion  of the course students should be able
  -  
 To understand basic concepts of computability and computational complexity.
  
-  
 To master the quantum computational model.
 
- 
  To  design, analyse and implement quantum algorithms.
Syllabus
-   Computability and  complexity 
  -  Problems and algorithms. 
  
-  Turing machines and computability. 
  
-  Computational complexity.
 
-   Quantum computation and algorithms
  -  The quantum computational model.
  
-  Introduction to quantum algorithms.
  
-  Algorithms based on phase amplification.
  
-  Algorithms based on the quantum Fourier transform.
  
-  Case studies in quantum algorithmics.
 
Summaries (2025-26)
     T Lectures
  
        
          | Sep 15 (17:00 - 19:00) | Introduction to Quantum Computation and the course dynamics
            (slides).  Revisiting computability and computational complexity
            (notes). | 
        
          | Sep 22 (16:00 - 18:00) | Computability and decidability. Turing machines. The Church-Turing thesis and its physical counterpart
            (notes). | 
        
          | Sep 29 (16:00 - 18:00) | Introduction to quantum algorithms. The Deutsch algorithm
            (slides). | 
        
          | Oct 6 (16:00 - 18:00) | The phase kick-back technique. Analysis of two algorithms: Deutsh-Joza and Bernstein-Vazirani 
            (slides). | 
        
          | Oct 13 (16:00 - 18:00) | Quantum approach to unstructured search problems. The Grover's algorithm
            (slides). | 
        
          | Oct 20 (16:00 - 18:00) | Quantum fundamentals with pennylane: Superposition, interference, entanglement and universal gate sets.  
            (notebook from class). | 
        
          | Oct 27 (16:00 - 18:00) | Simon’s algorithm and its generalisations
          (slides).
          Complementary notes on group theory (notes) | 
          
    
   
     TP Lectures 
    
        
          | Sep 17 (09:00 - 11:00) | Diagnostic exercise. | 
        
          | Sep 24 (09:00 - 11:00) | Superposition and quantum interference
            (slides).  Revisiting computational complexity 
            (notes). | 
        
          | Oct 1 (09:00 - 11:00) | Exercises (on background notions): Hilbert spaces and quantum gates
            (exercises 1). | 
        
          | Oct 8 (09:00 - 11:00) | Exercises (on quantum gates, and phase kick-back algorithms)
            (exercises 2). | 
        
          | Oct 15 (09:00 - 11:00) | Quantum computing introduction with pennylane (slides) and  (notebook from class). | 
        
          | Oct 22 (09:00 - 11:00) | Deutsch algorithm (notebook from class). | 
        
          | Oct 29 (09:00 - 11:00) | (to be re-scheduled) | 
     
 
    
    
    
    Bibliography
     Computability and Computational Complexity 
    
        - 
            H. R. Lewis and C. H. Papadimitriou.  Elements of the Theory of Computation. Prentice
            Hall (2nd Ed), 1997.
        
- 
            S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge
            University Press, 2009.
        
- 
            C. Moore and S. Mertens The nature of computation. Oxford
            University Press, 2011.
        
 Quantum Computation and Algorithms 
    
        - 
            M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information (10th
            Anniversary Edition). Cambridge University Press, 2010
        
- 
            N. S. Yanofsky and M. A. Mannucci. Quantum Computing for Computer Scientists. Cambridge
            University Press, 2008.
        
- 
            E. Rieffel and W. Polak. Quantum Computing: A Gentle Introduction. MIT Press, 2011.
        
- 
            A. M. Dalzell, S. Mcardle, et al. Quantum Algorithms. Cambridge
            University Press, 2025.
        
- 
            W. Scherer. Mathematics of Quantum Computing. Springer, 2019.
    
 Other (useful) readings 
    
        - 
            N. S. Yanofsky. The Outer Limits of Reason. MIT Press, 2013.
        
- 
            S. Aaronson. Quantum Computing since Democritus. Cambridge
            University Press, 2013.
        
- 
	    J. Preskill Quantum Computing in the NISQ era and beyond. Quantum 2, 79, 2018.
	
 Links 
    
    
    
    Pragmatics
     Lecturers 
    
     Assessment 
    
           -  Individual assignment on  quantum algorithms, 
            with written report and oral defense (40%)
            
        
- 
            Individual written test (60%)
            
        
 Contact 
    
        -  Appointments -  Wed, 18:00-20:00 and Fri, 18:00-20:00 (please send an email the day before)
        
-  Email: lsb at di dot uminho dot pt 
        
-  Last update: 2025.10.29