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:1209.5932

Efficient quantum algorithm to construct arbitrary Dicke states

Kaushik Chakraborty, Byung-Soo Choi, Arpita Maitra, Subhamoy Maitra

Published Sep 26, 2012• 3 citations
arXivHTMLPDF

Abstract

In this paper, we study efficient algorithms towards the construction of any arbitrary Dicke state. Our contribution is to use proper symmetric Boolean functions that involve manipulations with Krawtchouk polynomials. Deutsch-Jozsa algorithm, Grover algorithm and the parity measurement technique are stitched together to devise the complete algorithm. Further, motivated by the work of Childs et al (2002), we explore how one can plug the biased Hadamard transformation in our strategy. Our work compares fairly with the results of Childs et al (2002).

DOI
10.48550/arxiv.1209.5932

Related papers

A dynamical algebra of protocol-induced transformations on Dicke states

Pierre-Antoine Bernard, Luc Vinet

Quantum [Formula: see text]-qubit states that are totally symmetric under the permutation of qubits are essential ingredients of important algorithms and applications in quantum information. Consequently, there is significant interest in developing methods to prepare and manipulate Dicke states, which form a basis for the subspace of fully symmetric states. Two simple protocols for transforming Dicke states are considered. An algebraic characterization of the operations that these protocols induce is obtained in terms of the Weyl algebra [Formula: see text] and [Formula: see text]. Fixed points under the application of the combination of both protocols are explicitly determined. Connections with the binary Hamming scheme, the Hadamard transform and Krawtchouk polynomials are highlighted.This article is part of the theme issue 'Numerical analysis, spectral graph theory, orthogonal polynomials and quantum algorithms'.

arXiv:2412.17917•Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences•Oct 9, 2025•2 citations

Quantum filtering of Boolean functions

János A. Bergou, Ulrike Herzog, Mark S. Hillery

We develop an efficient probabilistic quantum algorithm that can distinguish between sets of Boolean functions. The method is based on an exact solution to the quantum state filtering problem and can be considered to be an extension of the original Deutsch-Jozsa algorithm.

•Aug 31, 2002•0 citations

Implementing quantum algorithms using classical electrical circuits: Deutsch, Deutsch-Jozsa and Grover

Charles Dyson

We develop the means to implement Deutsch's algorithm, the Deutsch-Jozsa algorithm and Grover's algorithm using electronic circuits, and review previous attempts to implement quantum algorithms classically. We attempt to demonstrate that these are not fundamentally quantum algorithms, but merely algorithms that scale exceptionally well on quantum computers. Finally, we discuss a prototype design for an electrical Hadamard gate and report experimental results.

•Mar 1, 2011•4 citations

Improving Grover’s Algorithm with Dicke States

Jehn‐Ruey Jiang, Qiao-Yi Lin

This paper proposes using Dicke states to improve Grover’s quantum search algorithm for solving the k-vertex cover problem in a given graph with n vertices, a well-known NP-complete problem. A Dicke state $\left| {D_k^n} \right\rangle $ is a special entangled quantum state representing the symmetric superposition of all n-qubit states where exactly k qubits are in |1⟩. It is used to prepare the initial quantum state to reduce the quantum search space from 2nto C(n,k). Consequently, the operations required by Grover’s algorithm are reduced from ${\mathbf{O}}\left({\sqrt {{2^n}} }\right)$ to ${\mathbf{O}}(\sqrt {C(n,k)} )$, which is ${\mathbf{O}}\left({\sqrt {{n^k}} }\right)$ for 1 ≤ k ≪ n/2 or n − k ≪ n/2.

IEEE International Conference on Consumer Electronics - Taiwan (ICCE-Taiwan)•Jul 16, 2025•4 citations

Efficient Simulation of the Deutsch-Jozsa Algorithm

Niklas Johansson

We provide a framework wherein one can simulate the Deutsch-Jozsa quantum algorithm on a regular computer within polynomial time, and with linear memory consumption. Under certain reasonable assumptions the simulation solves the problem with a bounded error of probability with only one function evaluation, which is comparable with the efficiency of the quantum algorithm. The provided framework lies within a slight extension of the toy model purposed by Robert W. Spekkens Phys. Rev. A 75 (2007), and consists of transformations that are reminiscent of transformations in quantum mechanics.

