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.6707

Quantum Circuit for Calculating Symmetrized Functions Via Grover-like Algorithm

Robert R. Tucci

Published Mar 26, 2014• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1403.6707

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

An Adaptive, Fixed-Point Version of Grover's Algorithm

Robert R. Tucci

We give an adaptive, fixed-point version of Grover's algorithm. By this we mean that our algorithm performs an infinite sequence of gradually diminishing steps (so we say it's adaptive) that drives the starting state to the target state with absolute certainty (so we say it's a fixed-point algorithm). Our algorithm is motivated by Bloch sphere geometry. We include with the ArXiv distribution of this paper some simple software (Octave/Matlab m-files) that implements, tests and illustrates some of the results of this paper.

arXiv:1001.5200•Jan 28, 2010•6 citations

Generalization of Quantum Search Algorithm

Debasis Sadhukhan

Grover's quantum search algorithm is an important landmark discovery in the area of quantum computing that drives a quantum computer from a known initial state(source state) to an unknown final state(target state) by using selective phase inversions of these states. The algorithm is simply a successive iteration of the Grover's search operator, which is a product of selective inversion operators of source and target states. In its original form, Grover's operator performs the selective inversions only on a unique source state and a unique target state. In the generalized version, we make our search operator to perform selective inversions on more than one source and target states. First, we find that the case of selective inversions of two source and two target states can be easily analysed somewhat similar to the case of Grover's algorithm. But unlike Grover's operator, the selective inversions of three source and three target states is not so easy to study analytically and hence we perform numerical calculations on some specific cases. We find that these generalized search operators also give us a successful quantum search as expected.

•Feb 13, 2013•0 citations

A Circuit-Based Quantum Algorithm Driven by Transverse Fields for Grover's Problem

Jiang Zhang, Eleanor Gilbert Rieffel, Zhihui Wang

We designed a quantum search algorithm, giving the same quadratic speedup achieved by Grover's original algorithm; we replace Grover's diffusion operator (hard to implement) with a product diffusion operator generated by transverse fields (easy to implement). In our algorithm, the problem Hamiltonian (oracle) and the transverse fields are applied to the system alternatively. We construct such a sequence that the corresponding unitary generates a closed transition between the initial state (even superposition of all states) and a modified target state, which has a high degree of overlap with the original target state.

•Jan 1, 2017•0 citations

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

Robert R. Tucci

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.

arXiv:1403.6910•Mar 27, 2014•3 citations

Improving the mapping of reversible circuits to quantum circuits using multiple target lines

Robert Wille, Mathias Soeken, C. Otterstedt +1 more

The efficient synthesis of quantum circuits is an active research area. Since many of the known quantum algorithms include a large Boolean component (e.g. the database in the Grover search algorithm), quantum circuits are commonly synthesized in a two-stage approach. First, the desired function is realized as a reversible circuit making use of existing synthesis methods for this domain. Afterwards, each reversible gate is mapped to a functionally equivalent quantum gate cascade. In this paper, we propose an improved mapping of reversible circuits to quantum circuits which exploits a certain structure of many reversible circuits. In fact, it can be observed that reversible circuits are often composed of similar gates which only differ in the position of their target lines. We introduce an extension of reversible gates which allow multiple target lines in a single gate. This enables a significantly cheaper mapping to quantum circuits. Experiments show that considering multiple target lines leads to improvements of up to 85% in the resulting quantum cost.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 1, 2013•64 citations
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.
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.
We give an adaptive, fixed-point version of Grover's algorithm. By this we mean that our algorithm performs an infinite sequence of gradually diminishing steps (so we say it's adaptive) that drives the starting state to the target state with absolute certainty (so we say it's a fixed-point algorithm). Our algorithm is motivated by Bloch sphere geometry. We include with the ArXiv distribution of this paper some simple software (Octave/Matlab m-files) that implements, tests and illustrates some of the results of this paper.
Grover's quantum search algorithm is an important landmark discovery in the area of quantum computing that drives a quantum computer from a known initial state(source state) to an unknown final state(target state) by using selective phase inversions of these states. The algorithm is simply a successive iteration of the Grover's search operator, which is a product of selective inversion operators of source and target states. In its original form, Grover's operator performs the selective inversions only on a unique source state and a unique target state. In the generalized version, we make our search operator to perform selective inversions on more than one source and target states. First, we find that the case of selective inversions of two source and two target states can be easily analysed somewhat similar to the case of Grover's algorithm. But unlike Grover's operator, the selective inversions of three source and three target states is not so easy to study analytically and hence we perform numerical calculations on some specific cases. We find that these generalized search operators also give us a successful quantum search as expected.
We designed a quantum search algorithm, giving the same quadratic speedup achieved by Grover's original algorithm; we replace Grover's diffusion operator (hard to implement) with a product diffusion operator generated by transverse fields (easy to implement). In our algorithm, the problem Hamiltonian (oracle) and the transverse fields are applied to the system alternatively. We construct such a sequence that the corresponding unitary generates a closed transition between the initial state (even superposition of all states) and a modified target state, which has a high degree of overlap with the original target state.
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.
The efficient synthesis of quantum circuits is an active research area. Since many of the known quantum algorithms include a large Boolean component (e.g. the database in the Grover search algorithm), quantum circuits are commonly synthesized in a two-stage approach. First, the desired function is realized as a reversible circuit making use of existing synthesis methods for this domain. Afterwards, each reversible gate is mapped to a functionally equivalent quantum gate cascade. In this paper, we propose an improved mapping of reversible circuits to quantum circuits which exploits a certain structure of many reversible circuits. In fact, it can be observed that reversible circuits are often composed of similar gates which only differ in the position of their target lines. We introduce an extension of reversible gates which allow multiple target lines in a single gate. This enables a significantly cheaper mapping to quantum circuits. Experiments show that considering multiple target lines leads to improvements of up to 85% in the resulting quantum cost.