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:2112.01666 · Quantum Information and Computation

Computing the quantumguesswork: a quadratic assignment problem

Michele Dall’Arno, Francesco Buscemi, Takeshi Koshiba

Published Jul 1, 2023• 3 citations
arXivHTMLPDF

Abstract

The quantum guesswork quantifies the minimum number of queries needed to guess the state of a quantum ensemble if one is allowed to query only one state at a time. Previous approaches to the computation of the guesswork were based on standard semi-definite programming techniques and therefore lead to approximated results. In contrast, we show that computing the quantum guesswork of qubit ensembles with uniform probability distribution corresponds to solving a quadratic assignment problem and we provide an algorithm that, upon the input of any qubit ensemble over a discrete ring, after finitely many steps outputs the exact closed-form expression of its guesswork. While in general the complexity of our guesswork-computing algorithm is factorial in the number of states, our main result consists of showing a more-than-quadratic speedup for symmetric ensembles, a scenario corresponding to the three-dimensional analog of the maximization version of the turbine-balancing problem. To find such symmetries, we provide an algorithm that, upon the input of any point set over a discrete ring, after finitely many steps outputs its exact symmetries. The complexity of our symmetries-finding algorithm is polynomial in the number of points. As examples, we compute the guesswork of regular and quasi-regular sets of qubit states.

DOI
10.26421/qic23.9-10-1

Related papers

Guesswork of a Quantum Ensemble

Michele Dall’Arno, Francesco Buscemi, Takeshi Koshiba

The guesswork of a quantum ensemble quantifies the minimum number of guesses needed in average to correctly guess the state of the ensemble, when only one state can be queried at a time. Here, we derive analytical solutions of the guesswork problem subject to a finite set of conditions, including the analytical solution for any qubit ensemble with uniform probability distribution. As explicit examples, we compute the guesswork for any qubit regular polygonal and polyhedral ensemble.

arXiv:2012.09350•IEEE Transactions on Information Theory•Jan 27, 2022•5 citations

On the Measurement Attaining the Quantum Guesswork

Michele Dall’Arno

The guesswork quantifies the minimum cost incurred in guessing the state of an ensemble, when only one state can be queried at a time. In the classical case, it is well known that the optimal strategy trivially consists of querying the states in their non-increasing order of posterior probability. In the quantum case, on the other hand, the most general strategy to obtain the optimal ordering in which to perform the queries consist of a quantum measurement. Here, we solve such an optimization problem by deriving the quantum measurement attaining the guesswork for a broad class of ensembles and cost functions.

arXiv:2302.06783•IEEE Transactions on Information Theory•Dec 15, 2023•1 citation

Guesswork with Quantum Side Information: Optimal Strategies and Aspects of Security

Eric P. Hanson, Vishal Katariya, Nilanjana Datta +1 more

What is the minimum number of guesses needed on average to correctly guess a realization of a random variable? The answer to this question led to the introduction of the notion of a quantity called guesswork by Massey in 1994, which can be viewed as an alternate security criterion to entropy. In this paper, we consider guesswork in the presence of quantum side information, and show that a general sequential guessing strategy is equivalent to performing a single quantum measurement and choosing a guessing strategy based on the outcome. We use this result to deduce entropic one-shot and asymptotic bounds on the guesswork in the presence of quantum side information, and to formulate a semi-definite program (SDP) to calculate the quantity. We evaluate the guesswork for a simple example involving the BB84 states, and we prove a continuity result that certifies the security of slightly imperfect key states when the guesswork is used as the security criterion.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•0 citations

Adversarial guesswork with quantum side information

Baasanchimed Avirmed, Kaito Niinomi, Michele Dall’Arno

The guesswork of a classical-quantum channel quantifies the cost incurred in guessing the state transmitted by the channel when only one state can be queried at a time, maximized over any classical pre-processing and minimized over any quantum post-processing. For arbitrary-dimensional covariant classical-quantum channels, we prove the invariance of the optimal pre-processing and the covariance of the optimal ost-processing. In the qubit case, we compute the optimal guesswork for the class of so-called highly symmetric informationally complete classical-quantum channels.

arXiv:2306.12633•Quantum Information and Computation•Nov 1, 2023•2 citations

Quantum Search Algorithm

Che‐Ming Li, Jin-Yuan Hsieh, Der-San Chuu

IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.

InTech eBooks•Apr 26, 2011•0 citations

Quantum algorithms and learning theory

Srinivasan Arunachalam

