The hidden subgroup problem (HSP) plays an important role in quantum computation, because many quantum algorithms that are exponentially faster than classical algorithms are special cases of the HSP. In this paper we show that there exist a new efficient quantum algorithm for the HSP on groups $\Z_{N}\rtimes\Z_{q^s}$ where $N$ is an integer with a special prime factorization, $q$ prime number and $s$ any positive integer.
The hidden subgroup problem (HSP) plays an important role in quantum computation, because many quantum algorithms that are exponentially faster than classical algorithms are special cases of the HSP. In this paper we show that there exist a new efficient quantum algorithm for the HSP on groups ZN o Zqs where N is an integer with a special prime factorization.
The minimum accuracy heuristic evaluates quantum feature maps without requiring full quantum support vector machine (QSVM) training. However, the original formulation is computationally expensive, restricted to balanced datasets, and lacks theoretical backing. This work generalizes the metric to arbitrary binary datasets and formally proves it constitutes a certified lower bound on the optimal empirical accuracy of any linear classifier in the same feature space. Furthermore, we introduce Monte Carlo strategies to efficiently estimate this bound using a random subset of Pauli directions, accompanied by rigorous probabilistic guarantees. These contributions establish minimum accuracy as a scalable, theoretically sound tool for pre-screening feature maps on near-term quantum devices.
The minimum accuracy heuristic provides a training-free way to evaluate quantum feature maps, but its original formulation assumes balanced datasets, requires an exhaustive Pauli-axis scan, and lacks a formal lower-bound interpretation. In this work, we generalize the metric to arbitrary binary datasets and prove that the resulting generalized minimum accuracy, denoted , is a certified lower bound on the optimal empirical accuracy achievable by linear classifiers in the same feature space. To improve scalability, we introduce Monte Carlo axis-selection strategies that estimate from random subsets of Pauli-feature axes and derive quantile-coverage guarantees for sampling high-accuracy directions. We validate the framework using exact statevector simulations of an qubit quantum feature map, corresponding to Pauli axes, over 30 independent runs on five synthetic datasets. The proposed methods sample as few as 60 axes, produce lower-bound estimates and achieve speedups of approximately to compared with exhaustive evaluation. The results support generalized minimum accuracy as a scalable and theoretically grounded tool for pre-screening quantum feature maps in simulated quantum-kernel workflows.
1 January 2026 in Journal of Communication and Information Systems
Channel estimation in OFDM systems requires minimal complexity with one-tap equalizers and it is generally performed based on pilot symbols (PS) using least squares (LS). However, in a practical environment where impulsive noise may be present, this method may not be effective; furthermore, the minimal complexity required depends on cyclic prefixes (CP), which must be sufficiently large to cover the channel impulse response. In contrast, the use of PS and CP decreases the useful information that can be conveyed in an OFDM frame, thereby degrading the spectral efficiency of the system. In this context, we propose the use of quantum machine learning algorithms for channel estimation in OFDM systems with a reduced number of PS, without PS, and without CP. Our approach involves adapting classical machine learning models, specifically support vector regression and K-means clustering, to their quantum counterparts by integrating quantum kernels and encoding strategies suitable for channel modeling. The performance of the resulting quantum models is evaluated in comparison to LS and classical learning-based estimators. The viability of our approach is substantiated by computational simulation results obtained in frequency-selective channel models with the presence of non-Gaussian impulsive noise interfering with the symbols.
We present a training-free, certified error bound for quantum regression derived directly from Pauli expectation values. Generalizing the heuristic of minimum accuracy from classification to regression, we evaluate axis-aligned predictors within the Pauli feature space. We formally prove that the optimal axis-aligned predictor constitutes a rigorous upper bound on the minimum training Mean Squared Error (MSE) attainable by any linear or kernel-based regressor defined on the same quantum feature map. Since computing this exact bound requires an intractable scan of the full Pauli basis, we introduce a Monte Carlo framework to efficiently estimate it using a tractable subset of measurement axes. We further provide non-asymptotic statistical guarantees to certify performance within a practical measurement budget. This method enables rapid comparison of quantum feature maps and early diagnosis of expressivity, allowing for the informed selection of architectures before deploying higher-complexity models.