|
Hidden Subgroup Problem
The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science. The framework captures problems such as factoring, discrete logarithm, graph isomorphism, and the shortest vector problem. This makes it especially important in the theory of quantum computing because Shor's quantum algorithm for factoring is an instance of the hidden subgroup problem for finite Abelian groups, while the other problems correspond to finite groups that are not Abelian. Problem statement Given a group G, a subgroup H \leq G, and a set X, we say a function f : G \to X hides the subgroup H if for all g_1 g_2 \in G, f(g_1) = f(g_2) if and only if g_1 H = g_2 H. Equivalently, f is constant on the cosets of ''H'', while it is different between the different cosets of ''H''. Hidden subgroup problem: Let G be a group, X a finite set, and f : G \to X a function that hides a subgroup H \leq G. The function f is given via an oracle, which uses O(\log , G, + \log , ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics with the major subdisciplines of number theory, algebra, geometry, and analysis, respectively. There is no general consensus among mathematicians about a common definition for their academic discipline. Most mathematical activity involves the discovery of properties of abstract objects and the use of pure reason to prove them. These objects consist of either abstractions from nature orin modern mathematicsentities that are stipulated to have certain properties, called axioms. A ''proof'' consists of a succession of applications of deductive rules to already established results. These results include previously proved theorems, axioms, andin case of abstraction from naturesome basic properties that are considered true starting points of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Quantum Computer
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though current quantum computers may be too small to outperform usual (classical) computers for practical applications, larger realizations are believed to be capable of solving certain computational problems, such as integer factorization (which underlies RSA encryption), substantially faster than classical computers. The study of quantum computing is a subfield of quantum information science. There are several models of quantum computation with the most widely used being quantum circuits. Other models include the quantum Turing machine, quantum annealing, and adiabatic quantum computation. Most models are based on the quantum bit, or "qubit", which is somewhat analogous to the bit in classical computation. A qubit can be in a 1 or 0 quantum ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hidden Shift Problem
The Hidden shift problem states: Given an oracle O that encodes two functions f and g, there is an n-bit string s for which g(x) = f(x + s) for all x. Find s. Many functions, such as the Legendre symbol and Bent functions, satisfy these constraints. With a quantum algorithm that's defined as ", s\rangle = H^ O_ H^ O_ H^, 0^\rangle " where H is the Hadamard gate and \hat is the Fourier transform of g, this problem can be solved in a polynomial number of queries to O while taking exponential queries with a classical algorithm. The difference between the Hidden subgroup problem and the Hidden shift problem is that the former focuses on the underlying group while the latter focuses on the underlying ring or field Field may refer to: Expanses of open ground * Field (agriculture), an area of land used for agricultural purposes * Airfield, an aerodrome that lacks the infrastructure of an airport * Battlefield * Lawn, an area of mowed grass * Meadow, a grass .... References {{reflist ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Dual Group (Quantum Computing)
In mathematics, Pontryagin duality is a duality between locally compact abelian groups that allows generalizing Fourier transform to all such groups, which include the circle group (the multiplicative group of complex numbers of modulus one), the finite abelian groups (with the discrete topology), and the additive group of the integers (also with the discrete topology), the real numbers, and every finite dimensional vector space over the reals or a -adic field. The Pontryagin dual of a locally compact abelian group is the locally compact abelian topological group formed by the continuous group homomorphisms from the group to the circle group with the operation of pointwise multiplication and the topology of uniform convergence on compact sets. The Pontryagin duality theorem establishes Pontryagin duality by stating that any locally compact abelian group is naturally isomorphic with its bidual (the dual of its dual). The Fourier inversion theorem is a special case of this theor ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Leonard Schulman
Leonard J. Y. Schulman (born September 14, 1963) is professor of computer science in the Computing and Mathematical Sciences Department at the California Institute of Technology. He is known for work on algorithms, information theory, coding theory, and quantum computation. Personal biography Schulman is the son of theoretical physicist Lawrence Schulman. Academic biography Schulman studied at the Massachusetts Institute of Technology, where he completed a BS degree in mathematics in 1988 and a PhD degree in applied mathematics in 1992. He was a faculty member in the College of Computing at the Georgia Institute of Technology from 1995 to 2000 before joining the faculty of the California Institute of Technology. From 2003-2017, he served as the director of the Center for Mathematics of Information at Caltech. He also participates in the Institute for Quantum Information and Matter. In 2017-2018, he was a EURIAS Senior Fellow at the Israel Institute for Advanced Studies at the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Quantum Fourier Transform
In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's algorithm for factoring and computing the discrete logarithm, the quantum phase estimation algorithm for estimating the eigenvalues of a unitary operator, and algorithms for the hidden subgroup problem. The quantum Fourier transform was discovered by Don Coppersmith. The quantum Fourier transform can be performed efficiently on a quantum computer with a decomposition into the product of simpler unitary matrices. The discrete Fourier transform on 2^n amplitudes can be implemented as a quantum circuit consisting of only O(n^2) Hadamard gates and controlled phase shift gates, where n is the number of qubits. This can be compared with the classical discrete Fourier transform, which takes O(n2^n) gates (where n is the number of bits), whi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Abelian Group
In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commutative. With addition as an operation, the integers and the real numbers form abelian groups, and the concept of an abelian group may be viewed as a generalization of these examples. Abelian groups are named after early 19th century mathematician Niels Henrik Abel. The concept of an abelian group underlies many fundamental algebraic structures, such as fields, rings, vector spaces, and algebras. The theory of abelian groups is generally simpler than that of their non-abelian counterparts, and finite abelian groups are very well understood and fully classified. Definition An abelian group is a set A, together with an operation \cdot that combines any two elements a and b of A to form another element of A, denoted a \cdot b. The symbo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 (or non-quantum) algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement. 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 fa ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Dihedral Group
In mathematics, a dihedral group is the group of symmetries of a regular polygon, which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry. The notation for the dihedral group differs in geometry and abstract algebra. In geometry, or refers to the symmetries of the -gon, a group of order . In abstract algebra, refers to this same dihedral group. This article uses the geometric convention, . Definition Elements A regular polygon with n sides has 2n different symmetries: n rotational symmetries and n reflection symmetries. Usually, we take n \ge 3 here. The associated rotations and reflections make up the dihedral group \mathrm_n. If n is odd, each axis of symmetry connects the midpoint of one side to the opposite vertex. If n is even, there are n/2 axes of symmetry connecting the midpoints of opposite sides and n/2 axes of symmetry connecting oppo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Symmetric Group
In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \mathrm_n defined over a finite set of n symbols consists of the permutations that can be performed on the n symbols. Since there are n! (n factorial) such permutation operations, the order (number of elements) of the symmetric group \mathrm_n is n!. Although symmetric groups can be defined on infinite sets, this article focuses on the finite symmetric groups: their applications, their elements, their conjugacy classes, a finite presentation, their subgroups, their automorphism groups, and their representation theory. For the remainder of this article, "symmetric group" will mean a symmetric group on a finite set. The symmetric group is important to diverse areas of mathematics such as Galois theory, invariant theory, the representatio ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Isomorphism Problem
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational complexity class NP-intermediate. It is known that the graph isomorphism problem is in the low hierarchy of class NP, which implies that it is not NP-complete unless the polynomial time hierarchy collapses to its second level. At the same time, isomorphism for many special classes of graphs can be solved in polynomial time, and in practice graph isomorphism can often be solved efficiently. This problem is a special case of the subgraph isomorphism problem, which asks whether a given graph ''G'' contains a subgraph that is isomorphic to another given graph ''H''; this problem is known to be NP-complete. It is also known to be a special case of the non-abelian hidden subgroup problem over the symmetric group. In the area of image recognition ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Non-abelian Group
In mathematics, and specifically in group theory, a non-abelian group, sometimes called a non-commutative group, is a group (''G'', ∗) in which there exists at least one pair of elements ''a'' and ''b'' of ''G'', such that ''a'' ∗ ''b'' ≠ ''b'' ∗ ''a''. This class of groups contrasts with the abelian groups. (In an abelian group, all pairs of group elements commute). Non-abelian groups are pervasive in mathematics and physics. One of the simplest examples of a non-abelian group is the dihedral group of order 6. It is the smallest finite non-abelian group. A common example from physics is the rotation group SO(3) in three dimensions (for example, rotating something 90 degrees along one axis and then 90 degrees along a different axis is not the same as doing them in reverse order). Both discrete groups and continuous groups may be non-abelian. Most of the interesting Lie groups are non-abelian, and these play an important role in gauge theory. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.jpg "Click for more on -> Quantum Computer")
