Purest Quantum State Identification
Authors: Yingqi Yu
Honglin Chen
Jun Wu
Wei Xie
Xiangyang Li
Venue: NeurIPS 2025 poster ()
Keywords: quantum property learning
best arm identification
online learning
Primary area: theory
TL;DR: Identify the purest quantum state among $K$ unknown $n$-qubit quantum states using total $N$ quantum state copies.

Abstract: Quantum noise constitutes a fundamental obstacle to realizing practical quantum technologies. To address the pivotal challenge of identifying quantum systems least affected by noise, we introduce the purest quantum state identification, which can be used to improve the accuracy of quantum computation and communication. We formulate a rigorous paradigm for identifying the purest quantum state among $K$ unknown $n$-qubit quantum states using total $N$ quantum state copies. For incoherent strategies, we derive the first adaptive algorithm achieving error probability $\exp\left(- \Omega\left(\frac{N H_1}{\log(K) 2^n }\right) \right)$, fundamentally improving quantum property learning through measurement optimization. By developing a coherent measurement protocol with error bound $\exp\left(- \Omega\left(\frac{N H_2}{\log(K) }\right) \right)$, we demonstrate a significant separation from incoherent strategies, formally quantifying the power of quantum memory and coherent measurement. Furthermore, we establish a lower bound by demonstrating that all strategies with fixed two-outcome incoherent POVM must suffer error probability exceeding $ \exp\left( - O\left(\frac{NH_1}{2^n}\right)\right)$. This research advances the characterization of quantum noise through efficient learning frameworks. Our results establish theoretical foundations for noise-adaptive quantum property learning while delivering practical protocols for enhancing the reliability of quantum hardware.

