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

Lecture notes in computer science

Quantum Algorithms for Evaluating Min-Max Trees

Richard Cleve, Dmitry Gavinsky, David L. Yonge-Mallo

Published Jan 1, 2008• 10 citations
Publisher
DOI
10.1007/978-3-540-89304-2_2

Related papers

Quantum Algorithms for Evaluating MIN-MAX Trees

Richard Cleve, Gavinsky, Dmytro, David L. Yonge-Mallo

We present a bounded-error quantum algorithm for evaluating Min-Max trees. For a tree of size N our algorithm makes N^{1/2+o(1)} comparison queries, which is close to the optimal complexity for this problem.

arXiv:0710.5794•Oct 31, 2007•4 citations

Tree search and quantum computation

Luís Tarrataca, Andreas Wichert

arXiv:1502.01951•Quantum Information Processing•Nov 20, 2010•15 citations

Extractable Common Randomness From Gaussian Trees: Topological and Algebraic Perspectives

Ali Moharrer, Shuangqing Wei, George T. Amariucai +1 more

In this paper, we study both topological and algebraic properties of unrooted Gaussian trees in order to characterize their security performance. Such performance is measured by the corresponding potential in extracting common randomness from a given tree, which is further determined by max-min and min-max conditional mutual information (CMI) values, subject to the order of selecting variables from the tree by legitimate nodes Alice and Bob, and an eavesdropper Eve, respectively. A new operation is proposed to transform a Gaussian tree into another, and also to order different Gaussian trees. Through such operation we construct several equivalent classes of Gaussian trees. Each class includes multiple Gaussian trees that can be partially ordered based on the associated max-min or min-max CMI metric, and thus, we can find the most secure and the least secure trees in each partially ordered set (poset). The union of all posets generates all possible non-isomorphic trees of the given number of variables. Then, we assign a particular polynomial to each Gaussian tree, and show that such polynomial can determine the relative security performance of the Gaussian tree with respect to other trees within the same class. In the end, based on a generalized integer partition method, we propose a novel approach to efficiently enumerate the most secure structures of all posets.

IEEE Transactions on Information Forensics and Security•Mar 17, 2016•4 citations

Implementation of Classical Decision Trees in a Quantum Computing Paradigm

Manuel Pegalájar Cuéllar, L. G. B. Ruiz, M. C. Pegalajar

Lecture notes in computer science•Oct 8, 2024•2 citations

A Quantum Algorithm for Minimum Steiner Tree Problem

Masayuki Miyamoto, Masakazu Iwamura, Koichi Kise

•Apr 7, 2019•0 citations

Classifying Unrooted Gaussian Trees under Privacy Constraints

Ali Moharrer, Shuangqing Wei, George T. Amariucai +1 more

In this work, our objective is to find out how topological and algebraic properties of unrooted Gaussian tree models determine their security robustness, which is measured by our proposed max-min information (MaMI) metric. Such metric quantifies the amount of common randomness extractable through public discussion between two legitimate nodes under an eavesdropper attack. We show some general topological properties that the desired max-min solutions shall satisfy. Under such properties, we develop conditions under which comparable trees are put together to form partially ordered sets (posets). Each poset contains the most favorable structure as the poset leader, and the least favorable structure. Then, we compute the Tutte-like polynomial for each tree in a poset in order to assign a polynomial to any tree in a poset. Moreover, we propose a novel method, based on restricted integer partitions, to effectively enumerate all poset leaders. The results not only help us understand the security strength of different Gaussian trees, which is critical when we evaluate the information leakage issues for various jointly Gaussian distributed measurements in networks, but also provide us both an algebraic and a topological perspective in grasping some fundamental properties of such models.

arXiv:1504.02530•Apr 10, 2015•4 citations
In this paper, we study both topological and algebraic properties of unrooted Gaussian trees in order to characterize their security performance. Such performance is measured by the corresponding potential in extracting common randomness from a given tree, which is further determined by max-min and min-max conditional mutual information (CMI) values, subject to the order of selecting variables from the tree by legitimate nodes Alice and Bob, and an eavesdropper Eve, respectively. A new operation is proposed to transform a Gaussian tree into another, and also to order different Gaussian trees. Through such operation we construct several equivalent classes of Gaussian trees. Each class includes multiple Gaussian trees that can be partially ordered based on the associated max-min or min-max CMI metric, and thus, we can find the most secure and the least secure trees in each partially ordered set (poset). The union of all posets generates all possible non-isomorphic trees of the given number of variables. Then, we assign a particular polynomial to each Gaussian tree, and show that such polynomial can determine the relative security performance of the Gaussian tree with respect to other trees within the same class. In the end, based on a generalized integer partition method, we propose a novel approach to efficiently enumerate the most secure structures of all posets.
In this work, our objective is to find out how topological and algebraic properties of unrooted Gaussian tree models determine their security robustness, which is measured by our proposed max-min information (MaMI) metric. Such metric quantifies the amount of common randomness extractable through public discussion between two legitimate nodes under an eavesdropper attack. We show some general topological properties that the desired max-min solutions shall satisfy. Under such properties, we develop conditions under which comparable trees are put together to form partially ordered sets (posets). Each poset contains the most favorable structure as the poset leader, and the least favorable structure. Then, we compute the Tutte-like polynomial for each tree in a poset in order to assign a polynomial to any tree in a poset. Moreover, we propose a novel method, based on restricted integer partitions, to effectively enumerate all poset leaders. The results not only help us understand the security strength of different Gaussian trees, which is critical when we evaluate the information leakage issues for various jointly Gaussian distributed measurements in networks, but also provide us both an algebraic and a topological perspective in grasping some fundamental properties of such models.