Early researchers attempting to simulate complex quantum mechanical interactions on digital computers discovered that they very quickly consumed the computers’ available memory\nresources, because the state space of a quantum system typically grows exponentially with problem size. Consequently, Richard Feynman proposed in 1982 that perhaps the only way to simulate complex quantum mechanical situations was by simulating them on some quantum mechanical system. Quantum computers attempt to exploit this idea incorporating the special properties of quantum mechanics, such as the superposition of states and entanglement, into a computing device. Two key algorithms have been discovered which would run on this new type of computer, Shor’s factorization algorithm discovered in 1994, which provides an exponential speedup over classical algorithms and Grover’s search algorithm in 1996, which provides a quadratic speedup. Following this in 1999 Meyer initiated the field of quantum game theory by introducing quantum mechanical states into the framework of classical game theory. In this thesis, we firstly investigate the phase estimation procedure, due to its importance as the basis for Shor’s factorization algorithm, for which a new error formula is found using an improved symmetrical definition of the error. Unlike other existing error formulas which require approximations in their derivation, our result is obtained analytically. The work on the phase estimation procedure then motivates the development of computer software written in the Java programming language, which can simulate the common algorithms and visually display their behavior on a circuit board type layout. The software is found useful in verifying the new error formula described above and to test ideas for new algorithms. Being written in Java, it is envisaged that it could be placed online and used as a learning tool for new students to the field. We then investigate the second key algorithm of quantum computing, the Grover search algorithm. It is already known that the Grover search is an SU(2) rotation but the idea is extended by deriving the three generators in terms of the two non-orthogonal basis vectors, representing the solution and initial states. We then demonstrate that the Grover search is equivalent to the precession of the polarization axis of a spin- 1/2 particle in a magnetic field. At this point we introduce geometric algebra (GA), because of its efficient implementation of rotations and its associated visual representation, and hence ideal to describe the Grover search process. It was found to provide a simple algebraic solution to the exact Grover search problem as well providing a simple visual picture describing the general solution to Meyer’s quantum penny flip game, which is a simple two-player quantum game based on the manipulation of a single qubit and hence closely analogous to the Grover search process. We then extend the work on quantum games developing two-player, three-player and N player quantum games in the context of an EPR type experiment, which has the advantage of providing a sound physical basis to quantum games avoiding the common criticism of other quantum game frameworks regarding the proper embedding of the classical game. Using the algebraic approach of GA, we solve the general N player game, without requiring the use of matrices which become unworkable for large N. Games based on non-factorisable joint probabilities were then also developed which provided a more general framework for both classical and quantum games, and allows the field of quantum games to be accessible to nonphysicists, as it does not employ Dirac’s bra-ket notation. In summary, several new results in the field of Quantum computing were produced, including an improved error formula for phase estimation [JMCL11b], a general solution to Meyer’s quantum penny flip game [CILVS09] and a paper producing quantum games from non-factorisable joint probabilities [CIA10], as well as an EPR framework for quantum games [JMCL11a], refer attached papers.
Early researchers attempting to simulate complex quantum mechanical interactions on digital computers discovered that they very quickly consumed the computers’ available memory\nresources, because the state space of a quantum system typically grows exponentially with problem size. Consequently, Richard Feynman proposed in 1982 that perhaps the only way to simulate complex quantum mechanical situations was by simulating them on some quantum mechanical system. Quantum computers attempt to exploit this idea incorporating the special properties of quantum mechanics, such as the superposition of states and entanglement, into a computing device. Two key algorithms have been discovered which would run on this new type of computer, Shor’s factorization algorithm discovered in 1994, which provides an exponential speedup over classical algorithms and Grover’s search algorithm in 1996, which provides a quadratic speedup. Following this in 1999 Meyer initiated the field of quantum game theory by introducing quantum mechanical states into the framework of classical game theory. In this thesis, we firstly investigate the phase estimation procedure, due to its importance as the basis for Shor’s factorization algorithm, for which a new error formula is found using an improved symmetrical definition of the error. Unlike other existing error formulas which require approximations in their derivation, our result is obtained analytically. The work on the phase estimation procedure then motivates the development of computer software written in the Java programming language, which can simulate the common algorithms and visually display their behavior on a circuit board type layout. The software is found useful in verifying the new error formula described above and to test ideas for new algorithms. Being written in Java, it is envisaged that it could be placed online and used as a learning tool for new students to the field. We then investigate the second key algorithm of quantum computing, the Grover search algorithm. It is already known that the Grover search is an SU(2) rotation but the idea is extended by deriving the three generators in terms of the two non-orthogonal basis vectors, representing the solution and initial states. We then demonstrate that the Grover search is equivalent to the precession of the polarization axis of a spin- 1/2 particle in a magnetic field. At this point we introduce geometric algebra (GA), because of its efficient implementation of rotations and its associated visual representation, and hence ideal to describe the Grover search process. It was found to provide a simple algebraic solution to the exact Grover search problem as well providing a simple visual picture describing the general solution to Meyer’s quantum penny flip game, which is a simple two-player quantum game based on the manipulation of a single qubit and hence closely analogous to the Grover search process. We then extend the work on quantum games developing two-player, three-player and N player quantum games in the context of an EPR type experiment, which has the advantage of providing a sound physical basis to quantum games avoiding the common criticism of other quantum game frameworks regarding the proper embedding of the classical game. Using the algebraic approach of GA, we solve the general N player game, without requiring the use of matrices which become unworkable for large N. Games based on non-factorisable joint probabilities were then also developed which provided a more general framework for both classical and quantum games, and allows the field of quantum games to be accessible to nonphysicists, as it does not employ Dirac’s bra-ket notation. In summary, several new results in the field of Quantum computing were produced, including an improved error formula for phase estimation [JMCL11b], a general solution to Meyer’s quantum penny flip game [CILVS09] and a paper producing quantum games from non-factorisable joint probabilities [CIA10], as well as an EPR framework for quantum games [JMCL11a], refer attached papers.
The Grover search algorithm is one of the two key algorithms in the field of quantum computing, and hence it is of significant interest to describe it in the most efficient mathematical formalism. We show firstly, that Clifford's formalism of geometric algebra, provides a significantly more efficient representation than the conventional Bra-ket notation, and secondly, that the basis defined by the states of maximum and minimum weight in the Grover search space, allows a simple visualization of the Grover search as the precession of a spin-1/2 particle. Using this formalism we efficiently solve the exact search problem, as well as easily representing more general search situations.
Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on Grover’s algorithm, a quantum algorithm for unstructured search problems that provides a quadratic speedup over classical approaches. In an unstructured search problem, we are given a function (often represented as an oracle) that marks one or more “correct” solutions among NNN possible candidates. A classical algorithm requires on the order of O(N)O(N)O(N) evaluations in the worst case. In contrast, Grover’s algorithm finds a solution using only O(N)O(\sqrt{N})O(N) oracle queries. This quadratic improvement implies: The quantum algorithm requires roughly the square root of the number of operations needed classically. Any classical algorithm for unstructured search must have cost at least quadratic relative to Grover’s quantum procedure. Core Idea of the Algorithm Grover’s algorithm relies on: Preparation of a uniform superposition (typically using Hadamard gates). An oracle that marks valid solutions via phase inversion. The Grover diffusion operator, which amplifies the probability amplitude of the marked states through interference. By repeatedly applying the Grover operator, the amplitude of the desired solution grows while others diminish, allowing measurement to reveal the correct answer with high probability. Practical Considerations Despite its theoretical elegance and wide applicability, the quadratic speedup of Grover’s algorithm is unlikely to yield near-term practical advantage. Modern classical hardware operates at extremely high clock rates and is vastly more mature than current quantum devices. For problem sizes accessible to today’s quantum computers, classical systems remain dominant. However, history shows that even sub-quadratic classical improvements — such as: Fast Fourier Transform (FFT) Efficient sorting algorithms like quicksort and mergesort have had transformative practical impact. The crucial distinction is that Grover’s algorithm depends on fundamentally different hardware — quantum processors — which are still in early development. Long-Term Perspective As quantum hardware advances in qubit count, coherence time, and error correction, Grover’s quadratic advantage may become practically significant for: Cryptographic key search Optimization heuristics Combinatorial search problems Amplitude amplification subroutines in broader quantum algorithms Through hands-on experimentation on IBM Q, this lesson demonstrates how theoretical amplitude amplification translates into executable quantum circuits, reinforcing the relationship between interference, probability amplitudes, and computational complexity.
Quantum Computing is widely perceived to be one of the ways forward in the future of computation as the end of Moore’s law is almost here. Instead of using bits in classical computers, quantum computers manipulate qubits which are governed by the phenomena of superposition and entanglement. In this paper, we demonstrate the relevance of quantum computing in game theory and database search applications. Through a simple example of coin tossing, we show how it is possible to organise a game where one player adopting a quantum strategy is guaranteed to win. It is also shown that the other player, using a second coin (qubit), can subvert this action to award the wins to themselves without the first player’s knowledge. In another application, a modified Grover’s database search algorithm is applied to clone an arbitrary quantum state of a qubit to a duplicate qubit. In both cases, the comparison of simulated and actual results emphasises on the hardware limitations of the current error-prone quantum computers. The quantum computer programs are designed using quantum gates and simulated in the Quantum Information Software Kit before testing on the IBM Q 5.1 (ibmqx4) quantum computer.
The advent of quantum computing has ushered in a new era of computational capabilities, promising to revolutionize the resolution of complex problems. Unlike classical computers, which rely on binary digits (bits) to process information, quantum computers utilize quantum bits (qubits) that can exist in multiple states simultaneously due to the principles of superposition and entanglement inherent in quantum mechanics. This fundamental difference allows quantum computers to perform certain calculations exponentially faster than their classical counterparts, offering profound implications for fields ranging from cryptography to material science. At the heart of this transformative potential lie quantum algorithms, specifically designed to harness the unique properties of quantum systems to tackle problems currently intractable for classical computers. Notable examples include Shor's algorithm for integer factorization, which threatens the security of widely used cryptographic schemes, and Grover's algorithm for unstructured search, which provides a quadratic speedup over classical approaches. Beyond these pioneering works, ongoing research continues to uncover new quantum algorithms capable of addressing a broad spectrum of applications. The proposed method leverages the principles of quantum mechanics to develop efficient algorithms that outperform classical approaches in solving complex computational problems. By harnessing the unique properties of quantum bits (qubits), such as superposition and entanglement, the method aims to achieve superior accuracy and efficiency in various applications. The performance of the proposed method was evaluated using several key metrics: an accuracy of 94.8%, a Root Mean Squared Error (RMSE) of 0.208, and a Mean Absolute Error (MAE) of 0.406. These metrics collectively underscore the robustness and reliability of the proposed quantum algorithms, highlighting their potential to significantly enhance computational efficiency and accuracy across various domains. This study delves into the development of quantum algorithms, exploring their theoretical foundations, practical implementations, and the challenges faced in their realization. By leveraging the principles of quantum mechanics, these algorithms hold the promise of not only solving existing problems more efficiently but also unlocking new computational paradigms previously deemed unattainable. Through a comprehensive analysis, this research aims to elucidate the current state of quantum algorithm research, highlight the advancements made, and identify the pathways forward in this rapidly evolving field.
Quantum computing is the field that studies computation using quantum mechanical systems, exploiting properties such as superposition or entanglement. The focus of this project will be on quantum phase estimation algorithms. The formalism commonly used to represent quantum algorithms as quantum circuits composed by qubits and quantum gates will be presented. Then, we will be able to explain the quantum Fourier transform (that is exponentially faster than its classical analogue) and three quantum phase estimation algorithms: Kitaev’s phase estimation (KPEA), the phase estimation algorithm based on QFT (PEA) and the iterative quantum phase estimation algorithm based on a semiclassical Fourier transform (IPEA). We will use the Qiskit framework in order to run simulations of such algorithms, and even run them in real IBM Q Experience quantum computers (specifically, we will use the 5 qubit computer ibmq_essex). Statistical post-processing techniques will be essential in order to extract a phase estimation from the results obtained. We will use two post-processing techniques: the majority and the average rule. The performance of these methods applied to the results of several simulations and executions in ibmq_essex will be studied. At last, we will talk about the possible applications of phase estimation algorithms. Phase estimation is used as a subroutine in the field of quantum simulation, allowing us to obtain several magnitudes of a quantum system such as the energy levels. We will present an efficient quantum algorithm for factoring called Shor’s algorithm. The cost of factorization with a classical computer increases exponentially with the size of the input, so this is a example of a task that cannot be solved efficiently on a classical computer, but can be solved efficiently by a quantum computer. Phase estimation is also used in the field of quantum metrology. Specifically, an N-V center can be used to measure magnetic fields with high sensitivity and spatial resolution operating at room temperature thanks to a measuring protocol based on phase estimation.
Quantum computing represents a fundamentally new paradigm in information processing, in which information is encoded and manipulated using two-level quantum systems known as qubits, whose evolution is governed by the principles of quantum mechanics. This chapter presents a structured introduction to the theoretical foundations of quantum computation, beginning with the limitations of classical computation and the physical constraints that motivate the need for a quantum model of computation. We develop the mathematical framework required to describe quantum information, introducing qubits as state vectors in Hilbert space and examining the roles of superposition, measurement, and unitary evolution. Single-qubit operations are presented through the Pauli and Hadamard gates, along with their geometric interpretation on the Bloch sphere. Building on this formalism, the discussion is extended to multi-qubit systems using tensor products, and quantum entanglement is introduced as a non-classical correlation fundamental to quantum information processing. The chapter then explores quantum algorithms, focusing on Grover’s unstructured search algorithm, to demonstrate how superposition, interference, and entanglement can be harnessed to achieve computational advantages over classical approaches. Finally, the chapter discusses applications of quantum computation, including quantum simulation, cryptography, search and optimization problems, and near-term hybrid quantum algorithms such as the Variational Quantum Eigensolver (VQE)and the Quantum Approximate Optimization (QAO) Algorithm, highlighting their relevance in the noisy intermediate-scale quantum (NISQ) era.