Hidden shift problem

Last updated June 27, 2024

In quantum computing, the hidden shift problem is a type of oracle-based problem. Various versions of this problem have quantum algorithms which can run much more quickly than known non-quantum methods for the same problem. In its general form, it is equivalent to the hidden subgroup problem for the dihedral group.^[1] It is a major open problem to understand how well quantum algorithms can perform for this task, as it can be applied to break lattice-based cryptography.^[2]^[3]

Problem statement

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$ .^[4]

Functions such as the Legendre symbol and bent functions, satisfy these constraints.^[5]

Algorithms

With a quantum algorithm that is defined as $|s\rangle =H^{\otimes n}O_{f}H^{\otimes n}O_{\hat {g}}H^{\otimes n}|0^{n}\rangle$ , where $H$ is the Hadamard gate and ${\hat {g}}$ is the Fourier transform of $g$ , certain instantiations of this problem can be solved in a polynomial number of queries to $O$ while taking exponential queries with a classical algorithm.

Related Research Articles

In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue to the complexity class BPP.

A quantum computer is a computer that exploits quantum mechanical phenomena. On small scales, physical matter exhibits properties of both particles and waves, and quantum computing leverages this behavior using specialized hardware. Classical physics cannot explain the operation of these quantum devices, and a scalable quantum computer could perform some calculations exponentially faster than any modern "classical" computer. In particular, a large-scale quantum computer could break widely used encryption schemes and aid physicists in performing physical simulations; however, the current state of the art is largely experimental and impractical, with several obstacles to useful applications.

Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical (non-quantum) algorithms. On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future. Another concern is that noise in quantum circuits may undermine results, requiring additional qubits for quantum error correction.

In quantum computing, Grover's algorithm, also known as the quantum search algorithm, is a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just $evaluations of the function, where is the size of the function's domain. It was devised by Lov Grover in 1996.$

In quantum computing, a quantum algorithm is an algorithm that 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 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 generally reserved for algorithms that seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.

In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate is a basic quantum circuit operating on a small number of qubits. Quantum logic gates are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.

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 algorithm for factoring in quantum computing is an instance of the hidden subgroup problem for finite abelian groups, while the other problems correspond to finite groups that are not abelian.

In quantum computing, a graph state is a special type of multi-qubit state that can be represented by a graph. Each qubit is represented by a vertex of the graph, and there is an edge between every interacting pair of qubits. In particular, they are a convenient way of representing certain types of entangled states.

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 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.

Quantum walks are quantum analogs of classical random walks. In contrast to the classical random walk, where the walker occupies definite states and the randomness arises due to stochastic transitions between states, in quantum walks randomness arises through (1) quantum superposition of states, (2) non-random, reversible unitary evolution and (3) collapse of the wave function due to state measurements.

<span class="mw-page-title-main">One-way quantum computer</span> Method of quantum computing

The one-way or measurement-based quantum computer (MBQC) is a method of quantum computing that first prepares an entangled resource state, usually a cluster state or graph state, then performs single qubit measurements on it. It is "one-way" because the resource state is destroyed by the measurements.

Adiabatic quantum computation (AQC) is a form of quantum computing which relies on the adiabatic theorem to perform calculations and is closely related to quantum annealing.

A quantum t-design is a probability distribution over either pure quantum states or unitary operators which can duplicate properties of the probability distribution over the Haar measure for polynomials of degree t or less. Specifically, the average of any polynomial function of degree t over the design is exactly the same as the average over Haar measure. Here the Haar measure is a uniform probability distribution over all quantum states or over all unitary operators. Quantum t-designs are so called because they are analogous to t-designs in classical statistics, which arose historically in connection with the problem of design of experiments. Two particularly important types of t-designs in quantum mechanics are projective and unitary t-designs.

Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical complexity classes.

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 Harrow–Hassidim–Lloyd algorithm or HHL algorithm is a quantum algorithm for numerically solving a system of linear equations, designed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations.

Quantum counting algorithm is a quantum algorithm for efficiently counting the number of solutions for a given search problem. The algorithm is based on the quantum phase estimation algorithm and on Grover's search algorithm.

The Bernstein–Vazirani algorithm, which solves the Bernstein–Vazirani problem, is a quantum algorithm invented by Ethan Bernstein and Umesh Vazirani in 1997. 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.

Feynman's algorithm is an algorithm that is used to simulate the operations of a quantum computer on a classical computer. It is based on the Path integral formulation of quantum mechanics, which was formulated by Richard Feynman.

In the context of quantum computing, the quantum walk search is a quantum algorithm for finding a marked node in a graph.

References

↑ Childs, Andrew M.; van Dam, Wim (2007), "Quantum algorithm for a generalized hidden shift problem", in Bansal, Nikhil; Pruhs, Kirk; Stein, Clifford (eds.), Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, SIAM, pp. 1225–1232, arXiv: quant-ph/0507190
↑ Lomont, Chris (November 4, 2004), The Hidden Subgroup Problem - Review and Open Problems, arXiv: quant-ph/0411037
↑ Regev, Oded (January 2004). "Quantum Computation and Lattice Problems". SIAM Journal on Computing. 33 (3): 738–760. doi:10.1137/S0097539703440678. ISSN 0097-5397.
↑ Dam, Wim van; Hallgren, Sean; Ip, Lawrence (2002). "Quantum Algorithms for some Hidden Shift Problems". SIAM Journal on Computing . 36 (3): 763–778. arXiv: quant-ph/0211140 . doi:10.1137/S009753970343141X. S2CID 11122780.
↑ Rötteler, Martin (2008). "Quantum algorithms for highly non-linear Boolean functions". Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Vol. 402. Society for Industrial and Applied Mathematics. pp. 448–457. arXiv: 0811.3208 . doi:10.1137/1.9781611973075.37. ISBN 978-0-89871-701-3. S2CID 9615826.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[CvD05-1] Childs, Andrew M.; van Dam, Wim (2007), "Quantum algorithm for a generalized hidden shift problem", in Bansal, Nikhil; Pruhs, Kirk; Stein, Clifford (eds.), Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, SIAM, pp. 1225–1232, arXiv: quant-ph/0507190

[2] Lomont, Chris (November 4, 2004), The Hidden Subgroup Problem - Review and Open Problems, arXiv: quant-ph/0411037

[3] Regev, Oded (January 2004). "Quantum Computation and Lattice Problems". SIAM Journal on Computing. 33 (3): 738–760. doi:10.1137/S0097539703440678. ISSN 0097-5397.

[WH02-4] Dam, Wim van; Hallgren, Sean; Ip, Lawrence (2002). "Quantum Algorithms for some Hidden Shift Problems". SIAM Journal on Computing . 36 (3): 763–778. arXiv: quant-ph/0211140 . doi:10.1137/S009753970343141X. S2CID 11122780.

[5] Rötteler, Martin (2008). "Quantum algorithms for highly non-linear Boolean functions". Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Vol. 402. Society for Industrial and Applied Mathematics. pp. 448–457. arXiv: 0811.3208 . doi:10.1137/1.9781611973075.37. ISBN 978-0-89871-701-3. S2CID 9615826.

[1]

[2]

[3]

[4]

[5]

Hidden shift problem

Contents

Problem statement

Algorithms

Related Research Articles

References