Towards identifying possible fault-tolerant advantage of quantum linear system algorithms in terms of space, time and energy

• URL: http://arxiv.org/abs/2502.11239v2
• Date: Tue, 18 Feb 2025 03:35:48 GMT
• Title: Towards identifying possible fault-tolerant advantage of quantum linear system algorithms in terms of space, time and energy
• Authors: Yue Tu, Mark Dubynskyi, Mohammadhossein Mohammadisiahroudi, Ekaterina Riashchentceva, Jinglei Cheng, Dmitry Ryashchentsev, Tamás Terlaky, Junyu Liu,
• Abstract summary: We provide a detailed estimation of space, time, and energy resources for fault-tolerant superconducting devices.<n>Our work quantitatively determine how advanced a fault-tolerant quantum computer should be to achieve possible, significant benefits on problems related to real-world.
• Score: 4.809611965725093
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum computing, a prominent non-Von Neumann paradigm beyond Moore's law, can offer superpolynomial speedups for certain problems. Yet its advantages in efficiency for tasks like machine learning remain under investigation, and quantum noise complicates resource estimations and classical comparisons. We provide a detailed estimation of space, time, and energy resources for fault-tolerant superconducting devices running the Harrow-Hassidim-Lloyd (HHL) algorithm, a quantum linear system solver relevant to linear algebra and machine learning. Excluding memory and data transfer, possible quantum advantages over the classical conjugate gradient method could emerge at $N \approx 2^{33} \sim 2^{48}$ or even lower, requiring ${O}(10^5)$ physical qubits, ${O}(10^{12}\sim10^{13})$ Joules, and ${O}(10^6)$ seconds under surface code fault-tolerance with three types of magic state distillation (15-1, 116-12, 225-1). Key parameters include condition number, sparsity, and precision $\kappa, s\approx{O}(10\sim100)$, $\epsilon\sim0.01$, and physical error $10^{-5}$. Our resource estimator adjusts $N, \kappa, s, \epsilon$, providing a map of quantum-classical boundaries and revealing where a practical quantum advantage may arise. Our work quantitatively determine how advanced a fault-tolerant quantum computer should be to achieve possible, significant benefits on problems related to real-world.

Related papers

• Augmenting Simulated Noisy Quantum Data Collection by Orders of Magnitude Using Pre-Trajectory Sampling with Batched Execution [47.60253809426628]
  We present the Pre-Trajectory Sampling technique, increasing efficiency and utility of trajectory simulations by tailoring error types. We generate massive datasets of one trillion and one million shots, respectively.
  arXiv  Detail & Related papers  (2025-04-22T22:36:18Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Single-Layer Digitized-Counterdiabatic Quantum Optimization for $p$-spin Models [8.463477025989542]
  We take advantage of a digitized-counterdiabatic quantum optimization (DCQO) algorithm to find an optimal solution of the $p$-spin model up to 4-local interactions. By further optimizing parameters using variational methods, we solve with unit accuracy 2-spin, 3-spin, and 4-spin problems for $100%$, $93%$, and $83%$ of instances, respectively.
  arXiv  Detail & Related papers  (2023-11-11T22:49:16Z)
• The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts [0.0]
  We give the first non-asymptotic computation of the cost of encoding the solution to general linear ordinary differential equations into quantum states. We show that the stability properties of a large class of classical dynamics allow their fast-forwarding. We find that the history state can always be output with complexity $O(T1/2)$ for any stable linear system.
  arXiv  Detail & Related papers  (2023-09-14T17:25:43Z)
• Fast Flux-Activated Leakage Reduction for Superconducting Quantum Circuits [84.60542868688235]
  leakage out of the computational subspace arising from the multi-level structure of qubit implementations. We present a resource-efficient universal leakage reduction unit for superconducting qubits using parametric flux modulation. We demonstrate that using the leakage reduction unit in repeated weight-two stabilizer measurements reduces the total number of detected errors in a scalable fashion.
  arXiv  Detail & Related papers  (2023-09-13T16:21:32Z)
• Fundamental causal bounds of quantum random access memories [13.19534468575575]
  We study the intrinsic bounds of rapid quantum memories based on causality. We show that QRAM can accommodate up to $mathcalO(107)$ logical qubits in 1 dimension, $mathcalO(1015)$ to $mathcalO(1020)$ in various 2D architectures, and $mathcalO(1024)$ in 3 dimensions.
  arXiv  Detail & Related papers  (2023-07-25T12:40:48Z)
• Classical Chaos in Quantum Computers [39.58317527488534]
  Current-day quantum processors, comprising 50-100 qubits, operate outside the range of quantum simulation on classical computers. We demonstrate that the simulation of classical limits can be a potent diagnostic tool potentially mitigating this problem. We find that classical and quantum simulations lead to similar stability metrics in systems with $mathcalO$ transmons.
  arXiv  Detail & Related papers  (2023-04-27T18:00:04Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Unimon qubit [42.83899285555746]
  Superconducting qubits are one of the most promising candidates to implement quantum computers. Here, we introduce and demonstrate a superconducting-qubit type, the unimon, which combines the desired properties of high non-linearity, full insensitivity to dc charge noise, insensitivity to flux noise, and a simple structure consisting only of a single Josephson junction in a resonator.
  arXiv  Detail & Related papers  (2022-03-11T12:57:43Z)
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications [10.436969366019015]
  We show that any $Theta(n)$-depth circuit can be prepared with a $Theta(log(nd)) with $O(ndlog d)$ ancillary qubits. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories.
  arXiv  Detail & Related papers  (2022-01-27T13:16:30Z)
• Emulating Quantum Interference with Generalized Ising Machines [0.0]
  This paper presents an exact and general procedure for mapping any sequence of quantum gates onto a network of probabilistic p-bits. We can view this structure as a Boltzmann machine whose states each represent a Feynman path leading from an initial configuration of qubits to a final configuration. Our results for mapping an arbitrary quantum circuit to a Boltzmann machine with a complex energy function should help push the boundaries of the simulability of quantum circuits with probabilistic resources.
  arXiv  Detail & Related papers  (2020-07-14T22:10:29Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• What limits the simulation of quantum computers? [5.22339562024796]
  We demonstrate that real quantum computers can be simulated at a tiny fraction of the cost that would be needed for a perfect quantum computer. Our algorithms compress the representations of quantum wavefunctions using matrix product states (MPS), which capture states with low to moderate entanglement very accurately. For a two dimensional array of $N=54$ qubits and a circuit with Control-Z gates, error rates better than state-of-the-art devices can be obtained on a laptop in a few hours.
  arXiv  Detail & Related papers  (2020-02-18T17:00:39Z)

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.