1.
Computational complexity theory
–
A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used. The theory formalizes this intuition, by introducing mathematical models of computation to study these problems and quantifying the amount of resources needed to solve them, such as time and storage. Other complexity measures are used, such as the amount of communication, the number of gates in a circuit. One of the roles of computational complexity theory is to determine the limits on what computers can. Closely related fields in computer science are analysis of algorithms. More precisely, computational complexity theory tries to classify problems that can or cannot be solved with appropriately restricted resources, a computational problem can be viewed as an infinite collection of instances together with a solution for every instance. The input string for a problem is referred to as a problem instance. In computational complexity theory, a problem refers to the question to be solved. In contrast, an instance of this problem is a rather concrete utterance, for example, consider the problem of primality testing. The instance is a number and the solution is yes if the number is prime, stated another way, the instance is a particular input to the problem, and the solution is the output corresponding to the given input. For this reason, complexity theory addresses computational problems and not particular problem instances, when considering computational problems, a problem instance is a string over an alphabet. Usually, the alphabet is taken to be the binary alphabet, as in a real-world computer, mathematical objects other than bitstrings must be suitably encoded. For example, integers can be represented in binary notation, and graphs can be encoded directly via their adjacency matrices and this can be achieved by ensuring that different representations can be transformed into each other efficiently. Decision problems are one of the objects of study in computational complexity theory. A decision problem is a type of computational problem whose answer is either yes or no. A decision problem can be viewed as a language, where the members of the language are instances whose output is yes. The objective is to decide, with the aid of an algorithm, if the algorithm deciding this problem returns the answer yes, the algorithm is said to accept the input string, otherwise it is said to reject the input. An example of a problem is the following
2.
Decision problem
–
In computability theory and computational complexity theory, a decision problem is a question in some formal system that can be posed as a yes-no question, dependent on the input values. For example, the given two numbers x and y, does x evenly divide y. is a decision problem. The answer can be yes or no, and depends upon the values of x and y. A method for solving a problem, given in the form of an algorithm, is called a decision procedure for that problem. A decision procedure for the problem given two numbers x and y, does x evenly divide y. would give the steps for determining whether x evenly divides y. One such algorithm is long division, taught to school children. If the remainder is zero the answer produced is yes, otherwise it is no, a decision problem which can be solved by an algorithm, such as this example, is called decidable. The field of computational complexity categorizes decidable decision problems by how difficult they are to solve, difficult, in this sense, is described in terms of the computational resources needed by the most efficient algorithm for a certain problem. The field of theory, meanwhile, categorizes undecidable decision problems by Turing degree. A decision problem is any arbitrary yes-or-no question on a set of inputs. Because of this, it is traditional to define the decision problem equivalently as and these inputs can be natural numbers, but may also be values of some other kind, such as strings over the binary alphabet or over some other finite set of symbols. The subset of strings for which the problem returns yes is a formal language, alternatively, using an encoding such as Gödel numberings, any string can be encoded as a natural number, via which a decision problem can be defined as a subset of the natural numbers. A classic example of a decision problem is the set of prime numbers. It is possible to decide whether a given natural number is prime by testing every possible nontrivial factor. Although much more efficient methods of primality testing are known, the existence of any method is enough to establish decidability. A decision problem A is called decidable or effectively solvable if A is a recursive set, a problem is called partially decidable, semidecidable, solvable, or provable if A is a recursively enumerable set. Problems that are not decidable are called undecidable, the halting problem is an important undecidable decision problem, for more examples, see list of undecidable problems. Decision problems can be ordered according to many-one reducibility and related to feasible reductions such as polynomial-time reductions
3.
Quantum computing
–
Quantum computing studies theoretical computation systems that make direct use of quantum-mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from binary digital electronic computers based on transistors, a quantum Turing machine is a theoretical model of such a computer, and is also known as the universal quantum computer. The field of computing was initiated by the work of Paul Benioff and Yuri Manin in 1980, Richard Feynman in 1982. A quantum computer with spins as quantum bits was also formulated for use as a quantum space–time in 1968, there exist quantum algorithms, such as Simons algorithm, that run faster than any possible probabilistic classical algorithm. A classical computer could in principle simulate a quantum algorithm, as quantum computation does not violate the Church–Turing thesis, on the other hand, quantum computers may be able to efficiently solve problems which are not practically feasible on classical computers. A classical computer has a made up of bits, where each bit is represented by either a one or a zero. A quantum computer maintains a sequence of qubits, in general, a quantum computer with n qubits can be in an arbitrary superposition of up to 2 n different states simultaneously. A quantum computer operates by setting the qubits in a drift that represents the problem at hand. The sequence of gates to be applied is called a quantum algorithm, the calculation ends with a measurement, collapsing the system of qubits into one of the 2 n pure states, where each qubit is zero or one, decomposing into a classical state. The outcome can therefore be at most n classical bits of information, Quantum algorithms are often probabilistic, in that they provide the correct solution only with a certain known probability. Note that the term non-deterministic computing must not be used in case to mean probabilistic. An example of an implementation of qubits of a computer could start with the use of particles with two spin states, down and up. This is true because any such system can be mapped onto an effective spin-1/2 system, a quantum computer with a given number of qubits is fundamentally different from a classical computer composed of the same number of classical bits. This means that when the state of the qubits is measured. To better understand this point, consider a classical computer that operates on a three-bit register, if there is no uncertainty over its state, then it is in exactly one of these states with probability 1. However, if it is a computer, then there is a possibility of it being in any one of a number of different states. The state of a quantum computer is similarly described by an eight-dimensional vector. Here, however, the coefficients a k are complex numbers, and it is the sum of the squares of the absolute values, ∑ i | a i |2
4.
BPP (complexity)
–
BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in time with a deterministic machine. Alternatively, BPP can be defined using only deterministic Turing machines, for some applications this definition is preferable since it does not mention probabilistic Turing machines. In practice, a probability of 1⁄3 might not be acceptable, however. It can be any constant between 0 and 1⁄2 and the set BPP will be unchanged and this makes it possible to create a highly accurate algorithm by merely running the algorithm several times and taking a majority vote of the answers. For example, if one defined the class with the restriction that the algorithm can be wrong with probability at most 1⁄2100, besides the problems in P, which are obviously in BPP, many problems were known to be in BPP but not known to be in P. The number of problems is decreasing, and it is conjectured that P = BPP. For a long time, one of the most famous problems that was known to be in BPP, in other words, is there an assignment of values to the variables such that when a nonzero polynomial is evaluated on these values, the result is nonzero. It suffices to choose each variables value uniformly at random from a subset of at least d values to achieve bounded error probability. If the access to randomness is removed from the definition of BPP, in the definition of the class, if we replace the ordinary Turing machine with a quantum computer, we get the class BQP. Adding postselection to BPP, or allowing computation paths to have different lengths, BPPpath is known to contain NP, and it is contained in its quantum counterpart PostBQP. A Monte Carlo algorithm is an algorithm which is likely to be correct. Problems in the class BPP have Monte Carlo algorithms with polynomial bounded running time and this is compared to a Las Vegas algorithm which is a randomized algorithm which either outputs the correct answer, or outputs fail with low probability. Las Vegas algorithms with polynomial bound running times are used to define the class ZPP, alternatively, ZPP contains probabilistic algorithms that are always correct and have expected polynomial running time. This is weaker than saying it is a polynomial time algorithm, since it may run for super-polynomial time and it is known that BPP is closed under complement, that is, BPP = co-BPP. BPP is low for itself, meaning that a BPP machine with the power to solve BPP problems instantly is not any more powerful than the machine without this extra power. The relationship between BPP and NP is unknown, it is not known whether BPP is a subset of NP, NP is a subset of BPP or neither. If NP is contained in BPP, which is considered unlikely since it would imply practical solutions for NP-complete problems, then NP = RP and it is known that RP is a subset of BPP, and BPP is a subset of PP
5.
Quantum algorithm
–
In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a sequence of instructions, or a step-by-step procedure for solving a problem. Similarly, an algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Problems which are undecidable using classical computers remain undecidable using quantum computers, what makes quantum algorithms interesting is that they might be able to solve some problems faster than classical algorithms. The most well known algorithms are Shors algorithm for factoring, Shors algorithms runs exponentially faster than the best known classical algorithm for factoring, the general number field sieve. Grovers algorithm runs quadratically faster than the best possible classical algorithm for the same task, Quantum algorithms are usually described, in the commonly used circuit model of quantum computation, by a quantum circuit which acts on some input qubits and terminates with a measurement. A quantum circuit consists of quantum gates which act on at most a fixed number of qubits. Quantum algorithms may also be stated in other models of quantum computation, Quantum algorithms can be categorized by the main techniques used by the algorithm. Quantum algorithms may also be grouped by the type of problem solved, the quantum Fourier transform is the quantum analogue of the discrete Fourier transform, and is used in several quantum algorithms. The Hadamard transform is also an example of a quantum Fourier transform over a vector space over the field F2. The quantum Fourier transform can be implemented on a quantum computer using only a polynomial number of quantum gates. The algorithm determines whether a function f is constant or balanced. Simons algorithm solves a black-box problem exponentially faster than any classical algorithm and this algorithm, which achieves an exponential speedup over all classical algorithms that we consider efficient, was the motivation for Shors factoring algorithm. The quantum phase estimation algorithm is used to determine the eigenphase of an eigenvector of a unitary gate given a state proportional to the eigenvector. The algorithm is used as a subroutine in other algorithms. Shors algorithm solves the discrete problem and the integer factorization problem in polynomial time. These problems are not known to be in P or NP-complete and it is also one of the few quantum algorithms that solves a non–black-box problem in polynomial time where the best known classical algorithms run in super-polynomial time. There are efficient quantum algorithms known for the Abelian hidden subgroup problem, the more general hidden subgroup problem, where the group isnt necessarily abelian, is a generalization of the previously mentioned problems and graph isomorphism and certain lattice problems
6.
Algorithm
–
In mathematics and computer science, an algorithm is a self-contained sequence of actions to be performed. Algorithms can perform calculation, data processing and automated reasoning tasks, an algorithm is an effective method that can be expressed within a finite amount of space and time and in a well-defined formal language for calculating a function. The transition from one state to the next is not necessarily deterministic, some algorithms, known as randomized algorithms, giving a formal definition of algorithms, corresponding to the intuitive notion, remains a challenging problem. In English, it was first used in about 1230 and then by Chaucer in 1391, English adopted the French term, but it wasnt until the late 19th century that algorithm took on the meaning that it has in modern English. Another early use of the word is from 1240, in a manual titled Carmen de Algorismo composed by Alexandre de Villedieu and it begins thus, Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris. Which translates as, Algorism is the art by which at present we use those Indian figures, the poem is a few hundred lines long and summarizes the art of calculating with the new style of Indian dice, or Talibus Indorum, or Hindu numerals. An informal definition could be a set of rules that precisely defines a sequence of operations, which would include all computer programs, including programs that do not perform numeric calculations. Generally, a program is only an algorithm if it stops eventually, but humans can do something equally useful, in the case of certain enumerably infinite sets, They can give explicit instructions for determining the nth member of the set, for arbitrary finite n. An enumerably infinite set is one whose elements can be put into one-to-one correspondence with the integers, the concept of algorithm is also used to define the notion of decidability. That notion is central for explaining how formal systems come into being starting from a set of axioms. In logic, the time that an algorithm requires to complete cannot be measured, from such uncertainties, that characterize ongoing work, stems the unavailability of a definition of algorithm that suits both concrete and abstract usage of the term. Algorithms are essential to the way computers process data, thus, an algorithm can be considered to be any sequence of operations that can be simulated by a Turing-complete system. Although this may seem extreme, the arguments, in its favor are hard to refute. Gurevich. Turings informal argument in favor of his thesis justifies a stronger thesis, according to Savage, an algorithm is a computational process defined by a Turing machine. Typically, when an algorithm is associated with processing information, data can be read from a source, written to an output device. Stored data are regarded as part of the state of the entity performing the algorithm. In practice, the state is stored in one or more data structures, for some such computational process, the algorithm must be rigorously defined, specified in the way it applies in all possible circumstances that could arise. That is, any conditional steps must be dealt with, case-by-case
7.
Quantum circuit
–
This analogous structure is referred to as an n-qubit register. The elementary logic gates of a computer, other than the NOT gate, are not reversible. A reversible gate is a function on n-bit data that returns n-bit data. The set of data is the space n, which consists of 2n strings of 0s. More precisely, a reversible gate is a bijective mapping f from the set n of n-bit data onto itself. An example of such a reversible gate f is a mapping that applies a fixed permutation to its inputs, for reasons of practical engineering, one typically studies gates only for small values of n, e. g. n=1, n=2 or n=3. These gates can be described by tables. To define quantum gates, we first need to specify the quantum replacement of an n-bit datum, the quantized version of classical n-bit space n is the Hilbert space H QB = ℓ2. This is by definition the space of complex-valued functions on n and is naturally an inner product space and this space can also be regarded as consisting of linear superpositions of classical bit strings. Note that HQB is a space over the complex numbers of dimension 2n. The elements of space are called n-qubits. Using Dirac ket notation, if x1, x2, all n-qubits are complex linear combinations of these computational basis states. Quantum logic gates, in contrast to classical logic gates, are always reversible, One requires a special kind of reversible function, namely a unitary mapping, that is, a linear transformation of a complex inner product space that preserves the Hermitian inner product. An n-qubit quantum gate is a unitary mapping U from the space HQB of n-qubits onto itself, typically, we are only interested in gates for small values of n. A reversible n-bit classical logic gate gives rise to a reversible n-bit quantum gate as follows, to each reversible n-bit logic gate f corresponds a quantum gate Wf defined as follows, note that Wf permutes the computational basis states. Of particular importance is the controlled NOT gate WCNOT defined on a quantized 2 qubit, other examples of quantum logic gates derived from classical ones are the Toffoli gate and the Fredkin gate. However, the Hilbert-space structure of the qubits permits many quantum gates that are not induced by classical ones, again, we consider first reversible classical computation. Conceptually, there is no difference between a reversible n-bit circuit and a reversible n-bit logic gate, either one is just a function on the space of n bit data
8.
Quantum Turing machine
–
A quantum Turing machine, also a universal quantum computer, is an abstract machine used to model the effect of a quantum computer. It provides a simple model which captures all of the power of quantum computation. Any quantum algorithm can be expressed formally as a particular quantum Turing machine, Quantum Turing machines are not always used for analyzing quantum computation, the quantum circuit is a more common model. Quantum Turing machines can be related to classical and probabilistic Turing machines in a framework based on transition matrices, Iriyama, Ohya, and Volovich have developed a model of a linear quantum Turing machine. This is a generalization of a classical QTM that has mixed states and these allow the representation of quantum measurements without classical outcomes. A quantum Turing machine with postselection was defined by Scott Aaronson, a way of understanding the quantum Turing machine is that it generalizes the classical Turing machine in the same way that the quantum finite automaton generalizes the deterministic finite automaton. That is, a classical Turing machine is described by a 7-tuple M = ⟨ Q, Γ, b, Σ, δ, q 0, F ⟩, for a three-tape quantum Turing machine, The set of states Q is replaced by a Hilbert space. The tape alphabet symbols Γ are likewise replaced by a Hilbert space, the blank symbol b ∈ Γ corresponds to the zero-vector. The input and output symbols Σ are usually taken as a set, as in the classical system, thus. The transition function δ, Σ × Q ⊗ Γ → Σ × Q ⊗ Γ × is a generalization of a transition monoid, the initial state q 0 ∈ Q may be either a mixed state or a pure state. The set F of final or accepting states is a subspace of the Hilbert space Q and this question of measurement affects the way in which writes to the output tape are defined. Satoshi Iriyama, Masanori Ohya, Igor Volovich, generalized Quantum Turing Machine and its Application to the SAT Chaos Algorithm. Abstract of Deutschs paper The quantum computer – history
. Bibcode:2005RSPSA.461.3473A. doi:10.1098/rspa.2005.1546.. Preprint available at [1]
