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

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,\dots ,n-1\}$. The second is a marginal of a probability distribution $P(y^n)$, where $y^n\in Boo{l}^n$. Known classical algorithms for calculating these Mobius-like transforms take $\mathcal{O}(2^n)$ steps. Our quantum algorithm is based on a Grover-like algorithm and it takes $\mathcal{O}(\sqrt{2^n})$ steps.

12 pages(4 files: 1 .tex, 1 .sty, 2 .eps)

References in corpus (7)

• Quantum Amplitude Amplification and Estimation
• Quantum computers can search rapidly by using almost any transformation
• A Quantum Algorithm for Finding the Minimum
• Code Generator for Quantum Simulated Annealing
• An Adaptive, Fixed-Point Version of Grover's Algorithm
• Computational Aspects of the Mobius Transform
• Quantum Circuit for Calculating Symmetrized Functions Via Grover-like Algorithm

Cited by in corpus (2)

• Quantum Circuit For Discovering from Data the Structure of Classical Bayesian Networks
• Quantum Circuit for Calculating Mean Values Via Grover-like Algorithm