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

Abstract

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.

Kuantum hesaplamanın teorik çerçevesi, klasik bilgisayarlara kıyasla bilgi işlemenin hızlandırılmasında önemli bir avantaj vaat etmiştir. Kuantum mekaniği teorisini kullanarak yeni hesaplama çerçeveleri önermektedir. Kuantum bilgisayarlarını uygulamak için kuantum hesaplamanın devre modeli, topolojik kuantum hesaplama ve ölçüm tabanlı kuantum hesaplama gibi çeşitli modeller önerilmiş ve geliştirilmiştir. Biz, birinci model olan kuantum hesaplamanın devre modeli ile ilgileneceğiz. Öncelikle, kuantum mekaniği teorisinin aksiyomlarına doğrudan dayanan kuantum hesaplamanın temel aksiyomlarının bir incelemesini sunacağız. Hesaplamalı görevlerle başa çıkmak için kuantum hesaplamanın devre modeli tanıtılacaktır. Bu çerçevede, kuantum hesaplamanın evrenselliği, hesaplamalı karmaşıklık açısından klasik hesaplamaya göre kuantum hesaplamanın avantajı ve gürültünün kuantum bilgisayar üzerindeki olası etkilerini dengeleme girişimleri de dahil olmak üzere endişe duyulan üç ana sorun vardır ve bunlar burada incelenmektedir. Bu modelle uyumlu olarak önerilen bazı ünlü kuantum algoritmalarından esinlenerek, BLR testi olarak adlandırılan iyi bilinen klasik doğrusallık testine göre hızlanma vaat eden Boole fonksiyonlarının doğrusallığını test etme sorunuyla başa çıkmak için yakın zamanda önerilen bir kuantum algoritması tartışılacaktır. Ayrıca, Boole fonksiyonlarının düşük dereceli bir polinom olduğu için test edilmesinin iyi bilinen klasik algoritmasını tartışacağız ve bu cebirsel özellik test görevini hedefleyen kuantum algoritmaları tasarlamak için önerilerde bulunabiliriz.