Quantum algorithms can offer substantial computational speed-ups, yet these advantages may disappear once the cost of structure-agnostic classical data encoding is taken into account. Real-world problem instances, however, often possess rich internal structure. This raises a fundamental question: can such structure be harnessed to make quantum speed-ups survive end-to-end cost accounting? Here we show that it can. We introduce a general framework for structure-aware quantum data encoding that compiles compact recursive descriptions of problem structure into efficient state-preparation circuits, translating structural information directly into reduced encoding complexity. For the uncapacitated facility-location problem, structure-agnostic encoding admits a classical dequantization that eliminates the quadratic quantum speed-up, whereas exploiting the underlying problem structure restores this advantage even when state-preparation costs are included. More broadly, the same framework prepares structured quantum states for combinatorial optimization that capture non-trivial relations among constraints, including group balance, conflicts and synergistic rewards, extending previously reported super-polynomial quantum advantages to broader classes of objectives. These results establish exploitable problem structure as a computational resource for quantum algorithms and provide a systematic route towards realizing quantum advantage in data-intensive problems.
Quantum algorithms can offer substantial computational speed-ups, yet these advantages may disappear once the cost of structure-agnostic classical data encoding is taken into account. Real-world problem instances, however, often possess rich internal structure. This raises a fundamental question: can such structure be harnessed to make quantum speed-ups survive end-to-end cost accounting? Here we show that it can. We introduce a general framework for structure-aware quantum data encoding that compiles compact recursive descriptions of problem structure into efficient state-preparation circuits, translating structural information directly into reduced encoding complexity. For the uncapacitated facility-location problem, structure-agnostic encoding admits a classical dequantization that eliminates the quadratic quantum speed-up, whereas exploiting the underlying problem structure restores this advantage even when state-preparation costs are included. More broadly, the same framework prepares structured quantum states for combinatorial optimization that capture non-trivial relations among constraints, including group balance, conflicts and synergistic rewards, extending previously reported super-polynomial quantum advantages to broader classes of objectives. These results establish exploitable problem structure as a computational resource for quantum algorithms and provide a systematic route towards realizing quantum advantage in data-intensive problems.
Quantum algorithms with super-polynomial or polynomial speedups have been central to the promise of quantum computing, yet their real-world impact remains unclear because most analyses are asymptotic and worst-case. This work develops a systematic framework for characterizing practical quantum advantage that explicitly separates three components of speedup: (i) oracle/algorithmic advantage (Salg), (ii) data/instance structure advantage (Sdata), and (iii) implementability advantage under realistic noise and resource constraints (S impl). We first formalize quantum speedup as a triple (Salg, Sdata, S impl) that jointly captures theoretical complexity, distribution of input instances, and hardware feasibility. We then analyze seven canonical algorithms-Grover search, amplitude estimation, phase estimation, HHL, VQE, QAOA, and Hamiltonian simulationand extract common structural patterns that lead to genuine advantage over classical algorithms for specific problem families. Building on these patterns, we derive sufficient and necessary conditions for average-case quantum advantage in terms of problem symmetries, spectral properties, and data-access models. For NISQ-era devices, we incorporate realistic noise models and compilation overheads to define a practical advantage region in the space of problem size, error rates, and algorithm depth. The framework yields decision procedures and flowcharts that, given a candidate problem and hardware profile, can certify whether a proposed quantum algorithm is likely to achieve practical advantage or not. Case studies in finance (Monte Carlo risk analysis), chemistry (electronic structure estimation), and optimization (QAOA-type problems) illustrate how our method can guide algorithm and hardware co-design, and also show negative results where no advantage is achievable under realistic constraints. This work turns "quantum advantage" from a vague narrative into a quantitatively testable property of algorithmproblem-hardware triples.
This paper establishes a theoretical framework for constraint-preserving quantum optimization that maintains problem structure throughout quantum algorithm execution, addressing a fundamental challenge in translating real-world optimization problems to quantum hardware. We develop mathematical formulations that embed hard constraints directly into quantum circuit design rather than relying solely on penalty methods, proving that certain constraint classes can be exactly enforced through quantum state space restriction. Our theory characterizes the complexity of constraint preservation across different problem classes including facility location, network optimization, and resource allocation, deriving conditions under which quantum algorithms can explore only feasible solution spaces. We introduce automated repair mechanisms with theoretical guarantees on convergence to valid solutions and establish bounds on the additional quantum resources required for constraint maintenance. The framework provides rigorous analysis of trade-offs between constraint flexibility, quantum circuit depth, and solution quality, identifying problem structures amenable to efficient constraint-preserving quantum formulations. We extend the theory to socioeconomic weighting and multi-objective scenarios, proving that preference structures can be incorporated without compromising feasibility guarantees. This theoretical foundation advances practical quantum optimization by ensuring quantum algorithms produce implementable solutions while maintaining provable performance characteristics across diverse constrained optimization domains including logistics, energy systems, and infrastructure planning.
Along with the development of quantum technology, finding useful applications of quantum computers has been a central pursuit. Despite various quantum algorithms have been developed, many of them often require strong input assumptions, which is hardware demanding. In particular, recent advances on dequantization have revealed that the quantum advantage is more of a mere artifact of strong input assumptions. In this work, we propose a variant of these algorithms, leveraging both classical and quantum resources. Provided the classical knowledge (the entries) of the matrix/vector of interest, a classical procedure is used to pre-process this information. Then they are fed into a quantum circuit which is shown to be a block encoding of the matrix of interest. From this block-encoding, we show how to use it to tackle a wide range of problems, including principal component analysis, linear equation solving, Hamiltonian simulation, preparing ground state, and data fitting. We also analyze our protocol, showing that both the classical and quantum procedure can achieve logarithmic complexity in the input dimension, thus implying its potential for near term realization. We then discuss several implications and corollaries of our result. First,, our results suggest there are certain matrices/Hamiltonians where our method can provide exponential improvement compared to the existing ones with respect to the sparsity. Regarding dense linear systems, our method achieves exponential speed-up with respect to the inverse of error tolerance, compared to the best previously known quantum algorithm for dense systems. Last, and most importantly, regarding quantum data fitting, we show how the output of our quantum algorithms can be leveraged to predict unseen data. Thus, it provides an end-to-end application, which has been an open aspect of the previous quantum data fitting algorithm.
Efficient encoding of classical data into quantum circuits is a critical challenge that directly impacts the scalability of quantum algorithms. In this work, we present an automated compilation framework for resource-aware quantum data loading tailored to a given input vector and target error tolerance. By explicitly exploiting the trade-off between exact and approximate state preparation, our approach systematically partitions the total error budget between precision and approximation errors, thereby minimizing quantum resource costs. The framework supports a comprehensive suite of state-of-the-art methods, including multiplexer-based loaders, quantum read-only memory (QROM) constructions, sparse encodings, matrix product states (MPS), Fourier series loaders (FSL), and Walsh transform-based diagonal operators. We demonstrate the effectiveness of our framework across several applications, where it consistently uncovers non-obvious, resource-efficient strategies enabled by controlled approximation. In particular, we analyze a computational fluid dynamics workflow where the automated selection of MPS state preparation and Walsh transform-based encoding, combined with a novel Walsh-based measurement technique, leads to resource reductions of over four orders of magnitude compared to previous approaches. We also introduce two independent advances developed through the framework: a more efficient circuit for d-diagonal matrices, and an optimized block encoding for kinetic energy operators. Our results underscore the indispensable role of automated, approximation-aware compilation in making large-scale quantum algorithms feasible on resource-constrained hardware.
We present a comprehensive end-to-end quantum algorithm for tensor problems, including tensor PCA and planted kXOR, that achieves potential superquadratic quantum speedups over classical methods. We build upon prior works by Hastings~(\textit{Quantum}, 2020) and Schmidhuber~\textit{et al.}~(\textit{Phys.~Rev.~X.}, 2025), we address key limitations by introducing a native qubit-based encoding for the Kikuchi method, enabling explicit quantum circuit constructions and non-asymptotic resource estimation. Our approach substantially reduces constant overheads through a novel guiding state preparation technique as well as circuit optimizations, reducing the threshold for a quantum advantage. We further extend the algorithmic framework to support recovery in sparse tensor PCA and tensor completion, and generalize detection to asymmetric tensors, demonstrating that the quantum advantage persists in these broader settings. Detailed resource estimates show that 900 logical qubits, ∼1015 gates and ∼1012 gate depth suffice for a problem that classically requires ∼1023 FLOPs. The gate count and depth for the same problem without the improvements presented in this paper would be at least 1019 and 1018 respectively. These advances position tensor problems as a candidate for quantum advantage whose resource requirements benefit significantly from algorithmic and compilation improvements; the magnitude of the improvements suggest that further enhancements are possible, which would make the algorithm viable for upcoming fault-tolerant quantum hardware.
This compendium presents a structured collection of computational problems with credible prospects for realizing meaningful quantum advantage, focused on describing problem characteristics rather than specific algorithms. It is intended for non-quantum researchers and practitioners with strong computational backgrounds, particularly domain experts, seeking to assess the relevance of quantum methods to real-world problems. The compendium focuses on enumerating core problems for which there is good evidence that a quantum computer can realize more than a quadratic speedup in offline non-relativized time-complexity (e.g., as opposed to in oracular settings, streaming models, or communication advantages). Entries characterize the structural constraints that real-world instances must satisfy to realize those advantages in practice. The intention is to provide a reference that can be leveraged to connect quantum algorithms to practical use cases.