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:2310.07428 · MATRIX book series

Quantum counting, and a relevant sign

Natalie Chung, Rafael I. Nepomechie

Published Jan 1, 2026• 0 citations
arXivHTMLPDF
DOI
10.1007/978-3-032-16206-9_3

Related papers

The implementation of the enhanced quantum floating-point adder

Shantao Zhao, Hai-Sheng Li, Guiqiong Li +1 more

The quantum adder is a vital arithmetic operation for quantum algorithms. However, the existing quantum floating-point adders only considered the case of two normal numbers. In this paper, we propose an enhanced quantum floating-point adder based on IEEE 754 standard. First, we divide quantum floating-point adders into four cases: the normal case, subnormal case, mixed case, and special case. Then, we propose a result-sign and mantissa-sign determining unit to avoid conversion from sign-magnitude to two complements. Moreover, we design a new quantum leading zero detector with the optimized T-depth and T-count. Comparison results reveal that the proposed floating-point adder has lower circuit width, T-depth, and T-count than the current works.

Modern Physics Letters A•Aug 30, 2022•3 citations

Quantum counting

Gilles Brassard, Peter Høyer, Alain Tapp

arXiv:quant-ph/9805082•Lecture notes in computer science•Jan 1, 1998•421 citations

Quantum Numbers and Rules

Paul Peter Urone, Roger A. Hinrichs

•Jan 1, 2012•0 citations

A Perfectly Distributable Quantum-Classical Algorithm for Estimating Triangular Balance in a Signed Edge Stream

Steven Kordonowy, Bibhas Adhikari, Hannes Leipold

We develop a perfectly distributable quantum-classical streaming algorithm that processes signed edges to efficiently estimate the counts of triangles of diverse signed configurations in the single pass edge stream. Our approach introduces a quantum sketch register for processing the signed edge stream, together with measurement operators for query-pair calls in the quantum estimator, while a complementary classical estimator accounts for triangles not captured by the quantum procedure. This hybrid design yields a polynomial space advantage over purely classical approaches, extending known results from unsigned edge stream data to the signed setting. We quantify the lack of balance on random signed graph instances, showcasing how the classical and hybrid algorithms estimate balance in practice.

quant-pharXiv:2603.16029•Mar 18, 2026•1 citation

Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions

Anindya De, Ilias Diakonikolas, Rocco A. Servedio

Let g : {-1, 1}k→ {-1, 1} be any Boolean function and q1, . . . , qkbe any degree-2 polynomials over {-1, 1}n. We give a deterministic algorithm which, given as input explicit descriptions of g, q1, . . ., qkand an accuracy parameter ϵ > 0, approximates Prx~{-1, 1}n[g(sign(q1(x)), . . . , sign(qk(x))) = 1] to within an additive ±ϵ. For any constant ϵ > 0 and k ≥ 1 the running time of our algorithm is a fixed polynomial in n (in fact this is true even for some not-too-small ϵ = 0n(1) and not-too-large k = ωn(1)). This is the first fixed polynomial-time algorithm that can deterministically approximately count satisfying assignments of a natural class of depth-3 Boolean circuits. Our algorithm extends a recent result [1] which gave a deterministic approximate counting algorithm for a single degree-2 polynomial threshold function sign(q(x)), corresponding to the k = 1 case of our result. Note that even in the k = 1 case it is NP-hard to determine whether Prx~{-1, 1}n[sign(q(x)) = 1] is nonzero, so any sort of multiplicative approximation is almost certainly impossible even for efficient randomized algorithms. Our algorithm and analysis requires several novel technical ingredients that go significantly beyond the tools required to handle the k = 1 case in [1]. One of these is a new multidimensional central limit theorem for degree-2 polynomials in Gaussian random variables which builds on recent Malliavin-calculus-based results from probability theory. We use this CLT as the basis of a new decomposition technique for k-tuples of degree-2 Gaussian polynomials and thus obtain an efficient deterministic approximate counting algorithm for the Gaussian distribution, i.e., an algorithm for estimating Prx~N(0, 1)n[g(sign(q1(x)), . . . , sign(qk(x))) = 1]. Finally, a third new ingredient is a “regularity lemma” for k-tuples of degree-d polynomial threshold functions. This generalizes both the regularity lemmas of [2], [3] (which apply to a single degree-d polynomial threshold function) and the regularity lemma of Gopalan et al [4] (which applies to a k-tuples of linear threshold functions, i.e., the case d = 1). Our new regularity lemma lets us extend our deterministic approximate counting results from the Gaussian to the Boolean domain.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2014•7 citations

