Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1403.6910

Quantum Circuit for Calculating Mobius-like Transforms Via Grover-like Algorithm

Robert R. Tucci

Published Mar 27, 2014• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1403.6910

Related papers

Quantum Circuit for Calculating Mean Values Via Grover-like Algorithm

Robert R. Tucci

In this paper, we give a quantum circuit for calculating the mean value of a function $A(x^n)\in \mathbb{C}$, where $x^n\in \{0,1\}^n$. Known classical algorithms for calculating the mean value of a structureless function $A(x^n)$ 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. Our algorithm differs significantly from previously proposed quantum algorithms for calculating the mean value of a function via Grover's algorithm.

arXiv:1404.0668•Mar 31, 2014•3 citations

Quantum Circuit for Calculating Symmetrized Functions Via Grover-like Algorithm

Robert R. Tucci

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\rangle$ to the target state $|t\rangle$. When targeting two hypotheses, $|t\rangle$ is a superposition $a_0|0\rangle + a_1|1\rangle$ of two orthonormal states or hypotheses $|0\rangle$ and $|1\rangle$. When targeting blindly, the value of $\langle t| s\rangle$ is not known a priori.

arXiv:1403.6707•Mar 26, 2014•3 citations

A Quantum Circuit Design for Grover’s Algorithm

Zijian Diao, Muhammad Suhail Zubairy, Goong Chen

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.

Zeitschrift für Naturforschung A•Aug 1, 2002•23 citations

Quantum Möbius Transform via Block Encoding

Cezary Pilaszewicz

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.

IEEE Conference on Artificial Intelligence (CAI)•May 8, 2026•0 citations

Decoherence in Grover’s quantum algorithm: Perturbative approach

Hiroo Azuma

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 ${P}_{\mathrm{th}}$ 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 ${P}_{\mathrm{th}}$ 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.

arXiv:quant-ph/0110101•Physical Review A•Apr 1, 2002•27 citations

Higher-order perturbation theory for decoherence in Grover’s algorithm

Hiroo Azuma

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 ${P}_{\mathrm{th}}$ or more. (We refer to this maximum value of $x$ as ${x}_{\mathrm{c}}$, a critical point of $x$.) We obtain a curve of ${x}_{\mathrm{c}}$ as a function of ${P}_{\mathrm{th}}$ by repeating this numerical calculation for many points of ${P}_{\mathrm{th}}$ and find the following facts: a tangent of the obtained curve at ${P}_{\mathrm{th}}=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 ${P}_{\mathrm{th}}=0$.

arXiv:quant-ph/0504033•Physical Review A•Oct 4, 2005•8 citations
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−)∈Cf^{-}(S^-)\in \mathbb{C}f−(S−)∈C, where S−⊂{0,1,…,n−1}S^-\subset \{0,1,\ldots,n-1\}S−⊂{0,1,…,n−1}. The second is a marginal of a probability distribution P(yn)P(y^n)P(yn), where yn∈Boolny^n\in Bool^nyn∈Booln. Known classical algorithms for calculating these Mobius-like transforms take O(2n){\cal O}(2^n)O(2n) steps. Our quantum algorithm is based on a Grover-like algorithm and it takes O(2n){\cal O}(\sqrt{2^n})O(2n​) steps.
In this paper, we give a quantum circuit for calculating the mean value of a function A(xn)∈CA(x^n)\in \mathbb{C}A(xn)∈C, where xn∈{0,1}nx^n\in \{0,1\}^nxn∈{0,1}n. Known classical algorithms for calculating the mean value of a structureless function A(xn)A(x^n)A(xn) take O(2n){\cal O}(2^n)O(2n) steps. Our quantum algorithm is based on a Grover-like algorithm and it takes O(2n){\cal O}(\sqrt{2^n})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⟩|s\rangle∣s⟩ to the target state ∣t⟩|t\rangle∣t⟩. When targeting two hypotheses, ∣t⟩|t\rangle∣t⟩ is a superposition a0∣0⟩+a1∣1⟩a_0|0\rangle + a_1|1\ranglea0​∣0⟩+a1​∣1⟩ of two orthonormal states or hypotheses ∣0⟩|0\rangle∣0⟩ and ∣1⟩|1\rangle∣1⟩. When targeting blindly, the value of ⟨t∣s⟩\langle t| s\rangle⟨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)p(0<~p<~1)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 2Mnp2Mnp2Mnp 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)2Mnp(>~0)2Mnp(> 0) can take any real positive value or 0.)0.)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 2Mnp2Mnp2Mnp (perturbative parameter), where the algorithm finds the correct item with a threshold of probability Pth{P}_{\mathrm{th}}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{P}_{\mathrm{th}}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 ppp independently at every step in the algorithm, where $0\ensuremath{\leqslant}p\ensuremath{\leqslant}1$. Considering an nnn-qubit density operator to which Grover's iterative operation is applied MMM times, we expand it in powers of 2Mnp2Mnp2Mnp and derive its matrix element order by order under the large-nnn limit. [In this large-nnn limit, we assume ppp is small enough, so that 2Mnp2Mnp2Mnp 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 xxx at which the algorithm finds a correct item with a given threshold of probability Pth{P}_{\mathrm{th}}Pth​ or more. (We refer to this maximum value of xxx as xc{x}_{\mathrm{c}}xc​, a critical point of xxx.) We obtain a curve of xc{x}_{\mathrm{c}}xc​ as a function of Pth{P}_{\mathrm{th}}Pth​ by repeating this numerical calculation for many points of Pth{P}_{\mathrm{th}}Pth​ and find the following facts: a tangent of the obtained curve at Pth=1{P}_{\mathrm{th}}=1Pth​=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{P}_{\mathrm{th}}=0Pth​=0.