Quantum computing offers promising approaches to combinatorial optimization problems whose search spaces grow exponentially with problem size. The Closest String problem belongs to this category, which seeks a string that minimizes the maximum Hamming distance to any string in a given collection of reference strings. In this work, we present an end-to-end quantum implementation of the Closest String problem using the Non-Variational Quantum Walk Optimization Algorithm (NV-QWOA), evaluating its resource requirements and solution amplification capabilities. Our automated workflow converts arbitrary problem instances into quantum circuits expressed in one- or two-qubit gates that encode candidate solutions, evaluate the objective function, and apply NV-QWOA optimisation to increase the measurement probabilities of high-quality solutions. Analytical resource estimates yield a qubit complexity of O(nmlogk) and a circuit depth of O(pmlog2n+pnlogn), where n is the string length, m is the number of reference strings, k is the alphabet size, and p is the number of NV-QWOA iterations. We introduce a revised prescription for the phase-separation parameter, γ, that depends on problem size but requires no instance-specific optimization. This prescription mitigates excessive phase wrapping modulo 2π, which can weaken the relationship between objective values and the phases guiding the optimization dynamics. Across all simulated problem sizes, the algorithm consistently amplifies optimal and near-optimal candidates. This work provides an explicit gate-level implementation, an improved phase-scaling method, and a foundation for hardware experiments and benchmarking against classical algorithms.
Quantum processing of classical data fundamentally relies on efficiently mapping classical datasets onto the amplitudes of quantum states. Preparing large amplitude-encoded states, however, remains a major bottleneck in quantum computing. In this paper, we introduce a novel state-preparation framework we call Q-MERGE, that addresses this bottleneck by partitioning a large target state into Mn-qubit segments, preparing these segments independently and in parallel, and then coherently combining them into a single amplitude-encoded state using SELECT-SWAP operations and measurement. Q-MERGE is agnostic to the segment-level preparation method, allowing existing techniques to be applied to smaller subproblems while providing a tunable trade-off between circuit depth and qubit count. With mid-circuit measurement and preparation-register reuse, the required ancilla qubits can be reduced from O(Mn) to O(n). Applied to a real-world 32x1024 ultrasound dataset, Q-MERGE achieves an infidelity of 3.5x10−9, compared with 6.2x10−3 for direct preparation using the same underlying method, a more than six orders of magnitude improvement at equal CNOT circuit depth. We demonstrate its feasibility experimentally with a 53 qubit circuit comprised of 954 1-qubit gates and 478 2-qubit gates, on the Quantinuum System Model H2 trapped-ion quantum computer. The prepared state is validated using shadow-overlap tomography. Numerical analysis of Haar-random states indicates consistent success probability for up to M=107 segments, supporting the scalability of Q-MERGE for encoding massive classical datasets.
Modern quantum algorithms are increasingly formulated as coherent procedures for implementing polynomial transformations of operators and singular values. This perspective provides a powerful and unifying language for quantum algorithm design, connecting a wide range of distinct problems through five closely related key tools: block-encoding, qubitization, QSP, QSVT and GQSP. Block-encoding embeds non-unitary matrices into larger unitaries; qubitization converts block-encodings into structured operators; QSP, QSVT and GQSP enable polynomial transformations with near-optimal query complexity. Together, these techniques form a general toolkit for transforming matrix functions into implementable quantum circuits. This paper develops these techniques from first principles as a unified framework for constructing quantum algorithms. We apply this framework to representative applications to highlight design principles and demonstrate how distinct algorithms can be constructed from a unified sequence of operator transformations.
A central contribution is a systematic decision workflow for selecting the appropriate approach according to the operator structure and the desired transformation polynomial. This perspective clarifies when direct GQSP or through qubitization, or Laurent expansion, or QSVT is most appropriate. We organize algorithmic design into an end-to-end pipeline: identifying the target matrix function, constructing an appropriate block-encoding, determining the relevant spectral domain, designing a polynomial or Laurent-polynomial approximation, synthesizing the phase factors, and translating the transformation into an executable quantum circuit. By applying this unified framework to example applications, we showcase a practical methodology for reasoning, designing, and implementing quantum algorithms based on polynomial transformations.
Preparation and verification of specific quantum states is an important capability for quantum devices to realise advantages over classical computations and algorithms. In this work, we have demonstrated an end-to-end framework that combines resource-efficient quantum state preparation with rapid, robust fidelity verification on near-term quantum hardware. By experimentally preparing and validating a structured complex quantum state encoding a digitized acoustic signal on the Quantinuum H2-1 trapped-ion platform, we achieved a high hardware fidelity of Fhw=0.929. Crucially, this milestone was realized without relying on idealized assumptions or deep fault-tolerant overhead, but rather through resource-minimal circuits optimized for NISQ-era and early fault-tolerant devices.
Furthermore, we addressed a key limitation in current quantum state certification. While validation methods like shadow overlap work well for random states, their sample complexity can become prohibitively high for the structured states used in practical algorithms. We mitigate this by introducing a pre-measurement basis-change technique that reduces the verification parameter, τ, by over 10 orders of magnitude for structured targets. This approach tightens the theoretical certification guarantees of the shadow overlap method and integrates tensor-network preparation and shadow validation into a unified workflow. These results shift the paradigm of how structured classical data can be mapped to and verified on quantum hardware under realistic noise and measurement budgets. By compressing a robust verification procedure to just 1,000 measurement shots, this framework offers an immediate, scalable benchmarking standard.
Fault-tolerant architectures implement non-Clifford T gates through magic-state distillation, so the T-count of a synthesized circuit dominates its physical cost. The Solovay-Kitaev algorithm approximates any single-qubit unitary from a finite gate set with a sequence length that grows only polylogarithmically in the inverse target error, but it optimizes for numerical convergence rather than circuit economy, and its output carries structural redundancy that a gate-level compiler cannot see. We report a measurement of what diagrammatic post-processing recovers from that redundancy. Twelve hundred random single-qubit targets, spanning the three Pauli rotation families and the general gate U(theta, phi, lambda), are synthesized over Clifford+T at three recursion depths, translated into graph-like ZX-diagrams, simplified by automated rewriting, and extracted back to circuits. Post-processing removes 26.6-30.1% of the total gate count and 18.5-22.2% of the T-count. The absolute saving grows with recursion depth, from about 60 to about 1600 gates, while the fractional saving does not: it rises slightly from the shallowest setting and is then flat across a twenty-five-fold change in circuit length, and by the deepest setting the four target families are no longer distinguishable from one another. Because the rewrite rules preserve the implemented linear map, the approximation error is unchanged. The compile-time cost of the rewriting layer, by contrast, grows sharply with depth and comes to dominate the synthesis itself.
The Black Scholes equation provides a fundamental model for the no arbitrage pricing of financial derivatives. After finite difference discretisation, the pricing problem can be formulated as a finite dimensional linear algebra problem involving the inverse of a non Hermitian time step matrix. Recent advances in quantum linear algebra algorithms, particularly the generalised quantum signal processing (GQSP)algorithm, enable matrix functions to be implemented through polynomial transformations of a suitable unitary or Hermitian form. In this paper, we develop a Hermitian block embedding method that enables GQSP to be applied to the two dimensional Black Scholes equation. Numerical simulations for two asset European call options are performed to evaluate the proposed approach. GQSP based solutions are benchmarked against the classical polynomial approximation with backward Euler finite difference method, showing close agreement. This indicates that the Hermitian block embedding construction accurately captures the dynamics of the original non Hermitian operator. These results demonstrate the feasibility of combining Hermitian block embeddings with GQSP for multidimensional Black Scholes problems and provide a proof of principle for applying modern quantum linear algebra techniques to option pricing.
This paper investigates the performance of the emerging non-variational Quantum Walk-based Optimisation Algorithm (NV-QWOA) for solving small instances of the Quadratic Assignment Problem (QAP). NV-QWOA is benchmarked against classical heuristics, the MaxMin Ant System (MMAS) and Greedy Local Search (GLS), as well as the Grover quantum search algorithm, which serves as a quantum baseline. Performance is evaluated using two metrics: the number of objective function evaluations and the number of algorithm iterations required to consistently reach optimal or near optimal solutions across QAP instances with 5 to 10 facilities. The motivation for this study stems from limitations of both classical exact methods and current quantum algorithms. Variational Quantum Algorithms (VQAs), such as QAOA and VQE, while widely studied, suffer from costly parameter tuning and barren plateaus that hinder convergence. By adopting a non-variational approach, this work explores a potentially more efficient and scalable quantum strategy for combinatorial optimisation. The results provide a direct comparative analysis between classical and quantum frameworks, characterising the average case performance of NV-QWOA. Our findings highlight the practical utility of quantum walks for complex combinatorial problems and establish a foundation for future quantum optimisation algorithms.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate for achieving quantum advantage in combinatorial optimization on Near-Term Intermediate-Scale Quantum (NISQ) devices. However, random initialization of the variational parameters typically leads to vanishing gradients, rendering standard variational optimization ineffective. This paper provides a comparative performance analysis of two distinct strategies designed to improve trainability: Lie algebraic pretraining framework that uses Lie-algebraic classical simulation to find near-optimal initializations, and non-variational QWOA (NV-QWOA) that targets a restrict parameter subspace covered by 3 hyperparameters. We benchmark both methods on the unweighted Maxcut problem using a circuit depth of p=256 across 200 Erdős-Rényi and 200 3-regular graphs, each with 16 vertices. Both approaches significantly improve upon the standard randomly initialized QWOA. NV-QWOA attains a mean approximation ratio of 98.9\% in just 60 iterations, while the Lie-algebraic pretrained QWOA improves to 77.71\% after 500 iterations. That optimization proceeds more quickly for NV-QWOA is not surprising given its significantly smaller parameter space, however, that an algorithm with so few tunable parameters reliably finds near-optimal solutions is remarkable. These findings suggest that the structured parameterization of NV-QWOA offers a more robust training approach than pretraining on lower-dimensional auxiliary problems. Future work is needed to confirm scaling to larger problem sizes and to asses generalization to other problem classes.
Quantum state preparation represents a critical bottleneck for a broad class of quantum algorithms. In this work, we introduce the Schmidt Spectrum Optimisation (SSO) algorithm as an efficient and scalable approach for preparing quantum states described by Matrix Product States (MPS). The SSO algorithm employs a preparation-by-disentangling strategy by optimising circuit layers of two-qubit gates to progressively remove entanglement from a target state. Each circuit layer is computed sequentially and efficiently on a classical computer using tensor network optimisation techniques. Once the target state has been successfully disentangled, a quantum state-preparation circuit is formed by reversing the sequence of optimised disentangling layers. Across benchmarks including random MPS and MPS approximations to the ground-states of local Hamiltonians, we find that the SSO algorithm significantly improves upon prior variational and disentangling-based approaches, highlighting its potential as a scalable framework for quantum state preparation.
Quantum Reservoir Computing (QRC) leverages the natural dynamics of quantum systems for information processing, without requiring a fault-tolerant quantum computer. In this work, we apply QRC within a hybrid quantum classical framework for image denoising. The quantum reservoir is implemented using a Rydberg atom array, while a classical neural network serves as the readout layer. To prepare the input, images are first compressed using Principal Component Analysis (PCA), reducing their dimensionality to match the size of the atom array. Each feature vector is encoded into local detuning parameters of a time-dependent Hamiltonian governing the Rydberg system. As the system evolves, it generates nonlinear embeddings through the measurement of observables across multiple time steps. These temporal embeddings capture complex correlations, which are fed into a classical neural network to reconstruct the denoised images. To evaluate performance, we compare this QRC-assisted model against a baseline architecture consisting of PCA followed by a dense neural network, trained under identical conditions. Our results show that the QRC-based approach achieves improved image sharpness and similar structural recovery compared to the PCA-based model. We demonstrate the practical viability of this framework through experiments on QuEra's Aquila neutral-atom processor, leveraging its programmable atom arrays to physically realize the reservoir dynamics.