Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.38134

Resource Compatibility in Optimal Quantum Symmetry Testing

Yimeng Cao, Ranyiliu Chen, Chengkai Zhu, Xin Wang

quant-phSubmitted Sep 29, 2026• Announced Sep 30, 2026• 0 citations
arXivHTMLPDF

Abstract

Can a symmetry be tested optimally without using the quantum resource naturally associated with it? For parallel subgroup-versus-Haar testing, we derive a quantitative representation-theoretic converse for every protocol with zero type-I error: the excess type-II error is bounded below by the sum of two nonnegative penalties, one for weight on suboptimal subgroup types and one for deviations of within-type Schur profiles from their typewise extremal profiles. At optimality, both penalties vanish, yielding support and weight locking for every optimal system marginal. Disjointness of the resulting locked set and the free marginal set rules out resource-free optimality, whereas overlap alone does not establish attainability. For the diagonal torus in dimension $d\geq 2$, optimal testing without coherence is possible only with a single query. We determine both the exact optimal type-II error over all protocols with incoherent system marginals and the minimum system-marginal coherence required to attain the unrestricted optimum. For the orthogonal subgroup in dimension $d\geq 2$, a real protocol attains the optimum at every query number. For the qutrit Clifford group, Wigner-positive optimal protocols exist at three and four queries but not from five through nine; whether they exist beyond nine queries remains open. Together, these results relate the subgroup- and query-dependent resource requirements of optimal symmetry testing to structural constraints on optimal system marginals.

Comments
6 pages, 1 figure; Supplemental Material: 35 pages, 8 tables

Related papers

Hypothesis testing of symmetry in quantum dynamics

Yu-Ao Chen, Chenghong Zhu, Keming He +2 more

Symmetry plays a crucial role in quantum physics, dictating the behavior and dynamics of physical systems. In this paper, we develop a hypothesis-testing framework for quantum dynamics symmetry using a limited number of queries to the unknown unitary operation and establish the quantum max-relative entropy lower bound for the type-II error. We construct optimal ancilla-free protocols that achieve optimal type-II error probability for testing time-reversal symmetry ($T$ symmetry) and diagonal symmetry ($Z$ symmetry) with limited queries. Contrasting with the advantages of indefinite causal-order strategies in various quantum information processing tasks, we show that parallel, adaptive, and indefinite causal-order strategies have equal power for our tasks. We establish optimal protocols for $T$ symmetry testing and $Z$ symmetry testing for six and five queries, respectively, from which we infer that the type-II error exhibits a decay rate of $O({m}^{\ensuremath{-}2})$ with respect to the number of queries $m$. This represents a significant improvement over the basic repetition protocols without using global entanglement, where the error decays at a slower rate of $O({m}^{\ensuremath{-}1})$.

arXiv:2411.14292•Physical Review A•May 5, 2025•4 citations

Predicting symmetries of quantum dynamics with optimal samples

Masahito Hayashi, Yu-Ao Chen, Chenghong Zhu +1 more

Identifying symmetries in quantum dynamics, such as identity or time-reversal invariance, is a crucial challenge with profound implications for quantum technologies. We introduce a unified framework combining group representation theory and subgroup hypothesis testing to predict these symmetries with optimal efficiency. By exploiting the inherent symmetry of compact groups and their irreducible representations, we derive an exact characterization of the optimal type-II error (failure probability to detect a symmetry), offering an operational interpretation for the quantum max-relative entropy. In particular, we prove that parallel strategies achieve the same performance as adaptive or indefinite-causal-order protocols, resolving debates about the necessity of complex control sequences. Applications to the singleton group, maximal commutative group, and orthogonal group yield explicit results: for predicting the identity property, Z-symmetry, and T-symmetry of unknown qubit unitaries, with zero type-I error and type-II error bounded by $δ$, we establish the explicit optimal sample complexity which scales as $\mathcal{O}(δ^{-1/3})$ for identity testing and $\mathcal{O}(δ^{-1/2})$ for T/Z-symmetry testing. These findings offer theoretical insights and practical guidelines for efficient unitary property testing and symmetry-driven protocols in quantum information processing.

