Reader small image

You're reading from  A Practical Guide to Quantum Machine Learning and Quantum Optimization

Product typeBook
Published inMar 2023
PublisherPackt
ISBN-139781804613832
Edition1st Edition
Right arrow
Authors (2):
Elías F. Combarro
Elías F. Combarro
author image
Elías F. Combarro

Elías F. Combarro holds degrees from the University of Oviedo (Spain) in both Mathematics (1997, award for second highest grades in the country) and Computer Science (2002, award for highest grades in the country). After some research stays at the Novosibirsk State University (Russia), he obtained a Ph.D. in Mathematics (Oviedo, 2001) with a dissertation on the properties of some computable predicates under the supervision of Prof. Andrey Morozov and Prof. Consuelo Martínez. Since 2009, Elías F. Combarro has been an associate professor at the Computer Science Department of the University of Oviedo. He has published more than 50 research papers in international journals on topics such as Computability Theory, Machine Learning, Fuzzy Measures and Computational Algebra. His current research focuses on the application Quantum Computing to algebraic, optimisation and machine learning problems. From July 2020 to January 2021, he was a Cooperation Associate at CERN openlab. Currently, he is the Spain representative in the Advisory Board of CERN Quantum Technology Initiative, a member of the Advisory Board of SheQuantum and one of the founders of the QSpain, a quantum computing think tank based in Spain.
Read more about Elías F. Combarro

Samuel González-Castillo
Samuel González-Castillo
author image
Samuel González-Castillo

Samuel González-Castillo holds degrees from the University of Oviedo (Spain) in both Mathematics and Physics (2021). He is currently a mathematics research student at the National University of Ireland, Maynooth, where he works as a graduate teaching assistant. He completed his physics bachelor thesis under the supervision of Prof. Elías F. Combarro and Prof. Ignacio F. Rúa (University of Oviedo), and Dr. Sofia Vallecorsa (CERN). In it, he worked alongside other researchers from ETH Zürich on the application of Quantum Machine Learning to classification problems in High Energy Physis. In 2021, he was a summer student at CERN developing a benchmarking framework for quantum simulators. He has contributed to several conferences on quantum computing.
Read more about Samuel González-Castillo

View More author details
Right arrow

Appendix C
Computational Complexity

An algorithm is a finite answer to an infinite number of questions
— Stephen Kleene

Computational complexity theory is the branch of theoretical computer science that is concerned with quantifying the resources needed to solve problems with algorithms. It asks questions such as “How much time is needed to multiply two integer numbers of bits each?”, “Do you need more memory space to solve a problem than to check its solution?”, or “Is randomness useful in computational tasks?”.

In this brief introduction to computational complexity, we will focus mainly on the concepts involved in estimating how much time is required to solve certain problems. For a thorough treatment of this and other topics (including space or memory complexity, the role of randomness in computation, approximation algorithms, and other advanced matters), you can check standard computational complexity books such as the ones by Sipser...

lock icon
The rest of the page is locked
Previous PageNext Chapter
You have been reading a chapter from
A Practical Guide to Quantum Machine Learning and Quantum Optimization
Published in: Mar 2023Publisher: PacktISBN-13: 9781804613832

Authors (2)

author image
Elías F. Combarro

Elías F. Combarro holds degrees from the University of Oviedo (Spain) in both Mathematics (1997, award for second highest grades in the country) and Computer Science (2002, award for highest grades in the country). After some research stays at the Novosibirsk State University (Russia), he obtained a Ph.D. in Mathematics (Oviedo, 2001) with a dissertation on the properties of some computable predicates under the supervision of Prof. Andrey Morozov and Prof. Consuelo Martínez. Since 2009, Elías F. Combarro has been an associate professor at the Computer Science Department of the University of Oviedo. He has published more than 50 research papers in international journals on topics such as Computability Theory, Machine Learning, Fuzzy Measures and Computational Algebra. His current research focuses on the application Quantum Computing to algebraic, optimisation and machine learning problems. From July 2020 to January 2021, he was a Cooperation Associate at CERN openlab. Currently, he is the Spain representative in the Advisory Board of CERN Quantum Technology Initiative, a member of the Advisory Board of SheQuantum and one of the founders of the QSpain, a quantum computing think tank based in Spain.
Read more about Elías F. Combarro

author image
Samuel González-Castillo

Samuel González-Castillo holds degrees from the University of Oviedo (Spain) in both Mathematics and Physics (2021). He is currently a mathematics research student at the National University of Ireland, Maynooth, where he works as a graduate teaching assistant. He completed his physics bachelor thesis under the supervision of Prof. Elías F. Combarro and Prof. Ignacio F. Rúa (University of Oviedo), and Dr. Sofia Vallecorsa (CERN). In it, he worked alongside other researchers from ETH Zürich on the application of Quantum Machine Learning to classification problems in High Energy Physis. In 2021, he was a summer student at CERN developing a benchmarking framework for quantum simulators. He has contributed to several conferences on quantum computing.
Read more about Samuel González-Castillo