In this paper, we give quantum circuits for calculating two closely related linear transforms that we refer to jointly as Mobius-like transforms. The first is the Mobius transform of a function $f^{-}(S^-)\in \mathbb{C}$, where $S^-\subset \{0,1,\ldots,n-1\}$. The second is a marginal of a probability distribution $P(y^n)$, where $y^n\in Bool^n$. Known classical algorithms for calculating these Mobius-like transforms take ${\cal O}(2^n)$ steps. Our quantum algorithm is based on a Grover-like algorithm and it takes ${\cal O}(\sqrt{2^n})$ steps.
In this paper, we give quantum circuits for calculating two closely related linear transforms that we refer to jointly as Mobius-like transforms. The first is the Mobius transform of a function f−(S−)∈C, where S−⊂{0,1,…,n−1}. The second is a marginal of a probability distribution P(yn), where yn∈Booln. Known classical algorithms for calculating these Mobius-like transforms take O(2n) steps. Our quantum algorithm is based on a Grover-like algorithm and it takes O(2n) steps.
In this paper, we give a quantum circuit for calculating the mean value of a function A(xn)∈C, where xn∈{0,1}n. Known classical algorithms for calculating the mean value of a structureless function A(xn) take O(2n) steps. Our quantum algorithm is based on a Grover-like algorithm and it takes O(2n) steps. Our algorithm differs significantly from previously proposed quantum algorithms for calculating the mean value of a function via Grover's algorithm.
In this paper, we give a quantum circuit that calculates symmetrized functions. Our algorithm applies the original Grover's algorithm or a variant thereof such as AFGA (adaptive fixed point Grover's algorithm). Our algorithm uses AFGA in conjunction with two new techniques we call "targeting two hypotheses" and "blind targeting". Suppose AFGA drives the starting state ∣s⟩ to the target state ∣t⟩. When targeting two hypotheses, ∣t⟩ is a superposition a0∣0⟩+a1∣1⟩ of two orthonormal states or hypotheses ∣0⟩ and ∣1⟩. When targeting blindly, the value of ⟨t∣s⟩ is not known a priori.
We present a circuit design realizing Grover’s algorithm based on 1-bit unitary gates and 2-bit quantum phase gates implementable with cavity QED techniques. In the first step, we express the circuit block which performs a key unitary transformation that flips only the sign of the state |11 · · · 11〉 using 1-bit and 2-bit gates. The Grover’s iteration operator can then be constructed using this key unitary transformation twice, plus other operations involving only 1-bit unitary gates on each qubit. Mathematical proofs are given to justify that the cricuiting satisfies the desired operator properties.
Beyond-quadratic quantum speed-up is often based on an efficient transform between representations. We present a quantum algorithm to compute the Möbius spectrum of a pseudo-Boolean function. The algorithm produces a quantum state where the amplitude of each basis state is proportional to the Möbius coefficient of the corresponding index set. To achieve it, we implement the block encoding framework for the non-orthogonal Möbius transform. The algorithm runs in polynomial time with respect to the number of input bits and has many applications within function learning, image processing, and cryptography.
In this paper, we study decoherence in Grover's quantum searching algorithm using a perturbative method. We assume that each two-state system (qubit) suffers ${\ensuremath{\sigma}}_{z}$ error with probability p(0<p<1) independently at every step in the algorithm. Considering an n-qubit density operator to which Grover's operation is applied M times, we expand it in powers of 2Mnp and derive its matrix element order by order under the $\stackrel{\ensuremath{\rightarrow}}{n}\ensuremath{\infty}$ limit. (In this large-n limit, we assume p is small enough, so that 2Mnp(>0) can take any real positive value or 0.) This approach gives us an interpretation about creation of new modes caused by ${\ensuremath{\sigma}}_{z}$ error and an asymptotic form of an arbitrary-order correction. Calculating the matrix element up to the fifth-order term numerically, we investigate a region of 2Mnp (perturbative parameter), where the algorithm finds the correct item with a threshold of probability Pth or more. It satisfies $2Mnp<(8/5)(1\ensuremath{-}{P}_{\mathrm{th}})$ around $2Mnp\ensuremath{\simeq}0$ and ${P}_{\mathrm{th}}\ensuremath{\simeq}1,$ and this linear relation is applied to a wide range of Pth approximately. This observation is similar to a result obtained by Bernstein and Vazirani concerning accuracy of quantum gates for general algorithms. We cannot investigate a quantum-to-classical phase transition of the algorithm, because it is outside the reliable domain of our perturbation theory.
In this paper, we study decoherence in Grover's quantum search algorithm using a perturbative method. We assume that each two-state system (qubit) that belongs to a register suffers a phase-flip error (${\ensuremath{\sigma}}_{z}$ error) with probability p independently at every step in the algorithm, where $0\ensuremath{\leqslant}p\ensuremath{\leqslant}1$. Considering an n-qubit density operator to which Grover's iterative operation is applied M times, we expand it in powers of 2Mnp and derive its matrix element order by order under the large-n limit. [In this large-n limit, we assume p is small enough, so that 2Mnp can take any real positive value or zero. We regard $x\ensuremath{\equiv}2Mnp$ $(\ensuremath{\geqslant}0)$ as a perturbative parameter.] We obtain recurrence relations between terms in the perturbative expansion. By these relations, we compute higher orders of the perturbation efficiently, so that we extend the range of the perturbative parameter that provides a reliable analysis. Calculating the matrix element numerically by this method, we derive the maximum value of the perturbative parameter x at which the algorithm finds a correct item with a given threshold of probability Pth or more. (We refer to this maximum value of x as xc, a critical point of x.) We obtain a curve of xc as a function of Pth by repeating this numerical calculation for many points of Pth and find the following facts: a tangent of the obtained curve at Pth=1 is given by $x=(8∕5)(1\ensuremath{-}{P}_{\mathrm{th}})$, and we have ${x}_{\mathrm{c}}>\ensuremath{-}(8∕5){\mathrm{log}}_{e}\phantom{\rule{0.2em}{0ex}}{P}_{\mathrm{th}}$ near Pth=0.