Toward speedup without quantum coherent access

• URL: http://arxiv.org/abs/2602.20781v1
• Date: Tue, 24 Feb 2026 11:21:44 GMT
• Title: Toward speedup without quantum coherent access
• Authors: Nhat A. Nghiem,
• Abstract summary: We propose a variant of quantum algorithms, leveraging both classical and quantum resources.<n>We show how to use it to tackle a wide range of problems, including principal component analysis, linear equation solving, Hamiltonian simulation, and data fitting.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Digital quantum simulation of many-body systems: Making the most of intermediate-scale, noisy quantum computers [51.56484100374058]
  This thesis is centered around simulating quantum dynamics on quantum devices.<n>We present an overview of the most relevant quantum algorithms for quantum dynamics.<n>We identify relevant problems within quantum dynamics that could benefit from quantum simulation in the near future.
  arXiv  Detail & Related papers  (2025-08-29T10:37:19Z)
• Quantum Algorithms Without Coherent Quantum Access [0.0]
  Most quantum speedups rely on a subroutine in which classical information can be accessed in a coherent quantum manner.<n>It has been shown that without such an access, the quantum computer cannot be stronger than the classical counterparts.<n>In this work, we develop several variants of quantum algorithms.
  arXiv  Detail & Related papers  (2025-03-04T11:24:28Z)
• QCircuitBench: A Large-Scale Dataset for Benchmarking Quantum Algorithm Design [63.02824918725805]
  Quantum computing is recognized for the significant speedup it offers over classical computing through quantum algorithms.<n>QCircuitBench is the first benchmark dataset designed to evaluate AI's capability in designing and implementing quantum algorithms.
  arXiv  Detail & Related papers  (2024-10-10T14:24:30Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• The curse of random quantum data [62.24825255497622]
  We quantify the performances of quantum machine learning in the landscape of quantum data. We find that the training efficiency and generalization capabilities in quantum machine learning will be exponentially suppressed with the increase in qubits. Our findings apply to both the quantum kernel method and the large-width limit of quantum neural networks.
  arXiv  Detail & Related papers  (2024-08-19T12:18:07Z)
• Tensor Quantum Programming [0.0]
  We develop an algorithm that encodes Matrix Product Operators into quantum circuits with a depth that depends linearly on the number of qubits. It demonstrates effectiveness on up to 50 qubits for several frequently encountered in differential equations, optimization problems, and quantum chemistry.
  arXiv  Detail & Related papers  (2024-03-20T10:44:00Z)
• A Quantum Algorithm Based Heuristic to Hide Sensitive Itemsets [1.8419202109872088]
  We present a quantum approach to solve a well-studied problem in the context of data sharing. We present results on experiments involving small datasets to illustrate how the problem could be solved using quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-12T20:44:46Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [88.57261102552016]
  The anticipated applications of quantum computers span across science and industry.<n>We present a survey of several potential application areas of quantum algorithms.<n>We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Quantum Machine Learning: from physics to software engineering [58.720142291102135]
  We show how classical machine learning approach can help improve the facilities of quantum computers. We discuss how quantum algorithms and quantum computers may be useful for solving classical machine learning tasks.
  arXiv  Detail & Related papers  (2023-01-04T23:37:45Z)
• Quantum communication complexity of linear regression [0.05076419064097732]
  We show that quantum computers have provable and exponential speedups in terms of communication for some fundamental linear algebra problems. We propose an efficient quantum protocol for quantum singular value transformation.
  arXiv  Detail & Related papers  (2022-10-04T13:27:01Z)
• Parametrized Complexity of Quantum Inspired Algorithms [0.0]
  Two promising areas of quantum algorithms are quantum machine learning and quantum optimization. Motivated by recent progress in quantum technologies and in particular quantum software, research and industrial communities have been trying to discover new applications of quantum algorithms.
  arXiv  Detail & Related papers  (2021-12-22T06:19:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.