TOWARD A SET OF THE QUANTUM NUMBERS

Alexey Orlovsky

•Aug 10, 2026•0 citations
The quantum adder is a vital arithmetic operation for quantum algorithms. However, the existing quantum floating-point adders only considered the case of two normal numbers. In this paper, we propose an enhanced quantum floating-point adder based on IEEE 754 standard. First, we divide quantum floating-point adders into four cases: the normal case, subnormal case, mixed case, and special case. Then, we propose a result-sign and mantissa-sign determining unit to avoid conversion from sign-magnitude to two complements. Moreover, we design a new quantum leading zero detector with the optimized T-depth and T-count. Comparison results reveal that the proposed floating-point adder has lower circuit width, T-depth, and T-count than the current works.
We develop a perfectly distributable quantum-classical streaming algorithm that processes signed edges to efficiently estimate the counts of triangles of diverse signed configurations in the single pass edge stream. Our approach introduces a quantum sketch register for processing the signed edge stream, together with measurement operators for query-pair calls in the quantum estimator, while a complementary classical estimator accounts for triangles not captured by the quantum procedure. This hybrid design yields a polynomial space advantage over purely classical approaches, extending known results from unsigned edge stream data to the signed setting. We quantify the lack of balance on random signed graph instances, showcasing how the classical and hybrid algorithms estimate balance in practice.
Let g : {-1, 1}k→ {-1, 1} be any Boolean function and q1, . . . , qkbe any degree-2 polynomials over {-1, 1}n. We give a deterministic algorithm which, given as input explicit descriptions of g, q1, . . ., qkand an accuracy parameter ϵ > 0, approximates Prx~{-1, 1}n[g(sign(q1(x)), . . . , sign(qk(x))) = 1] to within an additive ±ϵ. For any constant ϵ > 0 and k ≥ 1 the running time of our algorithm is a fixed polynomial in n (in fact this is true even for some not-too-small ϵ = 0n(1) and not-too-large k = ωn(1)). This is the first fixed polynomial-time algorithm that can deterministically approximately count satisfying assignments of a natural class of depth-3 Boolean circuits. Our algorithm extends a recent result [1] which gave a deterministic approximate counting algorithm for a single degree-2 polynomial threshold function sign(q(x)), corresponding to the k = 1 case of our result. Note that even in the k = 1 case it is NP-hard to determine whether Prx~{-1, 1}n[sign(q(x)) = 1] is nonzero, so any sort of multiplicative approximation is almost certainly impossible even for efficient randomized algorithms. Our algorithm and analysis requires several novel technical ingredients that go significantly beyond the tools required to handle the k = 1 case in [1]. One of these is a new multidimensional central limit theorem for degree-2 polynomials in Gaussian random variables which builds on recent Malliavin-calculus-based results from probability theory. We use this CLT as the basis of a new decomposition technique for k-tuples of degree-2 Gaussian polynomials and thus obtain an efficient deterministic approximate counting algorithm for the Gaussian distribution, i.e., an algorithm for estimating Prx~N(0, 1)n[g(sign(q1(x)), . . . , sign(qk(x))) = 1]. Finally, a third new ingredient is a “regularity lemma” for k-tuples of degree-d polynomial threshold functions. This generalizes both the regularity lemmas of [2], [3] (which apply to a single degree-d polynomial threshold function) and the regularity lemma of Gopalan et al [4] (which applies to a k-tuples of linear threshold functions, i.e., the case d = 1). Our new regularity lemma lets us extend our deterministic approximate counting results from the Gaussian to the Boolean domain.