•Jan 1, 2015•1 citation

Characterization of exact one-query quantum algorithms (ii): for partial functions

Zekun Ye, Lvzhou Li

The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity. Recently we have considered in (Phys. Rev. A. {\bf 101}, 02232 (2020)) the problem: what functions can be computed by an exact one-query quantum algorithm? This problem has been addressed for total Boolean functions but still open for partial Boolean functions. Thus, in this paper we continue to characterize the computational power of exact one-query quantum algorithms for partial Boolean functions by giving several necessary and sufficient conditions. By these conditions, we construct some new functions that can be computed exactly by one-query quantum algorithms but have essential difference from the already known ones. Note that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions, whereas the ones constructed in this papers are generally asymmetric.

arXiv:2008.11998•Aug 27, 2020•3 citations
In this paper, we study efficient algorithms towards the construction of any arbitrary Dicke state. Our contribution is to use proper symmetric Boolean functions that involve manipulations with Krawtchouk polynomials. Deutsch-Jozsa algorithm, Grover algorithm and the parity measurement technique are stitched together to devise the complete algorithm. Further, motivated by the work of Childs et al (2002), we explore how one can plug the biased Hadamard transformation in our strategy. Our work compares fairly with the results of Childs et al (2002).
Quantum [Formula: see text]-qubit states that are totally symmetric under the permutation of qubits are essential ingredients of important algorithms and applications in quantum information. Consequently, there is significant interest in developing methods to prepare and manipulate Dicke states, which form a basis for the subspace of fully symmetric states. Two simple protocols for transforming Dicke states are considered. An algebraic characterization of the operations that these protocols induce is obtained in terms of the Weyl algebra [Formula: see text] and [Formula: see text]. Fixed points under the application of the combination of both protocols are explicitly determined. Connections with the binary Hamming scheme, the Hadamard transform and Krawtchouk polynomials are highlighted.This article is part of the theme issue 'Numerical analysis, spectral graph theory, orthogonal polynomials and quantum algorithms'.
This paper proposes using Dicke states to improve Grover’s quantum search algorithm for solving the k-vertex cover problem in a given graph with n vertices, a well-known NP-complete problem. A Dicke state $\left| {D_k^n} \right\rangle $ is a special entangled quantum state representing the symmetric superposition of all n-qubit states where exactly k qubits are in |1⟩. It is used to prepare the initial quantum state to reduce the quantum search space from 2nto C(n,k). Consequently, the operations required by Grover’s algorithm are reduced from O(2n){\mathbf{O}}\left({\sqrt {{2^n}} }\right)O(2n​) to O(C(n,k)){\mathbf{O}}(\sqrt {C(n,k)} )O(C(n,k)​), which is O(nk){\mathbf{O}}\left({\sqrt {{n^k}} }\right)O(nk​) for 1 ≤ k ≪ n/2 or n − k ≪ n/2.
We provide a framework wherein one can simulate the Deutsch-Jozsa quantum algorithm on a regular computer within polynomial time, and with linear memory consumption. Under certain reasonable assumptions the simulation solves the problem with a bounded error of probability with only one function evaluation, which is comparable with the efficiency of the quantum algorithm. The provided framework lies within a slight extension of the toy model purposed by Robert W. Spekkens Phys. Rev. A 75 (2007), and consists of transformations that are reminiscent of transformations in quantum mechanics.
The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity. Recently we have considered in (Phys. Rev. A. {\bf 101}, 02232 (2020)) the problem: what functions can be computed by an exact one-query quantum algorithm? This problem has been addressed for total Boolean functions but still open for partial Boolean functions. Thus, in this paper we continue to characterize the computational power of exact one-query quantum algorithms for partial Boolean functions by giving several necessary and sufficient conditions. By these conditions, we construct some new functions that can be computed exactly by one-query quantum algorithms but have essential difference from the already known ones. Note that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions, whereas the ones constructed in this papers are generally asymmetric.