arXiv:2502.01464•Feb 3, 2025•0 citations

Resource Marginal Problems

Chung-Yun Hsieh, Gelo Noel M. Tabia, Yu-Chun Yin +1 more

We introduce the resource marginal problems , which concern the possibility of having a resource-free target subsystem compatible with a g i v e n collection of marginal density matrices. By identifying an appropriate choice of resource R and target subsystem T, our problems reduce, respectively, to the well-known marginal problems for quantum states and the problem of determining if a given quantum system is a resource. More generally, we say that a set of marginal states is resource-free incompatible with a target subsystem T if all global states compatible with this set must result in a resourceful state in T of type R. We show that this incompatibility i n d u c e s a resource theory that can be quantified by a monotone and obtain necessary and sufficient conditions for this monotone to be computable as a conic program with finite optimum. We further show, via the corresponding witnesses, that (1) resource-free incompatibility is equivalent to an operational advantage in some channel-discrimination tasks, and (2) some specific cases of such tasks fully characterize the convertibility between marginal density matrices exhibiting resource-free incompatibility. Through our framework, one sees a clear connection between any marginal problem – which implicitly involves some notion of incompatibility – for quantum states and a resource theory for quantum states. We also establish a close connection between the physical relevance of resource marginal problems and the ground state properties of certain many-body Hamiltonians. In terms of application, the universality of our framework leads, for example, to a further quantitative understanding of the incompatibility associated with the recently-proposed entanglement marginal problems and entanglement transitivity problems.

arXiv:2202.03523•Quantum•May 22, 2024•9 citations

Planted Cliques and Quantum Symmetry-Adapted Measurements

Vojtech Havlicek, Jordan Docter, Subhash Khot

We study how quantum encodings and symmetry-adapted measurements preserve information for planted-clique detection from one classical graph. For $k=\lfloor n^{1/2-\varepsilon}\rfloor$, with fixed $0<\varepsilon<1/2$, detection is statistically possible but conjectured hard for polynomial-time classical algorithms. For a compact binary phase encoding, we prove that constant-advantage detection requires $Ω(n^{1+2\varepsilon}\ln^2 n)$ copies of the phase state of the same graph, even under arbitrary joint measurements. In the large-copy limit, the optimal decision rule thresholds the total number of $k$-cliques in the graph and its complement, but this characterization provides no efficient detector. We therefore explore measurements guided by the symmetries of the input distributions, starting with the efficient Schur transform on the full graph register. We show that weak Schur sampling, which measures only the representation label, depends only on edge count and has vanishing distinguishing power in this regime. When the label and multiplicity registers are discarded, the remaining quantum states are almost perfectly distinguishable. We show that the support of the planted state occupies only a vanishing fraction of the graph Hilbert space. Any subspace containing it still permits near-perfect detection if its relative dimension also vanishes. This gives us freedom to choose a subspace that is easier to measure. We propose exploring subgroup isotypic measurements to find such subspaces. Whether they can yield an efficient detector remains open. Finally, we show that a single supplied coherent quantum sample permits efficient detection, yielding a conditional computational separation from one classical sample under quantum planted-clique hardness.

quant-pharXiv:2609.40310•Oct 1, 2026•0 citations

