Response-register quantum oracles admit two complementary operational interpretations: value readout and phase kickback. Although their computational equivalence is well understood, the quantitative relation between these two operational interpretations has lacked an exact characterization. We prove that, for finite Abelian response groups, the optimal single-query value-readout probability is exactly the normalized Rényi-1/2 effective Fourier support of the response state. This identity provides an exact information-theoretic characterization of optimal value-readout capability, gives the Rényi-1/2 effective Fourier support a direct operational interpretation in the oracle setting, and yields a tight phase--value complementarity theorem together with an explicit family of saturating response states.
Comments
12 pages, 4 figures, Comments and suggestions are most welcome
Response-register quantum oracles admit two complementary operational interpretations: value readout and phase kickback. Although their computational equivalence is well understood, the quantitative relation between these two operational interpretations has lacked an exact characterization. We prove that, for finite Abelian response groups, the optimal single-query value-readout probability is exactly the normalized Rényi-1/2 effective Fourier support of the response state. This identity provides an exact information-theoretic characterization of optimal value-readout capability, gives the Rényi-1/2 effective Fourier support a direct operational interpretation in the oracle setting, and yields a tight phase--value complementarity theorem together with an explicit family of saturating response states.
We study minimum-error identification of an unknown single-bit Boolean function given black-box (oracle) access with one allowed query. Rather than stopping at an abstract optimal measurement, we give a fully constructive solution: an explicit state preparation and an explicit measurement unitary whose computational-basis readout achieves the Helstrom-optimal success probability 3/4 for distinguishing the four possible functions. The resulting circuit is low depth, uses a fixed gate set, and (in this smallest setting) requires no entanglement in the input state. Beyond the specific example, the main message is operational. It highlights a regime in which optimal oracle discrimination is not only well-defined but implementably explicit: the optimal POVM collapses to a compact gate-level primitive that can be compiled, verified, and composed inside larger routines. Motivated by this, we discuss a "what if" question that is open in spirit: for fixed (n,m,k), could optimal k-query identification (possibly for large hypothesis classes) admit deterministic, closed-form descriptions of the inter-query unitaries and the final measurement unitary acting on the natural n+m-qubit input--output registers (and, if needed, small work registers)? Even when such descriptions are not compact and do not evade known circuit-complexity barriers for generic Boolean functions, making the optimum constructive at the circuit level would be valuable for theory-to-hardware translation and for clarifying which forms of "oracle access" are physically meaningful.
Introduction: A variational quantum classifier realises a function whose Fourier spectrum is fixed by the circuit and whose coefficients must be found by an optimiser. We study a readout borrowed from quantum phase estimation (QPE): a data-dependent operator acts on a target register through controlled powers, and the class label is read from an estimation register of m qubits after an inverse quantum Fourier transform (QFT). Materials and methods: We derive the exact readout distribution—a Fejér-weighted expansion in the moments of the operator—and characterise its Fourier spectrum for two single-qubit blocks: H ⋅ P h ⋅ R Y (family A) and a universal U 2 block (family B). All analytical statements are verified against a state-vector simulator, including attainment of the predicted spectrum. Three ablation controls alter one component each at an unchanged parameter count: the encoding QFT is removed, the exponential ladder of controlled powers is replaced by single powers, and the inverse QFT is replaced by independent Hadamard tests. The benchmark comprises 7680 training runs of 24 circuits on three tasks, with one generated dataset or one cross-validation fold as the unit of inference (twenty per sample size), exact signed-rank tests, and the corrected resampled t -test for the overlapping folds. Results: The support of every readout probability lies in parity-locked lattice cubes of maximal harmonic order 2 m + 1 . The maximal order is attained at every register size, in every feature and every outcome, except for family A with one target qubit, where the two highest orders cancel identically; the full support is attained at every register size used here ( t ≤ 4 , m ≤ 3 ), and the band is tapered towards its edge. Removing the encoding QFT costs family B 0.144 and 0.082 in test accuracy on the two-feature tasks, and replacing the power ladder by single powers costs 0.086 – 0.225 wherever m ≥ 2 ; replacing the inverse QFT by Hadamard tests has no detectable effect. The architecture leads the independently parameterised reference circuits only on the three-class task ( + 0.119 , p < 0.0001 ), where a parameter-tied re-uploading circuit with 12 rather than 20 parameters is not resolved from it ( + 0.023 , 95% confidence interval (CI)
In the quest to identify further quantum algorithms exhibiting superpolynomial speed-ups, a recurring theme is that the complexity of a problem is largely shaped by the input access model. Here, we study this phenomenon for the state hidden subgroup problem (StateHSP), a quantum generalization of the hidden subgroup problem in which the goal is to identify the symmetries of an unknown quantum state. For finite abelian groups, existing Fourier-sampling algorithms use O(log(∣G∣)/ε) copies of the state, but whether this scaling is optimal has remained open. We settle the complexity of the abelian StateHSP in both the previously studied sample model and a new query model, which is a stronger and operationally natural generalization that provides access to the state-preparation unitary and its inverse. In the query model, we give a time-efficient quantum algorithm using O(log(∣G/H∣)/ε) forward and inverse queries, and prove a matching Ω(log(∣G/H∣)/ε) lower bound which holds even in the stronger conjugate-query and controlled-query settings. By contrast, we show that in the sample model, Θ(log(∣G/H∣)/ε) copies are both sufficient and information-theoretically necessary, even if one allows for arbitrary collective measurements. Thus, the quadratic improvement in ε genuinely arises from coherent access to the preparation circuit. As applications, we obtain faster algorithms for learning stabilizer groups, locating unentanglement, and identifying hidden translation symmetries.
Deriving formulations to estimate worst-case size bounds for conjunctive queries under various constraints has been at the core of theoretical database research. If the problem has no constraints or has a single functional dependency, tight worst-case size bounds are computable. If the problem has more than one functional dependency, computing tight bounds can be difficult in practice and may even require an infinite number of linear inequalities in its optimization formulation. While these challenges have been addressed with varying methods, no prior research has employed quantum information theory to address this problem. In this work, we establish a connection between earlier classical information theory-based works and quantum information theory. We propose replacing the classical Shannon entropy formulation with the quantum Rényi entropy of order α∈(0,1) whose entropy cone is characterized simply by non-negativity. The first key result is to express the bound in terms of optimizing over quantum states and Rényi entropy. Optimizing with respect to quantum states rather than classical distributions transfers the hardness into the problem of characterizing classical states, yielding a sound but generally not tight upper bound. We further quantify this hardness explicitly by proposing a dichotomy theorem: if the query satisfies a head absorption rule, then the Rényi program value is at most one and ∣Q(D)∣≤rmax(D). Otherwise, the program is unbounded.
Oracle-based quantum computation reframes efficiency from classical time/space costs to query complexity, i.e., the number of accesses to a black-box unitary oracle Uf needed to reveal a hidden property or target state. This study comparatively analyzes query complexity across four canonical oracle-driven algorithms—Deutsch’s, Bernstein–Vazirani, Grover’s search, and Amplitude Amplification—to clarify how superposition, entanglement, interference, and phase kickback translate into provable speedups independent of hardware details. The objective is to systematically connect oracle structure to achievable quantum advantage by contrasting exact, single-query interference algorithms with iterative, probabilistic rotation-based algorithms, and by benchmarking classical deterministic/probabilistic query requirements against quantum bounds. Methodologically, we (i) mathematically model Deutsch and Bernstein–Vazirani via stepwise state-vector evolution to expose phase kickback and phase-encoded answer extraction in one oracle call, (ii) geometrically track Grover and Amplitude Amplification as two-dimensional state-space rotations, quantifying how repeated oracle-driven reflections amplify success amplitude, and (iii) compute classical query baselines and compare them directly with quantum query scaling. Results show that Deutsch reduces classical 2 queries to exactly 1 quantum query for constant-versus-balanced testing, while Bernstein–Vazirani deterministically recovers an n-bit hidden string s with (O(1)) quantum queries versus (O(n)) classical queries. For unstructured search over (N=2n) items, Grover achieves a bounded-error quadratic improvement from (O(N)) to (O(√{N}) queries, and Amplitude Amplification generalizes this to boost success probability from (p) to near certainty in O (1/√p) oracle applications. The central implication is a structural divide: rigid algebraic structure permits maximal, single-query speedups, whereas unstructured “chaos” necessitates iterative geometric amplification, which is more broadly applicable but demands highly stable, error-corrected hardware; consequently, quantum systems are best viewed as specialized co-processors activated when oracle structure warrants a quantum shortcut.
We study the problem of identifying an n-bit string using a single quantum query to an oracle that computes the Hamming distance between the query and hidden strings. The standard action of the oracle on a response register of dimension r is by powers of the cycle (1...r), all of which, of course, commute. We introduce a new model for the action of an oracle--by general permutations in S_r--and explore how the success probability depends on r and on the map from Hamming distances to permutations. In particular, we prove that when r = 2, for even n the success probability is 1 with the right choice of the map, while for odd n the success probability cannot be 1 for any choice. Furthermore, for small odd n and r = 3, we demonstrate numerically that the image of the optimal map generates a non-abelian group of permutations.