This thesis studies strengths and weaknesses of quantum computers. In the first part we present three contributions to quantum algorithms. 1) consider a search space of N elements. One of these elements is "marked" and our goal is to find this. We describe a quantum algorithm to solve this problem using essentially sqrt{N} queries and other operations, improving over the gate count of Grover's algorithm. 2) We give a succinct characterization of quantum algorithms in terms of polynomials, and develop a new technique for showing upper and lower bounds on quantum query complexity based on this. 3) One generic technique used to compute the minimum of a given function is "gradient descent". We present a quantum gradient-calculation algorithm and a gradient-optimization algorithm that is quadratically faster than classical algorithms. In the second part of this thesis we look at quantum learning theory. 1) We survey quantum learning theory, describing the main results known for three models of learning, using classical as well as quantum data: exact learning from membership queries, the probably approximately correct (PAC) learning model, and the agnostic learning model. 2) We then consider if a quantum learner can PAC-learn a given concept class from fewer quantum examples. We give a negative answer by showing that quantum examples are not more powerful than classical random examples, both for PAC learning and for agnostic learning.

•Apr 25, 2018•1 citation
The quantum guesswork quantifies the minimum number of queries needed to guess the state of a quantum ensemble if one is allowed to query only one state at a time. Previous approaches to the computation of the guesswork were based on standard semi-definite programming techniques and therefore lead to approximated results. In contrast, we show that computing the quantum guesswork of qubit ensembles with uniform probability distribution corresponds to solving a quadratic assignment problem and we provide an algorithm that, upon the input of any qubit ensemble over a discrete ring, after finitely many steps outputs the exact closed-form expression of its guesswork. While in general the complexity of our guesswork-computing algorithm is factorial in the number of states, our main result consists of showing a more-than-quadratic speedup for symmetric ensembles, a scenario corresponding to the three-dimensional analog of the maximization version of the turbine-balancing problem. To find such symmetries, we provide an algorithm that, upon the input of any point set over a discrete ring, after finitely many steps outputs its exact symmetries. The complexity of our symmetries-finding algorithm is polynomial in the number of points. As examples, we compute the guesswork of regular and quasi-regular sets of qubit states.
The guesswork quantifies the minimum cost incurred in guessing the state of an ensemble, when only one state can be queried at a time. In the classical case, it is well known that the optimal strategy trivially consists of querying the states in their non-increasing order of posterior probability. In the quantum case, on the other hand, the most general strategy to obtain the optimal ordering in which to perform the queries consist of a quantum measurement. Here, we solve such an optimization problem by deriving the quantum measurement attaining the guesswork for a broad class of ensembles and cost functions.
What is the minimum number of guesses needed on average to correctly guess a realization of a random variable? The answer to this question led to the introduction of the notion of a quantity called guesswork by Massey in 1994, which can be viewed as an alternate security criterion to entropy. In this paper, we consider guesswork in the presence of quantum side information, and show that a general sequential guessing strategy is equivalent to performing a single quantum measurement and choosing a guessing strategy based on the outcome. We use this result to deduce entropic one-shot and asymptotic bounds on the guesswork in the presence of quantum side information, and to formulate a semi-definite program (SDP) to calculate the quantity. We evaluate the guesswork for a simple example involving the BB84 states, and we prove a continuity result that certifies the security of slightly imperfect key states when the guesswork is used as the security criterion.
The guesswork of a classical-quantum channel quantifies the cost incurred in guessing the state transmitted by the channel when only one state can be queried at a time, maximized over any classical pre-processing and minimized over any quantum post-processing. For arbitrary-dimensional covariant classical-quantum channels, we prove the invariance of the optimal pre-processing and the covariance of the optimal ost-processing. In the qubit case, we compute the optimal guesswork for the class of so-called highly symmetric informationally complete classical-quantum channels.
IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.
This thesis studies strengths and weaknesses of quantum computers. In the first part we present three contributions to quantum algorithms. 1) consider a search space of N elements. One of these elements is "marked" and our goal is to find this. We describe a quantum algorithm to solve this problem using essentially sqrt{N} queries and other operations, improving over the gate count of Grover's algorithm. 2) We give a succinct characterization of quantum algorithms in terms of polynomials, and develop a new technique for showing upper and lower bounds on quantum query complexity based on this. 3) One generic technique used to compute the minimum of a given function is "gradient descent". We present a quantum gradient-calculation algorithm and a gradient-optimization algorithm that is quadratically faster than classical algorithms. In the second part of this thesis we look at quantum learning theory. 1) We survey quantum learning theory, describing the main results known for three models of learning, using classical as well as quantum data: exact learning from membership queries, the probably approximately correct (PAC) learning model, and the agnostic learning model. 2) We then consider if a quantum learner can PAC-learn a given concept class from fewer quantum examples. We give a negative answer by showing that quantum examples are not more powerful than classical random examples, both for PAC learning and for agnostic learning.