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

2014/03/27 by Robert R. Tucci, Tucci, Robert R. · 1 citation
Computer Science · Physics and Astronomy · #Blind Source Separation Techniques #FOS: Physical sciences #Numerical Methods and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.1403.6910

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

arxiv created 2014/03/27 · openalex publication_date 2014/03/27 · arxiv updated 2014/03/28 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

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^-)∈ ℂ, where S^-⊂ \0,1,…,n-1\. The second is a marginal of a probability distribution P(yⁿ), where yⁿ∈ Boolⁿ. Known classical algorithms for calculating these Mobius-like transforms take \cal O(2ⁿ) steps. Our quantum algorithm is based on a Grover-like algorithm and it takes \cal O(√(2ⁿ)) steps.

Citations

• Code Generator for Quantum Simulated Annealing
• An Adaptive, Fixed-Point Version of Grover's Algorithm
• An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance

Cited by

• Quantum Circuit for Calculating Mean Values Via Grover-like Algorithm

Related

• Quantum Circuit for Calculating Mean Values Via Grover-like Algorithm
• Quantum Circuit for Calculating Symmetrized Functions Via Grover-like Algorithm
• Exact quantum Fourier transforms and discrete logarithm algorithms
• A presentation of the quantum Fourier transform from a recursive viewpoint
• A Polylogarithmic-Time Quantum Algorithm for the Laplace Transform