Symmetry and Quantum Query-To-Communication Simulation

Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer +3 more

Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {-1,1}ⁿ → {-1,1} and G ∈ {AND₂, XOR₂}, the bounded-error quantum communication complexity of the composed function f∘G equals O(𝖰(f) log n), where 𝖰(f) denotes the bounded-error quantum query complexity of f. This is achieved by Alice running the optimal quantum query algorithm for f, using a round of O(log n) qubits of communication to implement each query. This is in contrast with the classical setting, where it is easy to show that 𝖱^{cc}(f∘G) ≤ 2𝖱(f), where 𝖱^{cc} and 𝖱 denote bounded-error communication and query complexity, respectively. Chakraborty et al. (CCC'20) exhibited a total function for which the log n overhead in the BCW simulation is required. This established the somewhat surprising fact that quantum reductions are in some cases inherently more expensive than classical reductions. We improve upon their result in several ways. - We show that the log n overhead is not required when f is symmetric (i.e., depends only on the Hamming weight of its input), generalizing a result of Aaronson and Ambainis for the Set-Disjointness function (Theory of Computing'05). Our upper bound assumes a shared entangled state, though for most symmetric functions the assumed number of entangled qubits is less than the communication and hence could be part of the communication. - In order to prove the above, we design an efficient distributed version of noisy amplitude amplification that allows us to prove the result when f is the OR function. This also provides a different, and arguably simpler, proof of Aaronson and Ambainis’s O(√n) communication upper bound for Set-Disjointness. - In view of our first result above, one may ask whether the log n overhead in the BCW simulation can be avoided even when f is transitive, which is a weaker notion of symmetry. We give a strong negative answer by showing that the log n overhead is still necessary for some transitive functions even when we allow the quantum communication protocol an error probability that can be arbitrarily close to 1/2 (this corresponds to the unbounded-error model of communication). - We also give, among other things, a general recipe to construct functions for which the log n overhead is required in the BCW simulation in the bounded-error communication model, even if the parties are allowed to share an arbitrary prior entangled state for free.

Leibniz international proceedings in informatics•Jan 1, 2022•0 citations

Certified Resource Separations in Symmetric Two-State Broadcasting

Dustin Ogle

A qubit carries one of two non-orthogonal label states, exchanged by a Pauli-𝑍 symmetry. A channel must produce a record of the label while returning the qubit, with the returned qubit’s deviation from the label held within a fixed disturbance budget; the record’s deviation from the label is the error to be minimised. We compare three implementation classes at one operating point (label overlap 3/5, budget 1/10): environment-free isometries intertwining the symmetry; channels that may use and discard an environment on which the symmetry acts trivially (equivalently, classical mixtures of the first class, with the budget on the mixture); and all channels. The optimal errors are bracketed by exact rational certificates: a feasible channel and an exactly dual-feasible point for each of the two convex classes, and an exact one-variable reduction with a rigorous interval enclosure for the nonconvex environment-free class. The unrestricted class lowers the minimal error by between 17.2789% and 17.3105% relative to the environment-free class; the environment-free optimum and the mixture-class optimum differ by less than 1.09 ⋅ 10−6, so more than 99.968640% of the reduction lies in the step from the mixture class to the unrestricted class. Equality of the first two optima is not established. All certificates are verified by exact arithmetic from standalone files; the verification requires no optimisation solver.

