Advances in quantum computing, quantum error correction, and quantum algorithms

The theoretical framework of quantum computing has promised a considerable advantage in the speed-up of the information processing over the classical computers. It harnesses the theory of quantum mechanics to propose novel frameworks of computing. Several models have been suggested and developed for implementing quantum computers, such as the circuit model of quantum computing, topological quantum computing, and measurement-based quantum computing. We will be concerned with the former model, that is the circuit model of quantum computing. We will first provide a review of the basic axioms of quantum computing that directly rely on those of the theory of quantum mechanics. The circuit model of quantum computation for dealing with computational tasks will be introduced. There are three main problems of concern in this framework including the universality of quantum computing, the advantage of quantum computing over classical computing from the computational complexity point of view, and attempts to counteract the possible effects of noise on a quantum computer, that are studied here. Inspired by some famous quantum algorithms that are proposed in alignment with this model, a recently proposed quantum algorithm for dealing with the problem of testing the linearity of Boolean functions which promises a speed-up over the well-known classical linearity test referred to as the BLR test, will be discussed. We will also discuss the well-known classical algorithm of testing the Boolean functions for being a low-degree polynomial and we may give suggestions on designing quantum algorithms aiming at this algebraic property testing task.