|
Simon's Algorithm
In computational complexity theory and quantum computing, Simon's problem is a computational problem that is proven to be solved exponentially faster on a quantum computer than on a classical (that is, traditional) computer. The quantum algorithm solving Simon's problem, usually called Simon's algorithm, served as the inspiration for Shor's algorithm. Both problems are special cases of the abelian hidden subgroup problem, which is now known to have efficient quantum algorithms. The problem is set in the model of decision tree complexity or query complexity and was conceived by Daniel Simon in 1994. Simon exhibited a quantum algorithm that solves Simon's problem exponentially faster and with exponentially fewer queries than the best probabilistic (or deterministic) classical algorithm. In particular, Simon's algorithm uses a linear number of queries and any classical probabilistic algorithm must use an exponential number of queries. This problem yields an oracle separation betwe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Simon Problems
In mathematics, the Simon problems (or Simon's problems) are a series of fifteen questions posed in the year 2000 by Barry Simon, an American mathematical physicist. Inspired by other collections of mathematical problems and open conjectures, such as the famous list by David Hilbert, the Simon problems concern quantum operators. Eight of the problems pertain to anomalous spectral behavior of Schrödinger operators, and five concern operators that incorporate the Coulomb potential. In 2014, Artur Avila won a Fields Medal for work including the solution of three Simon problems. Among these was the problem of proving that the set of energy levels of one particular abstract quantum system was in fact the Cantor set, a challenge known as the "Ten Martini Problem" after the reward that Mark Kac offered for solving it. The 2000 list was a refinement of a similar set of problems that Simon had posed in 1984. Context Background definitions for the "Coulomb energies" problems (N non ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bernstein–Vazirani Algorithm
The Bernstein–Vazirani algorithm, which solves the Bernstein–Vazirani problem, is a quantum algorithm invented by Ethan Bernstein and Umesh Vazirani in 1992. It is a restricted version of the Deutsch–Jozsa algorithm where instead of distinguishing between two different classes of functions, it tries to learn a string encoded in a function. The Bernstein–Vazirani algorithm was designed to prove an oracle separation between complexity classes BQP and BPP. Problem statement Given an oracle that implements a function f\colon\^n\rightarrow \ in which f(x) is promised to be the dot product between x and a secret string s \in \^n modulo 2, f(x) = x \cdot s = x_1s_1 \oplus x_2s_2 \oplus \cdots \oplus x_ns_n, find s. Algorithm Classically, the most efficient method to find the secret string is by evaluating the function n times with the input values x = 2^ for all i \in \: : \begin f(1000\cdots0_n) & = s_1 \\ f(0100\cdots0_n) & = s_2 \\ f(0010\cdots0_n) & = s_3 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Independence
In the theory of vector spaces, a set of vectors is said to be if there is a nontrivial linear combination of the vectors that equals the zero vector. If no such linear combination exists, then the vectors are said to be . These concepts are central to the definition of dimension. A vector space can be of finite dimension or infinite dimension depending on the maximum number of linearly independent vectors. The definition of linear dependence and the ability to determine whether a subset of vectors in a vector space is linearly dependent are central to determining the dimension of a vector space. Definition A sequence of vectors \mathbf_1, \mathbf_2, \dots, \mathbf_k from a vector space is said to be ''linearly dependent'', if there exist scalars a_1, a_2, \dots, a_k, not all zero, such that :a_1\mathbf_1 + a_2\mathbf_2 + \cdots + a_k\mathbf_k = \mathbf, where \mathbf denotes the zero vector. This implies that at least one of the scalars is nonzero, say a_1\ne 0, an ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Simons Algorithm
In computational complexity theory and quantum computing, Simon's problem is a computational problem that is proven to be solved exponentially faster on a quantum computer than on a classical (that is, traditional) computer. The quantum algorithm solving Simon's problem, usually called Simon's algorithm, served as the inspiration for Shor's algorithm. Both problems are special cases of the abelian hidden subgroup problem, which is now known to have efficient quantum algorithms. The problem is set in the model of decision tree complexity or query complexity and was conceived by Daniel Simon in 1994. Simon exhibited a quantum algorithm that solves Simon's problem exponentially faster and with exponentially fewer queries than the best probabilistic (or deterministic) classical algorithm. In particular, Simon's algorithm uses a linear number of queries and any classical probabilistic algorithm must use an exponential number of queries. This problem yields an oracle separation betwe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Birthday Problem
In probability theory, the birthday problem asks for the probability that, in a set of randomly chosen people, at least two will share a birthday. The birthday paradox is that, counterintuitively, the probability of a shared birthday exceeds 50% in a group of only 23 people. The birthday paradox is a veridical paradox: it appears wrong, but is in fact true. While it may seem surprising that only 23 individuals are required to reach a 50% probability of a shared birthday, this result is made more intuitive by considering that the comparisons of birthdays will be made between every possible pair of individuals. With 23 individuals, there are (23 × 22) / 2 = 253 pairs to consider, much more than half the number of days in a year. Real-world applications for the birthday problem include a cryptographic attack called the birthday attack, which uses this probabilistic model to reduce the complexity of finding a collision for a hash function, as well as ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Decision Problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whether a given natural number is prime. Another is the problem "given two numbers ''x'' and ''y'', does ''x'' evenly divide ''y''?". The answer is either 'yes' or 'no' depending upon the values of ''x'' and ''y''. A method for solving a decision problem, given in the form of an algorithm, is called a decision procedure for that problem. A decision procedure for the decision 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. If the remainder is zero the answer is 'yes', otherwise it is 'no'. A decision problem which can be solved by an algorithm is called ''decidable''. Decision problems typically appear in mat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Injective Function
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositive statement.) In other words, every element of the function's codomain is the image of one element of its domain. The term must not be confused with that refers to bijective functions, which are functions such that each element in the codomain is an image of exactly one element in the domain. A homomorphism between algebraic structures is a function that is compatible with the operations of the structures. For all common algebraic structures, and, in particular for vector spaces, an is also called a . However, in the more general context of category theory, the definition of a monomorphism differs from that of an injective homomorphism. This is thus a theorem that they are equivalent for algebraic structures; see for more details. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Black Box
In science, computing, and engineering, a black box is a system which can be viewed in terms of its inputs and outputs (or transfer characteristics), without any knowledge of its internal workings. Its implementation is "opaque" (black). The term can be used to refer to many inner workings, such as those of a transistor, an engine, an algorithm, the human brain, or an institution or government. To analyse an open system with a typical "black box approach", only the behavior of the stimulus/response will be accounted for, to infer the (unknown) ''box''. The usual representation of this ''black box system'' is a data flow diagram centered in the box. The opposite of a black box is a system where the inner components or logic are available for inspection, which is most commonly referred to as a white box (sometimes also known as a "clear box" or a "glass box"). History The modern meaning of the term "black box" seems to have entered the English language around 1945. In electr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''t''(''n'')), the set of all problems that can be solved by Turing machines using ''O''(''t''(''n'')) space for some function ''t'' of the input size ''n'', then we can define PSPACE formally asArora & Barak (2009) p.81 :\mathsf = \bigcup_ \mathsf(n^k). PSPACE is a strict superset of the set of context-sensitive languages. It turns out that allowing the Turing machine to be nondeterministic does not add any extra power. Because of Savitch's theorem,Arora & Barak (2009) p.85 NPSPACE is equivalent to PSPACE, essentially because a deterministic Turing machine can simulate a non-deterministic Turing machine without needing much more space (even though it may use much more time).Arora & Barak (2009) p.86 Also, the complements of all problems in PSPACE are also in PSPACE, meaning tha ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
EQP (complexity)
In computational complexity theory, exact quantum polynomial time (EQP or sometimes QP) is the class of decision problems that can be solved by a quantum computer with zero error probability and in guaranteed worst-case polynomial time. It is the quantum analogue of the complexity class P. This is in contrast to bounded-error quantum computing, where quantum algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...s are expected to run in polynomial time, but may not always do so. In the original definition of EQP, each language was computed by a single quantum Turing machine (QTM), using a finite gate set whose amplitudes could be computed in polynomial time. However, some results have required the use of an infinite gate set. The amplitudes in the gate set are typically ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME(''n''O(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. Cobham's thesis holds that P is the class of computational problems that are "efficiently solvable" or " tractable". This is inexact: in practice, some problems not known to be in P have practical solutions, and some that are in P do not, but this is a useful rule of thumb. Definition A language ''L'' is in P if and only if there exists a deterministic Turing machine ''M'', such that * ''M'' runs for polynomial time on all inputs * For all ''x'' in ''L'', ''M'' outputs 1 * For all ''x'' not in ''L'', ''M'' outputs 0 P can also be viewed as a uniform family of boolean circuits. A language ''L'' is in P if and only if there exists a polynomial-time uniform family of boolean circuits \, such that * For all n \in \m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Deutsch–Jozsa Algorithm
The Deutsch–Jozsa algorithm is a deterministic quantum algorithm proposed by David Deutsch and Richard Jozsa in 1992 with improvements by Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca in 1998. Although of little current practical use, it is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. The Deutsch–Jozsa problem is specifically designed to be easy for a quantum algorithm and hard for any deterministic classical algorithm. It is a black box problem that can be solved efficiently by a quantum computer with no error, whereas a deterministic classical computer would need a exponential number of queries to the black box to solve the problem. More formally, it yields an oracle relative to which EQP, the class of problems that can be solved exactly in polynomial time on a quantum computer, and P are different. Since the problem is easy to solve on a probabilistic classic ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