•Oct 3, 2026•0 citations
Can a symmetry be tested optimally without using the quantum resource naturally associated with it? For parallel subgroup-versus-Haar testing, we derive a quantitative representation-theoretic converse for every protocol with zero type-I error: the excess type-II error is bounded below by the sum of two nonnegative penalties, one for weight on suboptimal subgroup types and one for deviations of within-type Schur profiles from their typewise extremal profiles. At optimality, both penalties vanish, yielding support and weight locking for every optimal system marginal. Disjointness of the resulting locked set and the free marginal set rules out resource-free optimality, whereas overlap alone does not establish attainability. For the diagonal torus in dimension d≥2d\geq 2d≥2, optimal testing without coherence is possible only with a single query. We determine both the exact optimal type-II error over all protocols with incoherent system marginals and the minimum system-marginal coherence required to attain the unrestricted optimum. For the orthogonal subgroup in dimension d≥2d\geq 2d≥2, a real protocol attains the optimum at every query number. For the qutrit Clifford group, Wigner-positive optimal protocols exist at three and four queries but not from five through nine; whether they exist beyond nine queries remains open. Together, these results relate the subgroup- and query-dependent resource requirements of optimal symmetry testing to structural constraints on optimal system marginals.
Symmetry plays a crucial role in quantum physics, dictating the behavior and dynamics of physical systems. In this paper, we develop a hypothesis-testing framework for quantum dynamics symmetry using a limited number of queries to the unknown unitary operation and establish the quantum max-relative entropy lower bound for the type-II error. We construct optimal ancilla-free protocols that achieve optimal type-II error probability for testing time-reversal symmetry (TTT symmetry) and diagonal symmetry (ZZZ symmetry) with limited queries. Contrasting with the advantages of indefinite causal-order strategies in various quantum information processing tasks, we show that parallel, adaptive, and indefinite causal-order strategies have equal power for our tasks. We establish optimal protocols for TTT symmetry testing and ZZZ symmetry testing for six and five queries, respectively, from which we infer that the type-II error exhibits a decay rate of $O({m}^{\ensuremath{-}2})$ with respect to the number of queries mmm. This represents a significant improvement over the basic repetition protocols without using global entanglement, where the error decays at a slower rate of $O({m}^{\ensuremath{-}1})$.
Identifying symmetries in quantum dynamics, such as identity or time-reversal invariance, is a crucial challenge with profound implications for quantum technologies. We introduce a unified framework combining group representation theory and subgroup hypothesis testing to predict these symmetries with optimal efficiency. By exploiting the inherent symmetry of compact groups and their irreducible representations, we derive an exact characterization of the optimal type-II error (failure probability to detect a symmetry), offering an operational interpretation for the quantum max-relative entropy. In particular, we prove that parallel strategies achieve the same performance as adaptive or indefinite-causal-order protocols, resolving debates about the necessity of complex control sequences. Applications to the singleton group, maximal commutative group, and orthogonal group yield explicit results: for predicting the identity property, Z-symmetry, and T-symmetry of unknown qubit unitaries, with zero type-I error and type-II error bounded by δδδ, we establish the explicit optimal sample complexity which scales as O(δ−1/3)\mathcal{O}(δ^{-1/3})O(δ−1/3) for identity testing and O(δ−1/2)\mathcal{O}(δ^{-1/2})O(δ−1/2) for T/Z-symmetry testing. These findings offer theoretical insights and practical guidelines for efficient unitary property testing and symmetry-driven protocols in quantum information processing.
We introduce the resource marginal problems , which concern the possibility of having a resource-free target subsystem compatible with a g i v e n collection of marginal density matrices. By identifying an appropriate choice of resource R and target subsystem T, our problems reduce, respectively, to the well-known marginal problems for quantum states and the problem of determining if a given quantum system is a resource. More generally, we say that a set of marginal states is resource-free incompatible with a target subsystem T if all global states compatible with this set must result in a resourceful state in T of type R. We show that this incompatibility i n d u c e s a resource theory that can be quantified by a monotone and obtain necessary and sufficient conditions for this monotone to be computable as a conic program with finite optimum. We further show, via the corresponding witnesses, that (1) resource-free incompatibility is equivalent to an operational advantage in some channel-discrimination tasks, and (2) some specific cases of such tasks fully characterize the convertibility between marginal density matrices exhibiting resource-free incompatibility. Through our framework, one sees a clear connection between any marginal problem – which implicitly involves some notion of incompatibility – for quantum states and a resource theory for quantum states. We also establish a close connection between the physical relevance of resource marginal problems and the ground state properties of certain many-body Hamiltonians. In terms of application, the universality of our framework leads, for example, to a further quantitative understanding of the incompatibility associated with the recently-proposed entanglement marginal problems and entanglement transitivity problems.
We study how quantum encodings and symmetry-adapted measurements preserve information for planted-clique detection from one classical graph. For k=⌊n1/2−ε⌋k=\lfloor n^{1/2-\varepsilon}\rfloork=⌊n1/2−ε⌋, with fixed 0<ε<1/20<\varepsilon<1/20<ε<1/2, detection is statistically possible but conjectured hard for polynomial-time classical algorithms. For a compact binary phase encoding, we prove that constant-advantage detection requires Ω(n1+2εln⁡2n)Ω(n^{1+2\varepsilon}\ln^2 n)Ω(n1+2εln2n) copies of the phase state of the same graph, even under arbitrary joint measurements. In the large-copy limit, the optimal decision rule thresholds the total number of kkk-cliques in the graph and its complement, but this characterization provides no efficient detector. We therefore explore measurements guided by the symmetries of the input distributions, starting with the efficient Schur transform on the full graph register. We show that weak Schur sampling, which measures only the representation label, depends only on edge count and has vanishing distinguishing power in this regime. When the label and multiplicity registers are discarded, the remaining quantum states are almost perfectly distinguishable. We show that the support of the planted state occupies only a vanishing fraction of the graph Hilbert space. Any subspace containing it still permits near-perfect detection if its relative dimension also vanishes. This gives us freedom to choose a subspace that is easier to measure. We propose exploring subgroup isotypic measurements to find such subspaces. Whether they can yield an efficient detector remains open. Finally, we show that a single supplied coherent quantum sample permits efficient detection, yielding a conditional computational separation from one classical sample under quantum planted-clique hardness.
Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {-1,1}ⁿ → {-1,1} and G ∈ {AND₂, XOR₂}, the bounded-error quantum communication complexity of the composed function f∘G equals O(𝖰(f) log n), where 𝖰(f) denotes the bounded-error quantum query complexity of f. This is achieved by Alice running the optimal quantum query algorithm for f, using a round of O(log n) qubits of communication to implement each query. This is in contrast with the classical setting, where it is easy to show that 𝖱^{cc}(f∘G) ≤ 2𝖱(f), where 𝖱^{cc} and 𝖱 denote bounded-error communication and query complexity, respectively. Chakraborty et al. (CCC'20) exhibited a total function for which the log n overhead in the BCW simulation is required. This established the somewhat surprising fact that quantum reductions are in some cases inherently more expensive than classical reductions. We improve upon their result in several ways. - We show that the log n overhead is not required when f is symmetric (i.e., depends only on the Hamming weight of its input), generalizing a result of Aaronson and Ambainis for the Set-Disjointness function (Theory of Computing'05). Our upper bound assumes a shared entangled state, though for most symmetric functions the assumed number of entangled qubits is less than the communication and hence could be part of the communication. - In order to prove the above, we design an efficient distributed version of noisy amplitude amplification that allows us to prove the result when f is the OR function. This also provides a different, and arguably simpler, proof of Aaronson and Ambainis’s O(√n) communication upper bound for Set-Disjointness. - In view of our first result above, one may ask whether the log n overhead in the BCW simulation can be avoided even when f is transitive, which is a weaker notion of symmetry. We give a strong negative answer by showing that the log n overhead is still necessary for some transitive functions even when we allow the quantum communication protocol an error probability that can be arbitrarily close to 1/2 (this corresponds to the unbounded-error model of communication). - We also give, among other things, a general recipe to construct functions for which the log n overhead is required in the BCW simulation in the bounded-error communication model, even if the parties are allowed to share an arbitrary prior entangled state for free.
A qubit carries one of two non-orthogonal label states, exchanged by a Pauli-𝑍 symmetry. A channel must produce a record of the label while returning the qubit, with the returned qubit’s deviation from the label held within a fixed disturbance budget; the record’s deviation from the label is the error to be minimised. We compare three implementation classes at one operating point (label overlap 3/5, budget 1/10): environment-free isometries intertwining the symmetry; channels that may use and discard an environment on which the symmetry acts trivially (equivalently, classical mixtures of the first class, with the budget on the mixture); and all channels. The optimal errors are bracketed by exact rational certificates: a feasible channel and an exactly dual-feasible point for each of the two convex classes, and an exact one-variable reduction with a rigorous interval enclosure for the nonconvex environment-free class. The unrestricted class lowers the minimal error by between 17.2789% and 17.3105% relative to the environment-free class; the environment-free optimum and the mixture-class optimum differ by less than 1.09 ⋅ 10−6, so more than 99.968640% of the reduction lies in the step from the mixture class to the unrestricted class. Equality of the first two optima is not established. All certificates are verified by exact arithmetic from standalone files; the verification requires no optimisation solver.