Purest Quantum State Identification
Yingqi Yu² Honglin Chen' Jun Wu Wei Xie Xiang-Yang Li "School of Computer Science and Technology, University of Science and Technology of China Heffi National Laboratory. University of Science and Technology of China (yingqiyu, ch1777, devilu) Smail. ustc. edu. cn {xxiews, xiangyangli edu, en
Abstract
Quantum noise constitutes a fundamental obstacle realizing practical quantum technologies. To address the pivotal challenge of identifying quantum systems least affected by noise, we introduce the purest quantum state identification. which can be used to improve the accuracy of quantum computation and communica- tion. We formulate rigorous paradigm for identifying the purest quantum state among K unknown n--ubit quantum states using total N quantum state copies. For incoherent strategies, we derive the first adaptive algorithm achieving error NH, (2
probability exp (-
fundamentally improving quantum property learning through measurement optimization. By developing a coherent measure-
ment protocol with error bound exp (-Q NHHa ) we demonstrate significant [og[K]]
separation from incoherent strategies, formally quantifying the power of quantum memory and coherent measurement. Furthermore, we establish lower bound by demonstrating that all strategies with fixed two-outcome incoherent POVM must suffer eтror probability exceeding exp (-0 ( This research advances the characterization quantum noise through efficient learning frameworks. Our results establish theoretical foundations for noise-adaptive quantum property learn- ing while delivering practical protocols for enhancing the reliability of quantum hardware.
Introduction
Quantum computing demonstrates the remarkable potential for solving computational problems that are intractable for classical systems [12). However, current quantum systems face two fundamental constraints that limit their practical applications: (1) the number of available quantum bits (qubits) in existing devices remains severely limited compared to theoretical requirements B and (2)
these qubits exhibit high sensitivity environmental noise, compromising the reliability of quantum operations [5]. These fundamental constraints impose substantial barriers to achieving reliable quantum control and measurement, prerequisites for unlocking practical quantum computational advantages. Owing to variations in device implementation and environmental factors, the performance of quantum computation and communication differs markedly among various quantum systems [6] Thus, identifying the optimal quantum device [5), quantum state, or quantum channel is significant for the near-term quantum science and technology.
To evaluate the quality of quantum systems, researchers often use the purity of quantum states as a criterion. quantum communication, high-accuracy quantum channels are critical to ensuring the accurate transmission of quantum information [7]. By measuring the purity of the channel's
"onresponding author *Conesponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

associated state (Choi-state 77), researchers can evaluate how noise affects the channel. On the other hand. preparing high-purity quantum states also the foundation for guantum algorithms. The majority of quantum algorithms rely on pure quantum states as inputs [ 8 9 Therefore, identifying high-purity quantum states is essential for accurate quantum computing.
In this paper, we study the problem of purest quantum state identification (PQSI). The learner aims identify the purest state among multiple unknown quantum states using copies across all states, This issue holds considerable importance from both theoretical and practical perspectives. By identifying the purest quantum state, it is achievable distinguish the best quantum system that is least affected by noise, thus improving the accuracy of quantum computing and quantum communication near-term quantum systems.
This paper makes the following key contributions:
Problem Model. To the best of our knowledge, this is the first study dedicated to the best quantum state identification, In this paper, we focus on the issue of the purest quantum state identification, i... identifying the purest quantum state from a set of available quantum states. In this problem, while allocating copies to different quantum systems, the learner also needs to select the basis for quantum measurement, which significantly increases its complexity. Due to the limited number of qubits in existing quantum devices, these systems may not be able to facilitate large-scale quantum measurement [10] [1]. Consequently, while coherent (multi-copy) measurement techniques can more efficiently acquire information about quantum states, research on incoherent (single-copy) measurement is practical. We formalize the problem of purest quantum state identification with incoherent (single-copy) measurement as follows:
Problem 1.1 (Purest quantum state identification (PQSI) with incoherent (single-oppy) measurement). There is set of K unknown n-qubit quantum states represented as S (p:.-..- .PK): The learner aims to identify the purest quantum state in S using a total of N copies across all states. The problem protocol round E {1,..., NN is as follows:
The learner chooses a quantum state at. from the set S and gets a copy of it.
The learner selects a POVM and uses it to measure after which de is destroyed.
Upon completing N measurements, the learner selects a quantum state p' S based the measurement outcomes. The objective of the learner is to maximize the probability of identifying the purest quantuu state, i.e., P(p' E arg maxpes Tr(p²)).
In general, when coherent measurements are available, we formalize the problem as follows:
Problem 1.2 (Purest quantum state identification (PQSI) with coherent (multi-copy) measurement). There a set of K unknown n-qubit quantum states represented as = (pi..... : .K ). The learner aims to identify the purest quantum state in S using total of N copies across all states. Let Ne denote the number of quantum state copies that remain available round t and N = =N When N, > O, the problem protocol at round E N+ is as follows:
The learner decides the number of copies of the quantum state P3 to acquire, denoted as s(i, L), where s(i, t) 2 and 1 < Σ i=1 sii, S N₁. The quantum state constructed from these copies can @e(1.))
be represented at P1 @
PK
@e(K()) Let Ne41 N₂ -EK s(i,t).
The learner selects an entangled POVM and uses it to measure ot, after which o, is destroyed.
Upon completing measurements of all N copies of quantum states, the learner selects a quantum state p' E based on the measurement outcomes. The objective of the learner is to maximize the probability of identifying the purest quantum state P(p arg max Tr(p²)).
Algorithms. We develop two distinct algorithms to address this problem in different settings. To simplify the expression, for E K). let P(x) be the i-th purest quantum state in S and ( Tr (pin) Tr (?)) be the purity gap between the optimal quantum state and the i-th purest quantum state. In scenarios where only single-copy measurements are available, we developed the incoherent measurement based algorithm IM-PQSI. We employ Haar unitary matrices to generate random measurement basis and to measure quantum states in S. This measurement approach allows us to evaluate the purity of quantum states by analyzing measurement expectations and variances. The Haar unitary matrices utilized in IM-PQSI belong to the class of unitary 4-designs,

---

which can be efficiently simulated on quantum computer up to inverse-exppe eveeseeexponentiaal trace distance
[6]. During the evaluation of quantum state purity, our algorithms dynamically allocate copies to various quantum states. By assigning more copies to states with higher purity, we enhance the estimation accuracy these states, thereby increasing the likelihood of identifying the purest quantum state. Furthermore, we improve the performance of the algorithm for identifying the optimal quantum state by balancing the selection of measurement basis with the number of measurements conducted for each base. The enror probability of this algorithm satisfies the following theorem:
12 T3 14 T5
Theorem 1.3 (Informal version of Theorem 4.1). There exists an algorithum that solves the problem of the purest quantum state identification with incoherent measurement whose enror probability satisfies
CN S exp (-12
NH
log( (2)
where H1 = min A
Conversely, when multi-copy measurements accessible, developed the coherent measurement based algorithm CM-PQSI. We use the SWAP test to estimate the purity of quantum states in this algorithm, and its error probability satisfies the following theorem:
Theorem 1.4 (Informal version of Theorem 6.1). There exists algorithm that solves the problem of the purest quantum state identification with coherent measurement whose error probability satisfies
CN S exp (-1
NH2
(og(K)) )):
A
where H2 (2...
By comparing the error probability upper bound of these two algorithms, we can identify the advantages of quantum memory.
Lower Bound. For incoherent measurements, we utilize the properties of Haar unitary matrices to formulate related problem named Purest Random Quantum State Identification (PRQSI). In this context, the learner is required consider specific quantum state distribution constructed from Haar unitary matrices. We demonstrate that the lower bound of the error probability for the PROSI problem is also applicable as the lower bound for the error probability of the POSI problem. Furthermore, we show that the measurement outcomes generated by three-fourths of the Haar unitary matrices are insufficient for the learner to easily diffcrentiate among them, presenting a challenge in identification. Additionally, we demonstrate that in any PROSI problem employing fixed two-outcome Positive Operator- Valued Measure, the mcasurement outcomes exhibit a Bernoulli distribution that is inherently difficult to distinguish. Consequently, we derive the lower bounds for the error probability of the PROSI, which are also the lower bounds for the error probability of the POSI problem, as follows:
Theorem 1.5 (Informal version of Theorem 5.6p. For any algorithm A to solve the purest quantum state identification using fixed 2-outcome randomly incoherent POVM, there exists a set of quantum states which makes the error probability of A satisfies
eN 2 exp (-0
NH 2n
))
(3)
where Hi min.e
A
2 Related Work
Quantum learning and testing. Quantum learning and testing [7 18 is a vital area of research
in quantum computing and quantum communication. Extensive investigations have been conducted to understand the complexities of various measurements. Quantum state tomography [99 20 21
22 involves obtaining complete information about the density matrix of quantum state through measurements. While this technique can employed to tackle the PQSI problem, incurs significant
sampling costs. For the quantum state certification 23 24 25 26), the target is to determine whether

---

quantum state is close to specific target quantum state. Our problem can be viewed as identifying the quantum state that is the farthest from the maximally mixed state. However, this problem focused on quantum testing and does not deal with distance estimation.
Hence, these methods are not applicable to the PQSI problem. Another category of problems relates to inner product estimation between two quantum states [27
When proving lower bounds, this category often significantly restricts the quantum states for distinction. The relevant literature employs two general approaches to establish problem complexity. The first approach However, the
28
29
30).
involves constructing counterexamples using Haar unitary matrices (2
26 23
representation-theon
structure of Haar unitary matrices is intricate B1, which makes it difficult to
use. The other approach uses Gaussian Orthogonal Ensemble matrices create counterexamples
24 21.
However, when using GOE to prove the lower bound, the distance between quantum states specific range rather than a fixed number, making unsuitable for the POSI problem.
Classical best arm identification. To the best of our knowledge, our work is the first consider the best quantum state identification. Among the classical learning tasks, the best arm identification 35 36) has been extensively studied and is divided into two categories: fixed budget and fixed confidence [88] However, the existing research can only deal with the problem under specific distributions. These limitations restrict the algorithm's 's applicability and leave considerable room for further research on this issue. In our problem, we must select an appropriate POVM basis while choosing the quantum state in each round. The quantum state space and the POVM space grow exponentially with the increase in qubits, which makes this problem significantly more challenging than solving a classical problem of the best arm identification.
32
33
34
37
Preliminaries and Notations
Quantum State. Let 2n denote the dimension of an n-qubit quantum system. An n-qubit quantum state can be represented by density matrix p E Cd which is Hermitian and trace- positive semi-definite.
particular, an n-qubit pure quantum state can represented by unit vector (15) E Cd. The purity of a quantum state p is Tr(p²).
Quantum Measurement. Quantum measurements are usually described by a Positive Operator- Valued Measure (POVM), which produces probabilistic outcomes. An n-qubit positive operator- valued measurement M can be represented as a collection of positive semi-defing {Mm)m. where Mn Cdxd and Σ Mm la- When using M to measure a quantum state P, the probability of outcome m is Tr(Mmp), and the quantum state / is destroyed. When the coherent measurement method is employed, the learner can perform entanglement measurements on quantum states #1 @ & Pm. However, this approach necessitates the support of large-scale quantum devices and quantum memory, which are not feasible with current quantum technologies. Therefore, researching incoherent measurement methods applicable to near-term quantum devices is of great significance.
matrices M =
In this study, we aim to identify the purest quantum state from a set of unknown quantum states, achieving the highest probability through N measurements. For the purpose of simplicity, will assume that there exists a unique optimal quantum state that is the purest in the set S, denoted as n²" 14. For A it, represent the purity difference between each non-optimal quantum state and the optimal quantum state using
A = Tr (pt.) Tr (p²).
F E {1,..., K), let P(a) be the i-th purest quantum state in S. then we have
Tr (pz-) = Tr ((n) > Tr (pēs) 2 TI (pix)).
and
A < A (3) S.. S A
Let en denote the probability that the learner does not choose the purest quantum state in S after N samples and measurements, i.e., eN = P (p/ & arg max, Tr(p2)). The learner's objective is to min ex. We summarize key notations used throughout this paper in Table] [

---

4 Algorithm for PQSI with incoherent measurement
The current era of quantum computing presents limitations in the number of available qubits. This may hinder the measurement of multiple quantum states operated jointly. In this section, we use incoherent (single-oppy) measurement methods each round select the purest quantum state from the set of quantum states.
The algorithm we designed solve the PQSI problem with incoherent measurements is shown in Algorithm [ In our algorithm, we utilize Haar-random unitary matrices to construct multiple random measurement bases for probing quantum state copies. For each constructed measurement basis, perform m repeated measurements on the same quantum state. Let the i-th measurement outcome be I; {O..... ......... ., 1} for d-outcome POVM. We estimate the quantum state's purity based on the empirical probability of obtaining identical outcomes, defined as
172
11a, - 2,,,
m
jæi
which corresponds to the well-known collision estimator E P. in classical statistics.
39 40
used to estimate the second moment
The rationale behind this choice is follows. The positive operator-valued measurements (POVMs) adopted in our algorithm have possible outcomes, where p; denotes the probability of observing the i-th outcome. The purity of a quantum state is closely related to the quantity Σ P. Hence, an essential step in our algorithm estimator provides natural and statistically efficient approach to this task, allowing us to connect the observed measurement coincidences to the underlying purity of the quantum state. By analyzing the expectation and variance of g. we can further quantify the probability of correctly identifying the purest quantum state within our framework.
estimate this second-order statistic accurately. The collision
Algorithm ! includes two random processes. The first process involves the random selection of Haar unitary matrices construct measurement bases. while the second process entails the random acquisition of measurement results using these bases. Balancing the estimation errors introduced by these two processes is crucial for enhancing the algorithm's accuracy. When the purity difference between quantum states is substantial, each measurement base requires fewer instances to distinguish purity differences among states effectively. Conversely, when the purity difference minimal, more measurements are necessary under a single measurement base to gather sufficient information, limiting the number of measurement bases that can be utilized. Furthermore, when the purity difference is extremely slight, the choice of measurement basis significantly influences the measurement outcomes. Performing ((d)) measurements under single measurement base essential for adequately differentiating the outcomes between quantum states. Additionally, increasing the number of measurements under one measurement base will not improve the accuracy of purity estimation. Given these considerations, we balance the number of measurement bases and the number of measurements per base to enhance the probability of identifying the optimal quantum state.
In Algorithm 1, we use Haar unitary matrices to construct random measurement bases. Haar unitary matrices are extensively employed in quantum property testing and learning theory [4] 27 30]. Achieving exact Haar randomness is challenging; therefore, unitary (-designs are typically used to approximate Haar unitary matrices. Haar unitary matrices used in Algorithm Caan approximated using unitary 4-designs. As established in [12), unitary I-designs can be efficiently implemented on quantum computers with exponentially minor approximation errors. This thcoretical foundation ensures the practical feasibility and mathematical validity of employing Haar unitary matrices in our algorithmic framework.
Then, we give the error probability upper bound of IM-PQSI in the following theorem.
1. Theorem 4.1. For i E {1,..., K).4 A, 2 c a2, where e is a constant. Set m = J2 in Algorithm
The error probability of Algorithm 7 satisfies
K(K K 1)
exp (-12
VENHi
<
(4)
2
log(K))
Am -
where H1 minnee2.....X)
5

---

Algorithm Incoherent measurement based algorithm for solving PQSI problem (IM-PQSI)
Input: Copy access S {pI, .... PK), sample number N.
Initialization: Set So {pI...., pk}. log(K) = 2/2 2 No = and Nx
N-K (og(K) K-1-k for l E (1.... - }}. Sample [N/m] random unitary matrix Ui,... ULN/mJ
according the Haar measure. for k=l.... K-1 do
for E Sk-1 and j E {L No-1 + 1, 1,...
No do Measure m copies of p in the basis
{0]1001U;)110 and set the outputs as
x(p, j. 1). ..., xp, m).
Let j) = 1 m² Lizo Ei 1(x(p.i))) = 031 +. end for
Let u (p,
Let Sp = Sk-1 arg min P w k)-
end for
Output the quantum state o' Sk-1.
Proof Sketch.
The expectation of w(p, k) and Tag in Algorithm I satisfies Efw(p, k)] = Elānss
() and the variance of ğ(p.j) satisfies Var(ō(p:3) = O (2 + m²d + mad
mld+1)
By Bernstein's inequality and the union bound of error probability, we have en S where H1 min An The proof details are provided Tog(K
K(K-1)
2 exp (-12 MeNHi
in Appendix B.2
When the purity gaps between quantum states are very small, the gap parameter Hi becomes correspondingly small, which naturally results in a looser error bound. This reflects the intrinsic difficulty of the problem: identifying the quantum state with the highest purity is fundamentally hard when multiple states have nearly identical purities. Moreover, the system dimension d 2n grows exponentially with the number of qubits n, so that z tends to zero n increases. Therefore, in Theorem 4.1
we assume that for any quantum state Sp. Tr(p*2) Tr(p²) c Zz If this assumption does not hold, we can instead derive the following conclusion:
Lemma 4.2. Set m = d in Algorithm
7 The probability of error of Algorithm 7 satisfies
K(K - 1)
exp (-12 min
NH2
NH₁
))
eN
(og(K)
log(K)d
(K){
(5)
Age and H₂ minig (2.....K)
A
where H1 (2...)
Appendix B.3 provides the proof details of Lemma 4.2
In the field of quantum learning and testing, research quantum channels constitutes critical aspect. Evaluating the impact of noise on quantum channels can significantly enhance the accuracy of quantum computing and quantum communication (7]. Introduced method for assessing the "unitarity" of quantum channel by evaluating the purity of a quantum state. Subsequently, we utilize the algorithm IM-PQSI to identify the most "unitary" quantum channel from quantum channel set. Let U(s denote the unitarity of the i-th most unitary quantum channel. We have the following corollary:
Corollary 4.3. There exists an algorithm that solves the problem of the most "unitary" channel identification with incoherent access whose error probability satisfies:
NN S exp (S2
NH log(K)2*) ))
(6)
where H. minie (2....
24(13 (13--M MG3)

---

5 Lower bound for PQSI with incoherent measurement
In this section, we investigate the lower bound on the error probability for solving the problem of purest quantum state identification. This problem requires distinguishing between quantum states with different purity through sampling and measurement. Recent studies [1]] indicated that when a quantum state p is rotated by Haar unitary matrix and measured N times, the output distribution can be calculated only if p is either a pure state or a maximally mixed state. Consequently, the complexity analysis of testing problems often assumes that one of the quantum states is either pure state maximally mixed state. This limitation presents significant challenges to our analysis.
To solve this problem, reduce the problem of identifying the purest quantum state to the problem of identifying the purest random quantum state. This reduction allows us to retain the problem's complexity while enabling us to analyze the complexity by considering only single problem instance.
Next, we demonstrate that for any POVM base M, there is set of unitary matrices U(M) satisfying that (1) Fu (U E U(M) = Q(1): and (2) when the quantum states rotated by these unitary matrices, they are difficult to distinguish by the POVM base M..
At last, we only consider all the possible POVM M and their corresponding of unitary matrix U(M). By analyzing the sampling distribution for specific POVM M and unitary matrix in U(M), we reduce the problem into classical problem for resolution and provide lower bound for the purest quantum state identification.
Similar to Definition 7 in 42 we analyze the lower bound of the error probability for any algorithm solving the purest quantum state identification problem using a 2-outcome randomly incoherent POVM to evaluate the task's difficulty.
Definition 5.1 (Randomly fixed incoherent two-outcome POVM). We say an algorithm A with randomly fixed incoherent two-outcome POVM, if it proceeds as the following: The algorithm A samples POVM M (Mo, Mi = la Mo} from a well-designed distribution of POVMs DM and performs the two-outcome single-copy POVM M on the copies of the quantum states.
5.1 Problem reduction
In this subsection, we aim to demonstrate that if there exists a set of random quantum states T(x) = {n (z),...... ... Tx [x)) which is difficult to identify the purest one in T, there also exists a corresponding set of quantum states S = ........ PK] } where is difficult to identify the purest one in S. In this way, we only need to construct K random quantum states, which are hard to distinguish. Then, we can demonstrate the difficulty of the purest quantum state identification problem.
To enhance our discussion, we define the problem of the purest random quantum state identifica- (ion(PRQSI) with incoherent measurement as follows:
Problem 5.2 (Purest random quantum state identification(PRQS) with incoherent measurement). Consider set of K unknown random quantum stutes, denote as T(U) (n
where samples from a fixed distribution D. For each k E [K] and U ~ D. (T(() = 2k- In each round I. E {1..... N). the learner selects index kt [K] and a POVM M.. The learner obtains a copy of Tk. (U) and uses Me to measure it. Upon completing N measurements, the learner selects index K' E [K] as the output. The objective of the learner is to maximize Pk E arg maxke]K] zx).
As shown in the following lemma, we can reduce the proof of the error probability lower bound for the PQSI problem into the proof of the lower bound for a specific instance of the PRQSI problem.
Lemma 5.3. If there exists a set of random quantum states T(U) in Problem 5.2 such that any algorithm Ar addressing Problem 5.2] cannot identify the purest random quantum state with an error probability lower than eN, then for any algorithm A addressing Problem I.I there exists a specific set of quantum states {pI...... .Kk such that the error probability of algorithm A is not lower than eN-
Proof Sketch. Suppose that there exists an algorithm A satisfying whose error probability for solving Problem is less than ex. We can prove that the algorithm A can solve the Problem 5.2 with
7

---

the error probability less than ex. Furthermore, we can establish the proof by considering the contrapositive of this statement. Detailed explanations of the proof are included in Appendix C.I
we will establish the lower bound of the error probability for the problem POSI by demonstrating the error probability lower bound for the following problem:
According to Lemma 5.3
Problem 5.4. Consider the Problem 5.2 For k E [K], let as
v
d= and The Tx(U)
d-1
(o)U + -- la, where Haar.
Then, In the Problem 5.4 for l E {1,... K} and U Haar, the purity of the quantum state (U) satisfies:
( -
(d- 1) )ax))
2 + (d-1)) (²a -0k d
2
Tr ((Tx(U)))
= 2k.
d
5.2 Random quantum state purity certification
To analyze Problem 5.4 we first study the properties of the measurement results obtained from conducting N' measurements on the sampled quantum states from the quantum state distribution D {plp (0 (ojut + 1-a Ia), using specific POVM M {Mo, M1], where U Haar and a is constant satisfying 0 v a S 1.
Lemma 5.5. Let a E [0, 1]. Using a specific POVM M = {Mo, M2} to measure the random quanium state in = {plp = at(1)) (0) + I la}. Let M = arg ( Tr(M'). We have
[pmMCMI)) - TH(M) -
2a V Tr(M)
3 2 4'
Po~
d
and there is a function c(M,U) satisfying (M(
Tr(M) c(M, U)a
Proof Sketch. By utilizing the properties of the Haar unitary matrix, we can calculate the variance of (MM and prove the probabilistic bounds in the lemma using Chebyshev's inequality, thus completing the proof. The proof details are provided in Appendix C.2 C.2
According to Lemma 5.5 for specific POVM .M and unitary matrix U, let UM denote the
set unitary matrix satisfying that UM = U PM((MU) Tr(M) TT(M)
We have
PU- (U E UM) 2 3.
The following analysis will focus on the unitary matrices in UM-
4-
5.3 Error probability lower bound
In this subsection, we will prove the lower bound of error probability for using algorithms solve Problem [I]]] and Problem 5.4
Let M arg (MoMM) Tr(M'), then we have Tr(M) do,d/ In the following theorem, let Tr(M) > 16 in order to make Tr(M) 2 TT(M) 2 1 (T(M
Theorem 5.6. Let M arg min ( (Ma TI(M') and Tr(M) > 16. For any algorithm A to solve the purest quantum state identification using fixed 2-outcome randomly incoherent POVM, there exists a set of quantum states which makes the error probability of A satisfies
eN 2 exp (-o
H
where H, minii (2.....KK)
Proof Sketch. Let (M,, U) denote the enror probability for algorithm A to solve the problem with specific unitary matrix U and POVM M. The error probability of to solve the problem 5.4 satisfying e 2 IMEDY Su PA UU UM}dMdU.
5.4
8

---

When the i-th quantum state is measured using M, the measurement result follows a Bernoulli distribution with parameter pu)) From Lemma 5.5 and the definition of c(M, U), have Tr(Mp:(U) = c(M, U)a; + TrM
If U) O, need to find the Bernoulli distribution with the largest parameter where the parameter of the i-th Bernoulli distribution is Tr(Mp;(U) and we have Tr(M p. (U) (T) dM.U)
[
/ d-
Since Tr(M) 16 and according to the definition of U(M) and M, for U U we have Tr(Mp:(U) [T((M) Tr(ad) and - Tr(M) 2d 2 2.2 Then, according to the problem of best arm identification problem with Bernoulli distribution, we can demonstrate that ye (U, M) > exp (-0 (N Then we have ex exp (-0 ( (1
2d
For any algorithm Ap addressing Problem 5.4
cannot i identify the purest random quantum state with
an probability lower than exp (-0 N21 )) According to Lemma 5.3 complete the
proof. The proof details are provided in Appendix C.3
POSI with coherent measurement
In this section, investigate the problem of purest quantum state identification with coherent measurement and propose an algorithm to solve the purest quantum state identification with coherent measurement based on the SWAP test.
The SWAP test a quantum algorithm designed to assess the similarity between two quantum states. It offers method for estimating these states' fidelity to quantify their closeness. We use the SWAP test in Figure D to estimate the purity of the quantum state p in the unknown quantum state set S. The measurement results in Figure have a probability of !+Tr("") for 0 and probability of l-Tx(p)) for 1. The details of the algorithm are shown in Algorithm
P
SWAP
10)
H
H
Figure 1: The SWAP test circuit.
Algorithm 2 Coherent measurement based algorithm for solving PQSI problem (CM-PQSI) {PI..... PK sample number N. pk), log(K) = + Σke 1 No = and N₂ "l,...,--- 111
Input: Copy access
Initialization: Set Su =
N-K for k E {l,.... K
K+1-k for 1,...,
2log(K)
do
For all 0 E S;-1, use SWAP test as Figure for N N6-1 rounds, and set the outputs as To,,N ;(o.
For all a E S let w(a k) = Σ N2
No. Ei F(a,a)-
Let S₁ S arg minpes--1 w(p,kt k).
end for
Output the quantum state p' St-1.
Theorem 6.1. The probability of error of Algorithm
satisfies
K(K -1)
NH₃ 8log K)
CN
exp
(8)
2

---

where H2 = min f (2....
Proof Sketch. The outputs of the SWAP test within the range [0, 1] and are independent. Thus, we can apply the Hoeffding inequality to complete the proof. Detailed explanations of the proof are included in Appendix D
To further clarify the role of coherent measurements, compare the theoretical performance of the proposed algorithms both with and without the SWAP test. The essential difference lies in the scaling behavior of the error probability bounds across different purity-gap regimes.
When the purity gaps satisfy (1) > 1/d", the lower bound for the algorithm without the SWAP test
CN exp -n
NH
))
where H1 min VE(2..... K}
log -2n
In contrast, the algorithm with the SWAP test (i.e., using coherent measurements) achieves
cN S exp -20 (- NH ( ))
A
where H₂ =
min xe (2...... K}
(10)
log
which eliminates the additional 2" factor in the denominator. This implies that the coherent- measurement-basee algorithm can attain the same error probability with only O(1/2") of the sample complexity, thereby demonstrating a substantial advantage in this regime.
When the purity gaps are very small (A(s) S 1/d2), both algorithms yield similar lower bounds of the form
eN S exp -Ω2 N log K
(11)
and thus exhibit comparable asymptotic performance. Nevertheless, even in this regime, the algorithm employing the SWAP test tends to achieve smaller constant factor in the exponent, resulting in empirically faster convergence and lower error rates for finite sample sizes. Therefore, the coherent measurement strategy remains effective in practice, providing improvements in both asymptotic and finite-sample efficiency.
In summary, the advantage of the SWAP test becomes particularly evident when the purity differences between quantum states are not vanishingly small. most realistic scenarios, such tiny gaps can be regarded negligible, and the corresponding states can be considered effectively equivalent. Consequently, for practical tasks that aim to distinguish states with noticeable purity differences, the coherent measurement strategy via the SWAP test offers clear improvement in sample effi- ciency. This observation also highlights the essential role of quantum memory in enabling coherent measurements.
7 Conclusion and Outlook
In this study, we propose pivotal problem in quantum testing, termed purest quantum state identifi- cation (PQSI). This framework applies to various quantum computing and quantum communication tasks. We develop two distinct algorithms to address this problem under different settings. When the learner utilizes incoherent (single-copy) measurement, the upper bound on the error probability of our algorithm is given by exp (-
N
When the learner is allowed use coherent
log(K]2 K)2"
(two-copy) measurement, the upper bound on the error probability given by exp (-2 (.2(.N NHH By examining the error probabilities of these two algorithms, we can discern the advantage of the coherent measurement over the incoherent one. Furthermore, we establish that for any algorithm utilizing a randomly fixed incoherent two-outcome POVM solve the PQSI, its error probability is lower bounded by exp (-0 ( (N )). Our results lay the groundwork for further investigations into the best quantum state identification. We aim to establish a lower bound for PQSI problems across all POVM bases in future work. Several open questions remain to be addressed, including identifying the nearest quantum state with minimal trace distance and achieving the best quantum state identification with fixed confidence.
(ogg(k)
10

---

8 Acknowledgement
This work was partially supported by Innovation Program for Quantum Science and Technology (Grant No. 20212D0302201), National Natural Science Foundation of China (Grant No. 62102388).
References
[1] Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124-134. leee, 1994.
[2] Andrew Daley, Immanuel Bloch, Christian Kokail, Stuart Flannigan, Natalie Pearson, Matthias Troyer, and Peter Zoller. Practical quantum advantage in quantum simulation. Nature, 607(7920)x67-676, 2022.
[3] Jonathan Wei Zhong Lau, Kian Hwee Lim, Harshank Shrotriya, and Leong Chuan Kwek. Nisq computing: where are we and where do we go? AAPPS bulletin, 32(1):27, 2022.
[4] John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2:79, 2018.
[5] google. Suppressing quantum errors by scaling surface code logical qubit. Nature, 614(7949):676-6811 2023.
[6] Laszlo Gyongyosi and Sandor Imre. A survey on quantum computing technology. Computer Science Review, 11:11-71,0019
[7] Kean Chen, Qisheng Wang, Peixun Long, and Mingsheng Ying. Unitarity estimation for quantum channels. IEEE Transactions on Information Theory, (965)5111655134, 2023.
[8] M. S. Anwar, D. Blazina, H. A. Carteret, S. B. Duckett, T. K. Halstead, A. Jones, C. M. Kozak, and R. K. Taylor. Preparing high purity initial states for nuclear magnetic resonance quantum computing, Phys. Rev. Lett., 93:040501, Jul 2004.
[9] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al. Variational quantum algorithms. Nature Reviews Physies, 3(9):25--6)) 644, 2021.
[10] Nengkun Yu. Sample efficient identity testing and independence testing of quantum states. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Schloss Dagstuhl- Leibniz-Zentrun für Informatik, 2021.
[11] Khabat Heshami, Duncan G England, Peter C Humphreys, Philip J Bustard, Victor M Acosta, Joshua Nunn, and Benjamin Sussman. Quantum memories: emerging applications and recent advances. Journal of modern optics, 63(20))2005-2028, 2016.
[12] Fermi Ma and Hsin- Yuan Huang. How to construct random unitaries. Proceedings of the 57th Annual ACM Symposium Theory of Computing, pages 806-809, 2025.
[13] Laura Cui, Thomas Schuster, Fernando Brandao, and Yuan Huang. Unitary designs in nearly optimal depth. arXiv preprint arXiv:2507.06216 2025.
[14] Thomas Schuster, Jonas Haferkamp, and Hsin- Yuan Huang. Random unitaries in extremely low depth. Science, 389(6755):92-66, 2025.
[15] Jeongwan Haah, Yunchao Liu, and Xinyu Tan. Efficient approximate unitary designs from random pauli rotations. 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 463-475. IEEE, 2024.
[16] Chi-Fang Chen, Jordan Docter, Michelle Xu, Adam Bouland, Fernando GSL Brandão, and Patrick Hayden. Efficient unitary designs from random sums and permutations. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 476-484, IEEE,
2024.
11

---

[17] Ashley Montanaro and Ronald de Wolf. A survey of quantum property testing. arXiv preprint arXiv:1310.2033, 2013.
[18] Dorit Aharonov, Jordan Cotler, and Xiao-Liang Qi. Quantum algorithmic measurement. Nature commurtications, 13(1):887) 2022.
[19] Konrad Banaszek, Marcus Cramer, and David Gross. Focus on quantum tomography. New Journal of Physics, 15 (512))1250,,, 2013.
[20] David Gross, Yi-Kai Liu, Steven Flammia, Stephen Becker, and Jens Eisert, Quantum state tomography via compressed sensing. Physical review letters, 105(15): 150401, 2010.
[21] Sitan Chen, Brice Huang, Jerry Li, Allen Liu, and Mark Sellke. When does adaptivity help for quantum state learning? In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 391- IEEE, 2023.
[22] Sitan Chen, Jordan Cotler, Hsin-Yual Huang, and Jerry Li. Exponential separations between learning with and without quantum memory. In 202/ IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 574-585. IEEE, 2022.
[23] Sebastien Bubeck, Sitan Chen, and Jerry Li. Entanglement is necessary for optimal quantum property testing. In 2020 JEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 692-703. IEEE, 2020.
[24] Sitan Chen, Jerry Li, Brice Huang, and Allen Liu. Tight bounds for quantum state certification with incoherent measurements. In 2022 IEEE 63rd Annual Symposiun Foundations of Computer Science (FOCS), pages 1205-1213. IEEE, 2022.
[25] John Wright. How to learn quantum state, PhD thesis, Carnegie Mellon University, 2016.
[26] Sitan Chen, Jerry Li, and Ryan O'Donnell. Toward instance-optimal state certification with incoherent measurements. In Conference on Learning Theory, pages 2541 2541-2596. PMLR, 2022.
[27] Anurag Anshu, Zeph Landau, and Yunchao Liu. Distributed quantum inner product estimation. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 44 51, 2022.
[28] Marcel Hinsche, Marios loannou, Sofiene Jerbi, Lorenzo Leone, Jens Eisert, and Jose Car- rasco. Efficient distributed inner product estimation via pauli sampling. arXiv preprint arXiv:2405.06544 2024.
[29] Daiwei Zhu, Ze-Pei Cian, Crystal Noel, Andrew Risinger, Debopriyo Biswas, Laird Egan, Yingyue Zhu, Alaina M Green, Huerta Alderete, Nhung H Nguyen, et al. Cross Cross-platform comparison of arbitrary quantum states. Nature communications, 13(1):6620, 2022.
[30] Hsin- Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16(10): 1050-1105, 2020.
[31] Antonio Anna Mele. Introduction to haar measure tools in quantum information: A beginner's tutorial. Quantum, 8:1340, 2024.
[32] Yves Audibert and Sébastien Bubeck. Best arm identification in multi-armed bandits. In COLT-23th Conference on learning theory-2010, pages 13-p, 2010.
[33] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 998-1027. PMLR, 2016.
[34] Daniel Russo. Simple bayesian algorithms for best arm identification. In Conference Learning Theory, pages 1417-1418. PMLR, 2016.
[35] Kevin Jamieson and Robert Nowak. Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. 2014 48th Annual Conference on Information Sciences and Systems (CISS), pages 1-6, 2014.
12

---

[36] Victor Gabillon, Mohammad Ghavamzadeh, and Alessandro Lazaric. Best arm identification: unified approach fixed budget and fixed confidence. Advances in Neural Information Processing Systems, 25, 2012.
[37] Robert Bechhofer.
Single-stage procedures for ranking multiply-classified variances normal populations. Technometrics, 10(4):693-714 1968.
[38] Edward Paulson. sequential procedure for selecting the population with the largest mean from k normal populations. The Annals of Mathematical Statistics, pages 174-180, 1964.
[39] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price. Collision-based testers optimal for uniformity and closeness. Chic. J. Theor. Comput. Sci, 25:1-21, 2019.
[40] Clément L Canonne. A survey on distribution testing: Your data is big. but blue? Theory of Computing, pages 1-100, 2020.
[41] Fernando GSL Brandão, Wissam Chemissany, Nicholas Hunter-Jones, Richard Kueng, and
John Preskill. Models of quantum complexity growth. PRX Quantum, 2(3):030316, 2021.
[42] Weiyuan Gong, Jonas Haferkamp, Qi Ye, and Zhihan Zhang. On the sample complexity of purity and inner product estimation. arXiv preprint 2 2024.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The main claims made the abstract and introduction include the contribution of the paper and relevant the main content.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We mentioned the limitations of lower bound proof the Conclusion and Outlook section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
13

---

The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: For each theoretical result, the paper provides the full set of assumptions and complete (and correct) proof.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not include experiments. We believe that conducting simula- tions will align with our theoretical results and we will consider to validate our algorithms experimentally by real quantum devices in the future.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may
14

---

be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
httpe//guiide//ooeeSeeeee www.bmmmsssioooiiiyi.ooocc for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https wwwaiiicgguiee//eeeeeeee www.eeoboiiisiioooooooooooo sww.ubiiiisioooooocccc... for more details.
/ //nips
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
15

---

Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:p::://.nrrppp..ccccpttttt//
Answer: [Yes]
16

---

The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This paper discusses theoretical work related to the field of quantum informa- tion. There is no societal impact of the work performed
Guidelines:
The answer NA means that there no socictal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: This paper discusses theoretical work related to the field of quantum informa- tion. The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided relcasing unsafe images.
17

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. cow datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
18

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.MM policy Cactpp/s//aaarrpss..cc////eeeeee for what should or should not be described.
19

---

Table 1: Description of commonly used-notations
Notation
Description
the qubit number quantum state
d 2"
the set of the unknown quantum state
= [S]
the 2-th quantum state in S
P(S)
the i-th purest quantum in S
p²
P
the purest quantum state in S
A
A, Tr(pi-) ) Tr(p')
D
Arj Tr Tr(pn))
(
fixed orthogonal basis Caxd d-dimensional identity matrix
La
U(d)
the set of d x unitary matrix
A Auxiliary tools
A.1 Description of commonly used-notations
A.2 Probability inequalities for sums of bounded random variables
In this paper, we utilize the following inequalities, which are provided for the sake of completeness.
Theorem A.1 (Chebyshev's Inequality). Let be any random variable with expected value μ = E[X] and finite variance Var(X). Then, for any real number >> 0:
P( =1 Var(X)
(12)
Theorem A.2 (Hoeffding's Inequality). If 11, ,,, Xn are independent with P(a S; 5) = 1 and common mean μ then for any >
-2ne² (b- a²²
P
Σ
Xi - 1 > S 2xxp
(13)
Theorem A.3 (Bernstein's 's Inequality). If X1. Xn are independent bounded random variables
such that E x,] 0 for all E (I,..., n and P( S then, for any c > O,
nE²
X
26
$ exx
(14)
20 + 2cc/3
where 0² = 1 7 Em Var(X;).
A.3 Properties of Haar unitary matrix
For a locally compact topological group, its Haar measure is a unique nonzero left-invariant measure (or right-invariant, depending on the formulation) under group operations. The Haar unitary matrix is the Haar measure on the unitary matrix group and is the concept of drawing unitary matrices uniformly at random. The formal definition of Haar unitary matrix is as follows:
Definition A.4. The Haar unitary matrix is the unique probability measure μи that is both left and right invariant over the unitary matrix group, i.c., for all integrable functions f and for all unitary matrix V, we have:
J(UV)dU = S Ju-Hoar f(VU)dU.
U
J(U)dU
JU-Haar
(15)
For any unit column vector x E Cd, we have
EU-Hear [f(Ux)] = E [f(])))]
(16)
We will use the following lemma to complete our proofs in this paper.
20

---

Lemma A.5 (see Lemma 22 of Ref. (7)). Let A, B, C be Hermitian matrices. Then
Ea (b|A))) Tr((A),
(17)
and
E Bypae (x) d(d (T)( +T
(18)
and
C (M a(d 1)(d (T(A)) + Tr(AByTH(C)
(19)
+ (B)A)))(BBC) + +TTr(BC)))
and
Exwca (WW
E TTASBOCCD Pa(T)),
d(d + 1)(d 2) + 3)
mES.
(20)
where Pa(T)) = dd1 -o 2 (61, is} and a is permutation on items.
B Proof of IMPQSI with incoherent measurement
B.1
Proof of property for purity collision
Lemma B.1. The expectation and variance of the purity estimation satisfying
E
Pr+
(21)
771
and
d
2
Var[gl
<
+
p
(22)
m²
m
1=
Proof. The expectation of ğ satisfying
1
E
11
=1
1=0
1
=E
=i}
m
1=0
1=
11 = i
(23)
(ay=1)
Σ Σ
1 =1]
m
j=1 kgj
B1
= 131
= -11
= =
m2
m2
2=0 1=1
j=1 kyjiij
m
Σ
2
1
m
- 1
m
m1
1=1
21

---

The expectation of g² satisfying
2
m
Σ
1a,
m72
m
d-1
E
Σ
1 = 11] 1 k-] (112 =hi
m
$1 A1
1
2m(m [} + m(m 1)(m 2) 3)E[T] 4m 1) 2) Σ Pj
m
2
BIO
4
Σ
Pi
m
m
Then, we have
Varlø] - E[gg]]
2 d-1
(24)
<
B
Σ
m
m ==
B.2 proof of Theorem 4.1
By using the techniques similar to (27). we can prove the following lemma:
Lemma B.2 (See Lemma 16 of 277 ). The expectation of w(p, k) and Go.s Algorithm
satisfies
(m 1)(1 + Tr(p²))
(p k]] = E[gns]
(25)
m(d + 1)
and the variance of (), satisfies
VarlE(p.j)) = (
(26)
d3
m²d
md²
By the definition of w() and the definition of (c), we have
P(w(p", k) S w(p(t): 1:))
=P (w(p(() k)) w(p' k)) 2 (m 1)
Since wi(:,)) E [0, by Lemma
B.2 and Bernstein's 's inequality, we have
(m - 1) (8)
P (w(p()) k) w(p',
m
Nx m-1 m(d+1)
(1)
<exp
(27)
0 n ma² +
24
3(++1)
-(2 VeN&A(o)
exxp
By union bound of error probability, we have
22

---

K-1
P(wlp', k)) w(pro),mi) mk))
On
k=
i= =++l-k
k-
K
exp -S7
(28)
d
k=
i=+1-k
K-1
exp -S2 (K-N ))
d
By definition of Ng. we have
((
d
Vc N K
(K+I-
(29)
log(K) K +1-
d
VeN
x (K+I-KK)
(K)
K K+1-k
Combining equation 28 and
29
we have
K- 1
(S2
VeN
x A(K+-K))
S
k exp
log(K)d K+1-k
k=
K [K- - 1)
VCNHH
exp
log( (o)(K)))
where H1 min.g(l...... Ac
B.3 proof of Lemma 4.2
Proof. By the definition of w(:s)) :) and the definition of A(), we have P(w(p", k) I w(P()) R:))
(m ())
=P (w(p k) w(p", k)) 2
10, [0, Since wo(:.) E
by Lemma
B.2 and Bernstein's 's inequality, we have
(w(P())))) k)) w(p'; (k) (m - 1) (8)
P
m
N d
m-
A
m(d+1}
< exp
(30)
O 21))
2D(3)
3(d+1)
N₂ ( d2
N₂ 4 ))
exp
min
By a union bound of error probability, we have
P(w(p", ,k) S (p)p)))
Cn
K
K
exp (s2
min
Na
No N1.
(31)
d2
km
im K+
1ーk
K
k
exp
-S2
min
NNA((++-H))
N₂ N (xA((+11)))))
d
23

---

By definition of Ng, and combining equation (31. we have
K(K- 1) exp (S2 min
NHz log(K)
NH.
CN v
2
[)
log K)d
where H1 g Aga and H2 min
A/
C Proof of lower bound
C.1 Proof of Lemma 5.3
Suppose that there exists such an algorithm satisfying that the error probability of for solv- ing Problem 1.1 with the quantum state set Sp whose error probability is less than en- Let ps, (11, V1: ...; NNN NN: 2) denote the probability of the event satisfying
1. for E 1,..., N, the round N, the algorithm A select the 2--th quantum state for measurement, and its output is ys
2. the algorithm A output z-th quantum state at the end.
Furthermore, let q5, (Z1, Vii IN (Ni2) Ps, (21, ::: UN: 2).
denote the error probability corresponding to
Since when using A to solve the Problem 1.1 emor probability is less than ex. Then for all quantum state set = (,,,..., pK), we have
( VIN...E (N: 2x. M1:........... UN12) S eN.
(32)
WN NN
When the learner use the algorithm A to solve the problem 5.2 its error probability satifying
c S JAND Jen (S (11, V15 ... NN uNi dpspce (4), Vi; NN,, yyN; 2 da
$ [ JWND eNde
EN.
(33)
then prove that if there is an algorithm A can solve the Problem 5.2 with the error probability less than ex, then it can solve the Problem 1.1 with the error probability less than ev Furthermore, establish the proof by considering the contrapositive of this statement.
C.2 proof of Lemma 5.5
Without loss of generality, assume that Mg arg M' Tr(M'). According to the definition of POVM, there exists a unitary matrix V and diagonal matrix Eg diag(bo, ... ba-1). i), where bp .... ba- E [0, 1] such that
Mo = VE.V
Σ
1
Mi -I --VV Σ
1=0
We have
Tr(M)) Tr(En)
Σ
bis
1=0
(34)
Tr(Mi) = Tr( Eo)
by.
24

---

Let PM (M (U' denote the probability that M "accepts" the quantum state eU) + d-1 ld. According to the property of the Haar measure and the identity matrix La. we have
Haar
(Mo
- la) )
= Haar
Tr
Mo
Σ (V) (aU10x00ut + 1-11--0 La
-EEu~Haar
Tr
d
27
bilitit (aU1o)oout + -0010) Vio)
-ear
(35)
Haar
Σ
(abx(i1111000001111)) + Σ bi
- (u
=Bur
(ab. (ab(((1110)) +
1 -
Let V, is the matrix satisfying that Vilt) (0), then Vi is an unitary matrix and V/-1 V/', we have
(Mo
-Eu~Haar
Σ
(ab(((U1000001111)) 1 1- a (I((MM))
-Bar-Har
(abx(011()))))11)))
1 1- a T((Mo)
(36)
1 - - (abx()1)))))))
= Biiwer
= Eepieed
by (1110)
1=0
1=0 jzL
+2
(ab: (vli)()))))
- TMo +
1 - ax)
Tr (Mo)
1=0
According to the Lemma A.5
we have for i,j {O...., d - 1}. $ j.
E (111) d'
(37)
and
2 E E (111))( d(d+1) 1)
(38)
and similarly
Exnee (111) d(d+1)
(39)
25

---

According to Equation
36
37
38
and
39
we have
Haur (PM(M
2n²
d-1
d-1
20x(1 a))
d-1
(
2
b9 b
+
Σ
b,b, +
Tr(Mo)
Σ bj +
(Mr)
d(d + 1)
d(d+1) 1)
d
i=0 jzt
2=
a²
d-1
b +
a²
d-1
bi
2
2a(1 a)
Tr(M))
Σ
d-1
bi +
(17 d
1-- a
(Mb)
d(d +1 1)
d(d 1)
d2
1=0
1=0
a²
a²
2a(1 a)
1 (1-a
2
(M6)
+
TT (M2)
+
(Mp)
d(d + 1)
did
+ 1)
d2
d
a²
a²
+
TY2())),
a(d 1)
d²
de +
(40)
and
Huwe (Po
-Bu~Haar
Tr
Mo
aUU10)0OUt
1-a 1- la +
d
d-1
-Bu~Haar
Tr
aU10) 6VVV
1 1- a la
(41)
1 1- a la ))
Tr(Mo)
-Bu~Haar
Tr
Then the variance of pm (MolU) is given by
Var (M
PPM (MolU)
(BU~Haar (pm(M))())))
a²
d-1
1
a²
TM² IT
d(d + 1)
dld + 1)
a
d-1
69 (dd
(Mo)
d(d (dd+1)
+1
1=0
a
d-1
Σ 63 (Mo)
dd((+1)
(42)
6. (Mo))
d(d+1)
a
(dTr(Mo) TM2
d(d+1)
a² (d(+11 (TTr(Mo) d(d+1)
(dTr(Mo) - TM²
From Chebyshev's 's Inequality, we have
|Mu(MMlU))
Tr(Mo) d
20 Tr(Mo)
PU-Haar
(43)
d
26

---

And
(M
(V (a010)(0luu) + 1 1 =
1a)
=Ir
d
=Ir
(V (aU10)(010t + -g11) Ir
Σ
vi (2(1)
(44)
6V))(VVI U10)0010 + =(a)) + Mo
=aTr
Σ
d
(E (V (U10)01U1 2242) ). have
Let (M) 'r
Mo cdM,UM PM((olU) d
(45)
C.3 Proof of Theorem 5.6
We will use the following theorem to complete the proof:
Theorem C.1 (see Theorem of Ref. (32)). Let vi, ...... VK be Bernoulli distributions with parameters
in (a, al, (0, 1/2). For any forecaster, there exists permulation {1, ...y K} (,,..., K) such that the probability error of the forecaster on the bandit problem defined by in = (o(1):--. DK =
vo(K) satisfies
en 2 exp (- [_ +(1))) (-15+o(1))mH)
(46)
pa(1 - a)
where H min; (E[o-) (Errs)))
Let (M, U) denote the error probability for algorithm A to solve the problem 5.4 with specific unitary matrix U and POVM M, and M min Tr(M'). Then the error probability of A to solve the problem 5.4 satisfying
JNEON I JUHHaar
Pe(M UYdMUU
(47)
$ MMDD JU-H Pe (M E UMMdMMUU.
The first line corresponds to the deifintion of ex the second line corresponds to that (AM, U) 2 0
and UM is a subset of unitary matrix.
When the i-th quantum state is measured using M, the process in which the output result is accepted by M follows Bernoulli distribution with parameter Tr(Mpu) From Lemma 5.5 and the definition of c(M, U), we have
Tr(Mp, (U,M)a; + Tr(M)
(48)
d
If c(M,U)= O, we need to find the Bernoulli distribution with the largest parameter where the parameter of the i-th Bernoulli distribution Tr(Mp: (U) = a(M, U)a + Tr(M) Then we have d
Tr(Mp: U) Tr(MP,1U PU
=(MMU)a; c(M, U)a
(49)
dzy d-I
dzp
=c(MUU)
d
Since Tr(M) > 16, for U E U(M) we have
Tr(MplU) = ((M+ Tr(M)
(50)
2 Tr(M)
Tr(M)
Tr(M)
2d
27

---

And since M = arg mi Tr(M'), we have Tr(M) - 2. then for U E U we have
Tr(M)
Tr(M)
Tr(Mp:]U) E
(51)
2d
2d
and
Tr(M) 1
(52)
2d
2
According to Theorem C.1 and the definition of UM, for U E UM have
(1 (1- 2 (m(20)) min (Tr(Mp - ((MMMM))))M))))
Pel (M,U) 2 exp
-0
1 (T(MM)
(Vilzz- - V d2(s) - T)- ))
No. (M, U)
exp
min
Tr(M)
i(d ((d-1)
(M,
dz.- + d2(0)
1 - 2 /d2z. ()(d(()) -
exp
min
Ω
THMM
i(d -
NC U)
dez 1| (dz(s)) - 1]
exp
min
Ω
TY(M)
i(d - 1)
(2( U)
min dD(6)
cxp
Tr(M))
i(d 1)
(53)
According to the definition of UM, for UM we have
2 Tr(M) TT(M)
c(,
(54)
d
According to Equation
53 and Equation
54 we have
(U,
min dD(i)
Pc
(U, exp
Ω
TM(M)
i(d - 1)
d
TY)
N
d
dA
exp
min i(d 11
Tr(M)
(55)
N
A (6)
2 exp
min
d
H
exp
d
Similarly, if cU, <= 0, we have
(-0
NH
p. (U, 2 exp
(56)
28

---

According to Equation
47
55
56
we have
C
pe (M) E UM}dMdU
MEDM
U-Haar
exp -0 10 (o(NN))
LiU E UM}dMdu
MEDM
U-HHAT
NH
exp
11 E UM)dMau
d NH d
Un-Haar
I JMEDM
exp
PP
NH
zexp
d
Then for any algorithm Ap addressing Problem 5.4 cannot identify the purest random quantum state with an error probability lower than exp (-0 the proof.
According to Lemma 5.3 we can complete
D Proof of Theorem 6.1
By the definition of - and the definition of (c), we have
P(u((p" k) w((()))))) k))
=P (w(p()) k) w(p" , k)) 2 A()
Since T(...)) [0, and Hoeffding's inequality, have
(w(P(() k)) w(p', 2 (a)
Nk (a) 2
S exp
(57)
2
2
2 (5)
< exp
By a union bound of error probability, we have
P(w(p" k) I u(p(s)) mk))
Cn
k=
k+11-
K
K
N
(K+
exp
(58)
8
k
K-1
N
(K+1-k)
kexp
8
By definition of Nr. we have
N - K
N- K
A P
(K
A (K+1-K) S
(59)
log K) +1-k
log(K)
K+1-k
Combining equation 588 and
(59)
we have
K
A
cn <
k exx
X K+1-k
8log(K)
k=1
K
1)
N
exp
8log(K)
29

---

where H2 = min k)
E
Simulation Results
To empirically validate our theoretical results, we performed numerical simulations on classical simulators to evaluate the performance of the proposed method under finite-samen sammee-salleeee conditions. We considered a collection of 10 randomly generated 6-qubit quantum states of the form
Ia d
P: - X.) ( ( +
(60)
where each (+:)) is pure state sampled uniformly at random, and the mixing parameter X; chosen such that the purity Tr(p2) = 0.5 + 0.04i. The task is to identify the state with the highest purity given . 30,000 copies of the unknown quantum states.
We tested the following three algorithms:
IM_ PQSI: proposed adaptive algorithm using only incoherent measurements.
CM_PQSI: variant incorporating coherent measurements via the SWAP test.
Unadaptive: a non-adaptive baseline that uniformly allocates samples and uses the same purity estimator IM M_POSI.
Each algorithm was run for 100 independent trials. The results are summarized as follows:
IM POSI achieves a 53% success rate, with lower average purity 0.8736 and higher variance 0.001319.
CM POSI achieves perfect success in all 100 runs and consistently selects the state with purity 0.9.
Unadaptive achieves 43% success rate, with lower average purity 0.86192 and higher variance 0,002145.
These results demonstrate that coherent measurements (via the SWAP test) substantially improve accuracy, confirming the theoretical prediction of their advantage. Moreover, comparing IM_ M_PQII with the Unadaptive algorithm shows that adaptivity enhances performance by allocating more samples to promising candidates, leading to higher estimation accuracy and success rates.
Due to the computational cost of high-dimensional quantum-state simulation, experiments restricted to small systems (n = 6) and moderate sample budgets (N = 3 x 10²). Nevertheless, the observed behavior aligns well with theoretical predictions, and expect the advantages of adaptive and coherent measurement strategies to become even more pronounced for larger-scale systems and higher sample budgets.
30


Reviews:
[{"review_id": "qvN3l2NbMu", "reviewer": "Reviewer_7uPd", "summary": "This paper addresses the problem of quantum noise in the context of quantum system identification and introduces the task of purest quantum state identification. Theoretical analysis is provided to support the proposed approach.", "questions": "1）Regarding the lower bound, it would be helpful to clarify which specific factors or parameters determine the lower bound in the proposed analysis. For example, does it depend on the system dimension, noise level, or properties of the quantum state ensemble?\n2）In Algorithm 2, an additional SWAP test circuit is introduced to perform coherent measurements. However, it remains unclear how this component contributes to improving the accuracy or robustness of purest quantum state identification. A more detailed discussion or theoretical justification would strengthen the argument.\n3）Experimental validation of the proposed method is currently lacking. Incorporating numerical simulations or prototype experiments—such as using noisy intermediate-scale quantum (NISQ) devices or classical simulators—would significantly enhance the applicability of the approach.", "limitations": "Including simulation experiments would further strengthen the theoretical claims and improve the overall completeness of the work.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe authors introduce an incoherent measurement algorithm to solve the purest quantum state identification problem and provide a theoretical analysis of the error probability and lower bound.\nWeaknesses:\nNo simulation experiments are presented. Including such results would help validate the effectiveness of the proposed algorithm.", "was_revised": true, "final_justification": "Thank you for the author's response and for addressing my question. I would like to maintain my original  score.", "rebuttal": "We sincerely appreciate your valuable time and effort in reviewing this paper. We thank you for the thoughtful feedback you provided, which significantly improved the quality of this paper. For the potential concerns you bring up, we provide point-by-point responses in the following paragraphs.\n\n---\n\n**Response to factors or parameters in lower bound(Question 1):** \n\nThank you for your helpful comment. We agree that explaining the parameters behind our lower bound will make the result clearer to readers. Our lower bound is  \n$$\ne_N \\geq \\exp\\left(- O\\left(\\frac{N H_1}{d}\\right)\\right),\n$$  \nwhere $H_1 = \\min_{i \\in \\{2, \\ldots, K\\}} \\frac{\\Delta_{(i)}}{i}$ and $d = 2^n$ is the system dimension.\n\nWe briefly explain how each factor affects this bound:\n\n- **Number of samples $N$:**  \n  A larger $N$ leads to a smaller error lower bound. \n\n- **System dimension $d$:**  \n  As the number of qubits increases, $d = 2^n$ grows exponentially. This makes the problem harder, since the required number of samples increases rapidly with the system size.\n\n- **Quantum state ensemble (through $H_1$):**  \n  $H_1$ reflects the purity gap between the optimal state and the others. A smaller gap (i.e., states with similar purities) makes it more difficult to identify the optimal one, which matches the intuitive hardness of distinguishing nearly identical states.\n\n- **Noise level:**  \n  Our model assumes noiseless measurements. If measurement noise is present, both the algorithm and the analysis would need to be adjusted based on the specific noise model. On the other hand, our method can be used to identify the system with the lowest noise level, since the noise of a quantum channel is often characterized by the purity of its Choi state.\n\nWe thank the reviewer again for the suggestion and will include this explanation in the revision.\n\n---\n\n**Response to the contribution of swap test(Question 2):** \n\nThank you for the insightful comment. We agree that clarifying the role of the SWAP test in our algorithm is important for understanding its contribution to performance. Below we explain its theoretical advantage by comparing the error probability upper bounds with and without the SWAP test.\n\nWhen the SWAP test is used, our algorithm achieves the following upper bound:\n$$\ne_N \\leq \\exp\\left(- \\Omega\\left(\\frac{N H_2}{\\log K}\\right) \\right),\n$$\nwhere $H_2 = \\min_{i \\in \\{2, \\ldots, K\\}} \\frac{\\Delta_{(i)}^2}{i}$ and $\\Delta_{(i)}$ denotes the purity gap between the $i$-th best state and the optimal one.\n\nWe now consider two scenarios to compare this with the algorithm that does not use the SWAP test:\n\n1. **When $\\Delta_{(i)} > 1/d^2$**:  \n   The lower bound for the algorithm *without* the SWAP test becomes $e_N \\leq \\exp\\left(- \\Omega\\left(\\frac{N H_1}{\\log K \\cdot 2^n}\\right) \\right)$,where $H_1 = \\min_{i \\in \\{2, \\ldots, K\\}} \\frac{\\Delta_{(i)}}{i}$.  Comparing the two bounds, we see that the dominant difference lies in the $2^n$ factor. In this regime, the algorithm using coherent measurements (i.e., the SWAP test) can achieve the same error probability bound with $O(1/2^n)$ samples, demonstrating a substantial advantage.\n\n2. **When $\\Delta_{(i)} \\leq 1/d^2$**:  \n   In this case, both algorithms yield similar lower bounds of the form $e_N \\leq \\exp\\left(- \\Omega\\left(\\frac{N H_2}{\\log K}\\right) \\right)$, and thus exhibit comparable performance.\n\nThese comparisons show that the SWAP test significantly improves the sample efficiency when there is a not small purity gap between the optimal and suboptimal states. On the other hand, when the purity differences are extremely small ( $\\leq 1/d^2$), the two algorithms perform similarly. However, in realistic scenarios, such small purity gaps can often be ignored, and the corresponding states can be treated as equally good choices. In typical applications, we aim to distinguish states with noticeable purity differences, where the benefit of coherent measurements via the SWAP test becomes clearly evident.\n\nWe will incorporate this explanation in the revised version to better highlight the value of the SWAP test.\n\n---\n\n**Response to experimental validation(Question 3):**\n\nWe sincerely thank the reviewer for this excellent suggestion. We agree that both numerical simulations and real experiments can significantly enhance the credibility and practical relevance of our theoretical results.\n\nHowever, implementing such experiments comes with notable challenges. On the simulation side, numerically modeling large-scale quantum systems requires repeated high-dimensional matrix operations, which is computationally intensive and limits us to relatively small system sizes. On the experimental side, realizing real quantum hardware experiments is currently constrained by the limited availability and accessibility of physical quantum devices.\n\nWe fully recognize the importance of the reviewer’s suggestion. To this end, we conducted **numerical simulations** using classical simulators to evaluate the practical performance of our method in a finite-sample regime as follows.\n\nIn our simulations, we considered a set of 10 randomly generated 6-qubit quantum states of the form  \n$$\n\\rho_i = (1 - \\lambda_i) \\frac{I_d}{d} + \\lambda_i |\\psi_i\\rangle\\langle\\psi_i|,\n$$  \nwhere $|\\psi_i\\rangle$ are pure states sampled uniformly at random, and the mixing parameter $\\lambda_i$ is chosen so that the purity of $\\rho_i$ is exactly $0.5 + 0.04i$ for $i = 1, \\dots, 10$. The task is to identify the state with the highest purity using 30,000 copies of the unknown quantum states.\n\nWe tested the following four algorithms:\n\n- **IM_PQSI**: Our proposed adaptive algorithm using only incoherent measurements.  \n- **CM_PQSI**: A variant of our algorithm that incorporates coherent measurements (via the SWAP test).  \n- **Unadaptive**: A non-adaptive baseline that uniformly allocates samples and uses the same purity estimator as IM_PQSI.\n\nEach algorithm was run for 100 independent trials. The results are as follows:\n\n- **CM_PQSI** achieves perfect success in all 100 runs and consistently selects the state with purity 0.9.  \n- **IM_PQSI** achieves a 53% success rate, with lower average purity 0.8736 and higher variance 0.001319. \n- **Unadaptive** achieves a 43% success rate, with lower average purity 0.86192 and higher variance 0.002145. \n\nFrom these simulations, we find that the SWAP test (coherent measurement) significantly improves accuracy, demonstrating the advantage of coherent measurements. Comparing IM_PQSI with the Unadaptive algorithm shows that the adaptive strategy improves accuracy by allocating more samples to better-performing states, resulting in more accurate purity estimation and higher success rates. \n\nDue to the limitations of classical simulation resources, we are currently restricted to small-scale experiments, with both the system dimension $ d = 2^n $ and the total sample size $N$ constrained.  However, based on our theoretical results, we expect that the advantage of our algorithm will become even more pronounced as both the quantum system dimension and sample budget increase.\n\nOur current simulations are relatively simple. We plan to perform more extensive simulations and real-device experiments in the future, and will include these results in the paper to further enhance the credibility of our conclusions.\n\n---\n\nWe sincerely thank the reviewer again for these insightful questions. We will incorporate further discussion of these points in the revised version of the paper. If there are any further questions or points that require clarification, we would be grateful for the opportunity to address them."}, {"review_id": "KqUfT9ilkz", "reviewer": "Reviewer_j8kw", "summary": "This paper introduces Purest Quantum State Identification (PQSI) - the task of identifying the purest state out of a set of finite states. The authors propose algorithms for both single-copy and multi-copy measurement strategies, along with a lower bound for the former. The motivation is to identify the quantum state least affected by noise, which is framed as identifying the state with the highest purity.", "questions": "- The distinction between properties for a fixed POVM and properties averaged over Haar random POVMs is sometimes mixed up by the authors. This can drastically affect the results and their proofs require careful attention to how expectations and variances are taken.\n- How do the authors get the second equation of 552? This seems incorrect. \n- In particular, there are many unjustified steps/approximations in proofs, especially in Lemma B.1 (the variance approximation) and Lemma 5.5 (factor of 2 in variance and justification for Haar integral application is questionable). I suggest the authors carefully redo their technical analyses. \n- Notation could be more consistent.\n\nUpdate: these questions and concerns have been addressed in the comments and I am satisfied with the answers.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n- The paper contains algorithms for both single and multi-copy measurement ability.\n- The authors keep practical considerations in mind. \n\nWeaknesses:\n1.  Before delving into technical flaws, I believe this work is simply not suited for NeurIPS. The content and research direction has virtually nothing to do with machine learning. This type of work is probably better suited for a quantum theory journal/conference like QIP/TQC.\n\n2.  The derived bounds on the error probability are all extremely loose. Am I perhaps missing something? For example in Thm 1.3 and 1.4, if the gaps H_1 and H_2 are small, this gives an upper bound close to 1. These are two of the main results in a completely theory-based paper.\n\n3.  There are many technical issues in the proofs and I question the validity of the technical soundness.\n\nUpdate after rebuttal: \n1.  Indeed, this work is suitable for the online learning theory category, but I still maintain that it is more appropriate for QIP/TQC. \n2.  The authors clarified that loose bounds in small gap regimes are an illustration of the hardness of the task and pointed to other analogous settings in RL for which this occurs which marginally puts this concern at ease.\n3. My concerns around technical issues have been resolved by the author's response.", "was_revised": true, "final_justification": "As explained in the revised review, the concerns around technical soundness have been addressed. Considering this, as well as the very positive reviews by the other reviewers, I am happy to change my score from reject to borderline accept.", "rebuttal": "We sincerely appreciate your valuable time and effort in reviewing this paper. We would like to emphasize that we are confident in the correctness and significance of our main results. \n\nWe sincerely apologize for any confusion caused by insufficient explanation or minor typographical errors in the presentation. In the revised version, we will provide detailed justifications for each step to improve clarity and readability. We provide point-by-point responses to your questions in the following paragraphs.\n\n---\n\n**Response to Relevance to NeurIPS and ML Community(Weakness 1):** \n\nOur paper is fundamentally centered on **online learning theory**, a core and active area of research regularly featured at NeurIPS. Although our application involves quantum states, the main problem we study is a sequential estimation task with bandit feedback—where the learner adaptively selects measurements based on past observations. This feedback-driven structure is standard in online learning and aligns closely with the NeurIPS community’s interests.\n\nThe quantum setting introduces additional challenges, such as exponentially large state spaces and restricted observability, making the learning task particularly complex and meaningful. These features do not isolate our work from machine learning; rather, they provide a high-dimensional framework to explore the limits of online learning under novel constraints.\n\nOur contribution thus extends classical online learning theory into the quantum regime in a way that advances both fields. This fits well with NeurIPS’s mission of supporting research that pushes learning theory into new, high-impact domains.\n\nNeurIPS and other top-tier venues have a history of accepting theoretical works involving quantum aspects, e.g., [1][2][3]. In particular, [1]—a highly cited NeurIPS paper—addresses quantum-state online learning and quantum bandit problems. Compared to [1], our model is more grounded in current experimental constraints and has broader relevance to near-term quantum technologies.\n\nWe firmly believe that our contribution fits well within the scope of NeurIPS and will be of interest to its community.\n\n---\n\n**Response to the derived bounds on the error probability(Weakness 2) :** \n\nWe would like to clarify that the bounds in Theorems 1.3 and 1.4 are not overly loose. When the gaps $H_1$ and $H_2$ are small, this indicates the presence of a suboptimal quantum state whose purity is very close to that of the optimal one. In such cases, the problem itself becomes intrinsically difficult, and a large number of samples is required to distinguish between nearly optimal states—reflected in the scaling of $N$ in our bound. This behavior is expected and consistent with similar phenomena in statistical learning and bandit literature. For instance, classical results on best-arm identification also exhibit dependence on such gap parameters [4]. \n\nAs an analogy, in the classical stochastic multi-armed bandit setting[5], the instance-dependent regret is often bounded by:\n$$\\mathbb{E}[\\text{Regret}(T)] \\leq \\sum_{a: \\mu(a) < \\mu^*} \\frac{\\log T}{\\Delta(a)},$$ \n\nwhere $\\Delta(a) = \\mu^* - \\mu(a)$ is the gap between the optimal arm and arm $a$. When the gap is small, the regret bound becomes large, reflecting the increased difficulty in distinguishing between near-optimal choices. Extreme cases where the gap $\\Delta(a)$ approaches zero do not invalidate the meaningfulness of the bound in general settings. A similar phenomenon is captured by our bounds through the gap parameters $H_1$ and $ H_2 $.\n\nHence, our result is theoretically justified and meaningful.\n\n---\n\n**Response to the distinction between properties for a fixed POVM and properties averaged over Haar random POVMs (Question 1):**\n\nWe would like to assure you that our analyses concerning fixed POVMs and Haar random POVMs are correct. In our work, Haar random POVMs are used to perform measurements on quantum states for unbiased estimation of purity. In the theoretical analysis, we carefully account for the variance arising from both the randomness of Haar sampling and the measurement outcomes associated with the fixed POVM drawn from the Haar distribution. **Considering both sources of randomness is essential for a correct and complete analysis.** This should not be viewed as a conflation of the two types of measurements, but rather as the proper structure of the variance decomposition in our setting.\n\n---\n\n**Response to  the second equation of 552 (Question 2) :**\n\nWe would like to clarify that **the second equation in line 552 is correct.** The presence of the $\\Omega$ notation is optional in the first line of 552. From Theorem C.1, we obtain the first line of equation 552:\n$$\np_e^\\mathcal{A}(\\mathcal{M},U) \\geq \\exp\\left(-O\\left( \\frac{N}{\\left(\\frac{\\operatorname{Tr}(M)}{d}\\right)\\left(1-\\frac{\\operatorname{Tr}(M)}{d}\\right)} \\min_i \\frac{\\left(\\operatorname{Tr}(M\\rho^\\star|U) - \\operatorname{Tr}(M\\rho_{(i)}|U)\\right)^2}{i} \\right)\\right).\n$$\n\nIn Equation (44), we showed that $1 - \\frac{\\operatorname{Tr}(M)}{2d} \\geq \\frac{1}{2}$. This allows us to safely replace the factor $1 - \\frac{\\operatorname{Tr}(M)}{d}$ with $1/2$ in the bound without affecting the inequality, since the substitution only loosens the lower bound. Furthermore, this constant $1/2$ appears inside the $O(\\cdot)$ term and therefore can be omitted.\n\nLastly, in Equation (41), we provided an alternative expression for the difference $\\operatorname{Tr}(M\\rho_i|U) - \\operatorname{Tr}(M\\rho_j|U)$. Substituting that into the first line of 552 yields the second equation directly.\n\nSince the expression is inside the $O(\\cdot)$ notation, using “=” rather than “$\\geq$” does not affect the validity of the bound.\n\n\nWe will clarify this derivation in the revised version to avoid further confusion.\n\n---\n\n**Response to the question of Lemma B.1 and Lemma 5.5(Question 3):**\n\n(a) **Lemma B.1** :  Here we briefly explain the key idea behind bounding $ \\operatorname{Var}[\\tilde{g}] $. According to the definition of $ \\tilde{g} $, the first line of Equation (479) follows directly. When expanding the expression $ \\sum_{i=0}^{d-1} \\left[ \\sum_{j=1}^m \\mathbf{1}(x_j = i) \\right]^2 $, the squared terms $ [\\mathbf{1}(x_j = i) ]^2 $ contribute exactly $ m $ ones due to indicator properties. Their sum yields a term that cancels with the $ 1/m $ factor, explaining the second line of Equation (479). All remaining index patterns fall into three categories, whose expectations correspond to $ \\mathbb{E}[\\tilde{g}] $, $ \\sum_{i=0}^{d-1} p_i^3 $, and $ \\mathbb{E}[\\tilde{g}]^2 $, respectively. These categories correspond to index patterns with: (1) two identical indices among four, (2) one pair of repeated indices, and (3) all distinct indices. Their respective counts are $ \\Theta(m^2) $, $ \\Theta(m^3) $, and $ m^4 - \\Theta(m^3) $. Based on this classification, we obtain the third line of Equation (479). By further simplification, the fourth line of Equation (479) follows. We can show that\n$ \\mathbb{E}[\\tilde{g}^2] \\leq c_1 \\frac{\\mathbb{E}[\\tilde{g}]}{m^2} + c_2 \\frac{\\sum_{i=0}^{d-1} p_i^3}{m} + \\mathbb{E}[\\tilde{g}]^2 $, and hence derive the upper bound $ \\operatorname{Var}[\\tilde{g}] \\leq c_1 \\frac{\\mathbb{E}[\\tilde{g}]}{m^2} + c_2 \\frac{\\sum_{i=0}^{d-1} p_i^3}{m} $, which will be used in the proof of Lemma 5.2.\n\n\n(b) **Lemma 5.5 factor of 2 in variance**: The factor of 2 is necessary in our setting because we aim to ensure that more than $\\frac{3}{4}$ of the probability satisfies the desired property. By Chebyshev’s inequality, $\\mathbb{P}(|X - \\mu| \\geq \\varepsilon) \\leq \\frac{\\mathrm{Var}(X)}{\\varepsilon^2}$, we require $\\varepsilon = 2\\sqrt{\\mathrm{Var}(X)}$ to guarantee that $\\mathbb{P}(|X - \\mu| \\geq \\varepsilon) \\leq \\frac{1}{4}$, which implies $\\mathbb{P}(|X - \\mu| < \\varepsilon) \\geq 3/4$. This directly supports our probabilistic guarantee, and thus justifies the factor of 2.\n\n(c) **Lemma 5.5 Haar integral application:** In the proof of Lemma 5.5, we apply several algebraic identities that do not involve Haar randomness to simplify and derive expressions. For the part involving Haar integrals, the step is justified by standard results[6]: we transform expressions of the form $\\int_{U \\sim \\text{Haar}} \\langle 0 | U (\\cdot) U^\\dagger | 0 \\rangle dU$ into $\\int_{\\psi \\sim \\mathbb{C}^d} \\langle \\psi | (\\cdot) | \\psi \\rangle dU$,  and similarly,  $\\int_{U \\sim \\text{Haar}} f(V U) (\\cdot) dU$ into  $\\int_{U \\sim \\text{Haar}} f(U) (\\cdot) dU$, where $V$ is a unitary matrix.  These are valid changes of variables due to the unitary invariance of the Haar measure. Therefore, the application of Haar integrals in our derivation is mathematically sound.\n\n\nWe will revise the manuscript to clearly state the reasoning behind each step and improve the overall clarity and readability.\n\n---\n\n**Response to the Notation(Question 4):**\n\nThank you for your comment. We will revise the manuscript to ensure consistent and clear notation throughout.\n\n---\n\nOnce again, we sincerely thank you for your time and insightful feedback. We are confident in the correctness and significance of our results, and we will carefully revise the paper to enhance its clarity and readability in accordance with your suggestions.\n\n**If you have any further questions or concerns, please let us know—we would be glad to respond promptly.**\n\n---\n\nReference:\n\n[1] Aaronson S, Chen X, Hazan E, et al. Online learning of quantum states. NIPS 2018\n\n[2] Quek Y, Arunachalam S, Smolin J A. Private learning implies quantum stability. NIPS 2021\n\n[3] Yang F, Jiang J, Zhang J, et al. Revisiting online quantum state learning//AAAI 2020.\n\n[4] Audibert J Y, Bubeck S. Best arm identification in multi-armed bandits//COLT-23th.\n\n[5] Slivkins A. Introduction to multi-armed bandits[J]. Foundations and Trends in Machine Learning, 2019.\n\n[6] Mele A A. Introduction to Haar measure tools in quantum information: A beginner's tutorial. Quantum, 2024, 8: 1340."}, {"review_id": "OU2u2YBgOG", "reviewer": "Reviewer_mGRh", "summary": "The authors propose two algorithms for purest quantum state identification. The first algorithm requires first a random unitary transformation of the quantum state, followed by a POVM measurement. Purity can be estimated by the probability of identical outcomes, after which the highest is found. The second algorithm utilizes the SWAP test to directly compute the purity instead of estimation.", "questions": "1. The algorithm for incoherent measurements seems to share similiarities with the classical shadows method proposed in Ref. [26] with slight modifications in for 4-unitary designs, projective measurements to POVM, and from estimating all values to an fixed accuracy to a search problem. Regardless, the main protocol seems similiar, with the random transformation and subsequent channel inversion that takes the form of computing identical probablities in this algorithm.\n\n2. Given that Lemma A.5 only lists results up to the 3rd power, does this imply that the protocol only require 3-designs instead of 4-designs? In this case, we would only require random Clifford circuits, which would be surprising.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "__Strengths__\n1. The paper proposes an interesting question for quantum information.\n\n2. The paper provides a lower bound in addition to algorithm results, adding more context to the performance of the algorithm itself.\n\n__Weakness__\n1. Not sure if the scope of the paper is aligned with the call for papers, particularly the theory track, though I suppose optimization could work.\n\n2. Algorithm and results seem simililar to the classical shadows method proposed in Ref. [26]. See further Question 1.\n\n3. The proof of requiring unitary 4-designs is not provided in the manuscript, and Haar random unitaries are assumed to be provided in the proof. See further Question 2.", "was_revised": true, "final_justification": "The authors have addressed my previous concerns, and I retain my original evaluation.", "rebuttal": "We sincerely appreciate your valuable time and effort in reviewing this paper. We thank the thoughtful feedback you provided, which significantly improved the quality of this paper. For the potential concerns you bring up, we provide point-by-point responses in the following paragraphs.\n\n---\n\n**Response to the scope of the paper(Weakness 1)**\n\nOur paper is fundamentally centered on **online learning theory**, a core and active area of research regularly featured at NeurIPS. Although our application involves quantum states, the main problem we study is a sequential estimation task with bandit feedback—where the learner adaptively selects measurements based on past observations. This feedback-driven structure is standard in online learning and aligns closely with the NeurIPS community’s interests. Because online learning theory is a part of learning theory, we believe our work is more suitable for the theory track than the optimization track.\n\nThe quantum setting introduces additional challenges, such as exponentially large state spaces and restricted observability, making the learning task particularly complex and meaningful. These features do not isolate our work from machine learning; rather, they provide a high-dimensional framework to explore the limits of online learning under novel constraints.\n\nOur contribution thus extends classical online learning theory into the quantum regime in a way that advances both fields. This fits well with NeurIPS’s mission of supporting research that pushes learning theory into new, high-impact domains.\n\nNeurIPS and other top-tier venues have a history of accepting theoretical works involving quantum aspects, e.g., [1][2][3]. In particular, [1]—a highly cited NeurIPS paper—addresses quantum-state online learning and quantum bandit problems. Compared to [1], our model is more grounded in current experimental constraints and has broader relevance to near-term quantum technologies.\n\nWe firmly believe that our contribution fits well within the scope of NeurIPS and will be of interest to its community.\n\n---\n\n**Response to the technology of the paper(Question 1)**\n\nWe are grateful to the reviewer for pointing out this connection. Using random procedures to build unbiased estimators for quantum properties is indeed a powerful and widely used approach.\n\nWhile our method shares some general ideas with Ref. [26]—such as using random unitaries and measurement inversion—we make several important extensions:\n\n- We give a more detailed theoretical analysis focused on the specific task of purity estimation.\n- Our algorithm is adapted to the purity testing problem, instead of aiming to estimate all observables equally well.\n- We also apply online learning methods to improve estimation accuracy, which is especially useful given the practical limits of today’s quantum hardware.\n\nWe believe that our contributions—from problem setting to algorithm design and theoretical results—provide meaningful progress in quantum property testing. They also better match the capabilities and constraints of current NISQ-era quantum devices.\n\n---\n\n**Response to the unitary 4-designs(Question 2)**\n\nThank you for this valuable question—it reflects a deep understanding of the topic. Indeed, our algorithm **requires unitary 4-designs**.\n\nThis is because, in our protocol, estimating the purity of quantum states involves squaring the measurement outcomes. The expectation of the purity estimator relies on the expression  $\\mathbb{E}_{U \\sim \\text{Haar}}[U^{\\otimes 2} (\\cdot)U^{\\dagger\\otimes 2}],$ \n\nwhile the variance analysis of the estimator requires $\\mathbb{E}_{U \\sim \\text{Haar}}[U^{\\otimes 4} (\\cdot) U^{\\dagger\\otimes 4}]$.\n\nAlthough Lemma A.5 lists results only up to the 3rd power, the 4th power analysis is in Lemma B.2, where we directly cite relevant results from previous work. Therefore, the protocol still requires unitary 4-designs to guarantee the correctness of the theoretical bounds.\n\nAccording to the algorithm described in [4], such quantities can be efficiently estimated using unitary 4-designs.\n\nWe fully agree with the reviewer that performing the estimation using only unitary 3-designs would greatly enhance the practicality of the algorithm. This is a very interesting question, and we intend to investigate it further in future work.\n\n---\n\nWe sincerely thank the reviewer again for these insightful questions. We will incorporate further discussion of these points in the revised version of the paper. If there are any further questions or points that require clarification, we would be grateful for the opportunity to address them.\n\n---\n\n**Reference:**\n\n[1] Aaronson S, Chen X, Hazan E, et al. Online learning of quantum states[J]. Advances in neural information processing systems, 2018, 31.\n\n[2] Quek Y, Arunachalam S, Smolin J A. Private learning implies quantum stability[J]. Advances in Neural Information Processing Systems, 2021, 34: 20503-20515.\n\n[3] Yang F, Jiang J, Zhang J, et al. Revisiting online quantum state learning[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2020, 34(04): 6607-6614.\n\n[4] Ma F, Huang H Y. How to construct random unitaries[C]//Proceedings of the 57th Annual ACM Symposium on Theory of Computing. 2025: 806-809."}, {"review_id": "gw4TR6STKz", "reviewer": "Reviewer_ATtA", "summary": "This paper introduces the problem of Purest Quantum State Identification (PQSI). Given $K$ unknown $n$-qubit states, the goal is to identify the quantum state with the higest purity using $N$ total copies of these states. The authors propose algorithms for both incoherent (single-copy) and coherent (multi-copy) measurement strategies and provide upper bounds on error probability. They also establish a lower bound for the incoherent case.", "questions": "1. Have you considered the fixed-confidence setting? Could your algorithms be adapted to this setting rather than the fixed-budget framework?\n2. Have you considered the lower bound for coherent measurements? How does it differ from the incoherent case, and what challenges arise in establishing it?\n3. Is it possible to use alternative purity estimation methods such as quantum tomography? If so, how would this affect the performance of your algorithms?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The formulation of the PQSI problem is novel and opens a promising direction for integrating quantum computing with online learning. While both components (purity estimation in quantum computing and best-arm identification in online learning) are well studied individually, their combination is still non-trivial and requires careful algorithmic and theoretical design.\n2. The paper provides rigorous theoretical results, including upper bounds for both incoherent and coherent measurement strategies, and a lower bound using carefully constructed hardness reductions.\n3. Compared with existing studies on quantum online learning, this paper adopts a more natural problem formulation that does not rely on strong quantum oracles.\n\nWeaknesses:\n1. The paper lacks empirical or simulation-based validation to support the theoretical claims.\n2. The presentation lacks key intuitions. For example, the collision estimator is conceptually simple, but its physical meaning and intuitions are not explained when presenting the algorithms.\n\nOverall, I recommend accepting this paper. Integrating quantum computing and online learning is a timely and important topic, but existing studies usually rely on strong assumptions about quantum oracles, and the feedback models lack concrete counterparts in real-world quantum systems. In contrast, this paper proposes a more practical problem formulation.", "was_revised": true, "final_justification": "While several theoretical aspects remain open and require further investigation, I believe this paper makes a meaningful step forward in addressing an important problem. Therefore, I lean toward acceptance and would like to maintain my positive score.", "rebuttal": "We sincerely appreciate your valuable time, effort, and constructive feedback in reviewing this paper. We are also grateful for your recognition of our work. For the potential concerns you bring up, we provide point-by-point responses in the following paragraphs.\n\n---\n\n**Response to empirical or simulation-based validation(Weakness 1):**\n\nWe sincerely thank the reviewer for this excellent suggestion. We agree that both numerical simulations and real experiments can significantly enhance the credibility and practical relevance of our theoretical results.\n\nHowever, implementing such experiments comes with notable challenges. On the simulation side, numerically modeling large-scale quantum systems requires repeated high-dimensional matrix operations, which is computationally intensive and limits us to relatively small system sizes. On the experimental side, realizing real quantum hardware experiments is currently constrained by the limited availability and accessibility of physical quantum devices.\n\nWe fully recognize the importance of the reviewer’s suggestion. To this end, we conducted **numerical simulations** using classical simulators to evaluate the practical performance of our method in a finite-sample regime as follows.\n\nIn our simulations, we considered a set of 10 randomly generated 6-qubit quantum states of the form  \n$$\n\\rho_i = (1 - \\lambda_i) \\frac{I_d}{d} + \\lambda_i |\\psi_i\\rangle\\langle\\psi_i|,\n$$  \nwhere $|\\psi_i\\rangle$ are pure states sampled uniformly at random, and the mixing parameter $\\lambda_i$ is chosen so that the purity of $\\rho_i$ is exactly $0.5 + 0.04i$ for $i = 1, \\dots, 10$. The task is to identify the state with the highest purity using 30,000 copies of the unknown quantum states.\n\nWe tested the following four algorithms:\n\n- **IM_PQSI**: Our proposed adaptive algorithm using only incoherent measurements.  \n- **CM_PQSI**: A variant of our algorithm that incorporates coherent measurements (via the SWAP test).  \n- **Unadaptive**: A non-adaptive baseline that uniformly allocates samples and uses the same purity estimator as IM_PQSI.\n\nEach algorithm was run for 100 independent trials. The results are as follows:\n\n- **CM_PQSI** achieves perfect success in all 100 runs and consistently selects the state with purity 0.9.  \n- **IM_PQSI** achieves a 53% success rate, with lower average purity 0.8736 and higher variance 0.001319. \n- **Unadaptive** achieves a 43% success rate, with lower average purity 0.86192 and higher variance 0.002145. \n\nFrom these simulations, we find that the SWAP test (coherent measurement) significantly improves accuracy, demonstrating the advantage of coherent measurements. Comparing IM_PQSI with the Unadaptive algorithm shows that the adaptive strategy improves accuracy by allocating more samples to better-performing states, resulting in more accurate purity estimation and higher success rates. \n\nDue to the limitations of classical simulation resources, we are currently restricted to small-scale experiments, with both the system dimension $ d = 2^n $ and the total sample size $ N $ constrained.  However, based on our theoretical results, we expect that the advantage of our algorithm will become even more pronounced as both the quantum system dimension and sample budget increase.\n\nOur current simulations are relatively simple. We plan to perform more extensive simulations and real-device experiments in the future, and will include these results in the paper to further enhance the credibility of our conclusions.\n\n---\n\n**Response to key intuitions(Weakness 2):**\n\nWe agree with the reviewer that providing more intuitive explanations would improve the clarity of our presentation. In the revised version, we will enhance the exposition of key intuitions behind our algorithm design.\n\nIn particular, regarding the use of the collision estimator, our rationale is as follows:\n\nThe POVMs we adopt has $d$ possible outcomes. Let $p_i$ denote the probability of observing the $i$-th outcome. We show that the purity of a quantum state is closely related to $\\sum_{i=1}^d p_i^2$. Therefore, an essential step in our algorithm is to estimate this quantity accurately. \n\nThe collision estimator is a well-established technique in classical statistics for estimating the second moment $\\sum_{i=1}^d p_i^2$. Motivated by this, we adopt the collision estimator as a natural and efficient tool for estimating quantum state purity in our setting.\n\n---\n\n**Response to the fixed-confidence setting(Question 1):**\n\nWe sincerely thank the reviewer for raising this insightful and important question. Indeed, we have considered the fixed-confidence setting as a potential extension of our framework. While we believe that our algorithm can be adapted to this setting with some modifications, conducting a satisfactory theoretical analysis within this framework remains a challenging task.\n\nThe main difficulties are summarized as follows:\n\n* Modeling Assumptions: In classical best-arm identification under the fixed-confidence setting, it is typically assumed—to enable theoretical analysis—that all arms (distributions) belong to a one-parameter exponential family. In our setting, applying this assumption would imply that each quantum state in the candidate set is characterized by only a single scalar parameter, which is generally not realistic.\n\n* KL Divergence Analysis: Algorithm design and lower bound analysis in the fixed-confidence setting strongly rely on precise control of the Kullback–Leibler (KL) divergence between distributions. However, for Haar-random unitary measurements, the KL divergence between measurement outcome distributions has not been adequately studied in existing work. Most known results require that one of the compared quantum states be either a pure state or a maximally mixed state—conditions that do not hold in our general setting.\n\n* Alternative Approaches: We have also explored using alternative random matrix ensembles such as the Gaussian Orthogonal Ensemble (GOE) in place of Haar unitaries. Unfortunately, these substitutes introduce their own challenges and have not resolved the core analytical difficulties.\n\nIn summary, the fixed-confidence setting is a valuable and meaningful direction. Although we have explored it, we have not yet found an analysis that meets the level of completeness and clarity we are aiming for. We plan to continue working on this important extension in future work.\n\n\n\n---\n\n**Response to lower bound for coherent measurements(Question 2):**\n\nWe sincerely thank the reviewer for this insightful question. We have indeed considered the problem of establishing a lower bound for coherent measurements, and we believe that the lower bound in this setting could be significantly smaller than that for incoherent measurements.\n\nAnalyzing the coherent case introduces additional layers of complexity. In each round, one not only has to decide which quantum states to measure and which measurement basis to use, but also how many states to jointly measure in a single coherent operation. This additional degree of freedom greatly complicates both the modeling and theoretical analysis.\n\nOur current work primarily focuses on the algorithm design and lower bound analysis under the incoherent measurement model. Nonetheless, we agree that studying lower bounds and algorithmic strategies under the coherent setting is both important and technically challenging. We view this as an important direction and plan to investigate it in future work.\n\n---\n\n**Response to alternative purity estimation(Question 3):**\n\nWe thank the reviewer for raising this interesting and relevant question.\n\nIndeed, one could consider applying quantum state tomography as an alternative approach for estimating the purity of the quantum states. However, doing so would likely reduce the accuracy of the algorithm in the fixed-budget setting.\n\nQuantum tomography aims to reconstruct the full density matrix of a quantum state, including many properties that are only weakly related to purity. As a result, it becomes more difficult to estimate purity accurately.\n\nFrom a theoretical perspective, achieving trace distance $\\epsilon$ via quantum state tomography requires $\\Theta(d^3/\\epsilon^2)$ measurements using general POVMs [1]. In contrast, our purity estimation method only requires $O(\\sqrt{d}/\\epsilon^2)$ samples to achieve the same error. As the dimension $d$ increases, tomography-based methods require significantly more measurements, which leads to reduced accuracy under a fixed sampling budget.\n\n---\n\nWe sincerely thank you again for your insightful questions. We will incorporate further discussion of these points in the revised version of the paper. If there are any further questions or points that require clarification, we would be grateful for the opportunity to address them.\n\n---\n\n**Reference:**\n\n[1] Chen S, Huang B, Li J, et al. When does adaptivity help for quantum state learning?[C]//2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2023: 391-404."}]

Author rebuttal:

Meta-review: This paper addresses the quantum noise in quantum system identification and presents the problem termed purest quantum state identification (PQSI). The proposed framework is applicable to various quantum computing and quantum communication tasks. Algorithms for incoherent (single-copy) and coherent (multi-copy) measurement strategies are proposed with theoretical results on the error probability. Reviewers find that the paper addresses an interesting problem with solid theoretical results and a more natural, practical formulation. After rebuttal, reviewers acknowledge their concerns resolved and favor the acceptance for this paper. The AC goes through all the comments and agrees with the reviewers. Accept is recommended for this paper.
Decision: Accept (poster)