Polynomial-time quantum algorithms for finding the linear structures of Boolean function
| Autor: | Houzhen Wang, Shaowu Mao, Huanguo Zhang, Wanqing Wu |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Polynomial (hyperelastic model)
Statistical and Nonlinear Physics String (physics) Theoretical Computer Science Electronic Optical and Magnetic Materials Combinatorics Modeling and Simulation Quantum mechanics Signal Processing Quantum algorithm Electrical and Electronic Engineering Boolean function Hamming weight Quantum Time complexity Mathematics Quantum computer |
| Zdroj: | Quantum Information Processing. 14:1215-1226 |
| ISSN: | 1573-1332 1570-0755 |
| DOI: | 10.1007/s11128-015-0940-1 |
| Popis: | In this paper, we present quantum algorithms to solve the linear structures of Boolean functions. "Suppose Boolean function $$f$$f: $$\{0, 1\}^{n}\rightarrow \{0, 1\}$${0,1}n?{0,1} is given as a black box. There exists an unknown n-bit string $$\alpha $$? such that $$f(x)=f(x\oplus \alpha )$$f(x)=f(x??). We do not know the n-bit string $$\alpha $$?, excepting the Hamming weight $$W(\alpha )=m, 1\le m\le n$$W(?)=m,1≤m≤n. Find the string $$\alpha $$?." In case $$W(\alpha )=1$$W(?)=1, we present an efficient quantum algorithm to solve this linear construction for the general $$n$$n. In case $$W(\alpha )>1$$W(?)>1, we present an efficient quantum algorithm to solve it for most cases. So, we show that the problem can be "solved nearly" in quantum polynomial times $$O(n^{2})$$O(n2). From this view, the quantum algorithm is more efficient than any classical algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|