Tradeoffs between quantum and classical resources in linear combination of unitaries

• URL: http://arxiv.org/abs/2512.06260v1
• Date: Sat, 06 Dec 2025 03:10:22 GMT
• Title: Tradeoffs between quantum and classical resources in linear combination of unitaries
• Authors: Kaito Wada, Hiroyuki Harada, Yasunari Suzuki, Yuuki Tokunaga, Naoki Yamamoto, Suguru Endo,
• Abstract summary: The linear combination of unitaries (LCU) algorithm is a building block of many quantum algorithms.<n>We propose a quantum algorithm that manages the tradeoff between sampling cost and the circuit size.
• Score: 0.07388859384645262
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The linear combination of unitaries (LCU) algorithm is a building block of many quantum algorithms. However, because LCU generally requires an ancillary system and complex controlled unitary operators, it is not regarded as a hardware-efficient routine. Recently, a randomized LCU implementation with many applications to early FTQC algorithms has been proposed that computes the same expectation values as the original LCU algorithm using a shallower quantum circuit with a single ancilla qubit, at the cost of a quadratically larger sampling overhead. In this work, we propose a quantum algorithm intermediate between the original and randomized LCU that manages the tradeoff between sampling cost and the circuit size. Our algorithm divides the set of unitary operators into several groups and then randomly samples LCU circuits from these groups to evaluate the target expectation value. Notably, we analytically prove an underlying monotonicity: larger group sizes entail smaller sampling overhead, by introducing a quantity called the reduction factor, which determines the sampling overhead across all grouping strategies. Our hybrid algorithm not only enables substantial reductions in circuit depth and ancilla-qubit usage while nearly maintaining the sampling overhead of LCU-based non-Hermitian dynamics simulators, but also achieves intermediate scaling between virtual and coherent quantum linear system solvers. It further provides a virtual ground-state preparation scheme that requires only a resettable single-ancilla qubit and asymptotically shows advantages in both virtual and coherent LCU methods. Finally, by viewing quantum error detection as an LCU process, our approach clarifies when conventional and virtual detection should be applied selectively, thereby balancing sampling and hardware overhead.

Related papers

• Compressed BC-LISTA via Low-Rank Convolutional Decomposition [47.15001096567547]
  We study Sparse Signal Recovery (SSR) methods for multichannel imaging with compressed forward and backward operators.<n>We propose a Compressed Block-Convolutional (CBC) measurement model based on a low-rank Convolutional Network (CNN) decomposition.
  arXiv  Detail & Related papers  (2026-01-30T16:33:51Z)
• A Posteriori Certification Framework for Generalized Quantum Arimoto-Blahut Algorithms [41.15017547767954]
  We introduce an a posteriori certification viewpoint for the generalized quantum Arimoto-Blahut (QAB) algorithm.<n>We prove a global convergence theorem showing that, under convexity and a substantially weaker numerically verifiable condition, the QAB iteration converges to the global minimizer.<n>As an application, we develop a certified iterative scheme for computing the quantum relative entropy of channels.
  arXiv  Detail & Related papers  (2026-01-14T09:10:41Z)
• Neural Guided Sampling for Quantum Circuit Optimization [26.90377134346014]
  Translating a quantum circuit on a specific hardware topology with a reduced set of available gates, also known as transpilation, comes with a substantial increase in the length of the equivalent circuit.<n>One method to address efficient transpilation is based on approaches known from optimization, e.g. by using random sampling and token replacement strategies.<n>Here, we propose in this work 2D neural guided sampling. Thus, given a 2D representation of a quantum circuit, a neural network predicts groups of gates in the quantum circuit, which are likely reducible.
  arXiv  Detail & Related papers  (2025-10-14T12:09:05Z)
• Randomized Quantum Singular Value Transformation [18.660349597156266]
  We introduce the first randomized algorithms for Quantum Singular Value Transformation (QSVT)<n>Standard implementations of QSVT rely on block encodings of the Hamiltonian, requiring a logarithmic number of ancilla qubits, intricate multi-qubit control, and circuit depth scaling linearly with the number of Hamiltonian terms.<n>Our algorithms use only a single ancilla qubit and entirely avoid block encodings.
  arXiv  Detail & Related papers  (2025-10-08T10:14:15Z)
• Compensating connectivity restrictions in quantum annealers via splitting and linearization techniques [26.214048364226365]
  We present an iterative algorithm that does not need additional qubits but instead efficiently uses the available connectivity.<n>We present a weak monotonicity proof and benchmark our algorithm against the default minor-embedding algorithm on the D-Wave quantum annealer.<n>We also confirm the practicality of our method with experiments on the D-Wave Advantage quantum annealer.
  arXiv  Detail & Related papers  (2025-07-16T18:00:09Z)
• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  Branch-and-bound algorithms effectively solve convex optimization problems, relying on the relaxation the objective function to obtain tight lower bounds.<n>We propose a branch-and-bound digitized counterdiabatic quantum optimization (BB-DCQO) algorithm that addresses the relaxation difficulties.
  arXiv  Detail & Related papers  (2025-04-21T18:19:19Z)
• Fast Expectation Value Calculation Speedup of Quantum Approximate Optimization Algorithm: HoLCUs QAOA [55.2480439325792]
  We present a new method for calculating expectation values of operators that can be expressed as a linear combination of unitary (LCU) operators.<n>This method is general for any quantum algorithm and is of particular interest in the acceleration of variational quantum algorithms.
  arXiv  Detail & Related papers  (2025-03-03T17:15:23Z)
• Dynamical cluster-based optimization of tensor network algorithms for quantum circuit simulations [0.0]
  We introduce a variation of the standard TEBD algorithm, "cluster-TEBD", which dynamically arranges qubits into entanglement clusters, enabling the exact contraction of multiple circuit layers in a single time step.<n>We analyze the performances of these enhanced algorithms in simulating both stabilizer and non-stabilizer random circuits, with up to $1000$ qubits and $100$ layers of Clifford and non-Clifford gates, and in simulating Shor's quantum algorithm with tens of thousands of layers.
  arXiv  Detail & Related papers  (2025-02-26T16:49:11Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Block encoding bosons by signal processing [0.0]
  We demonstrate that QSP-based techniques, such as Quantum Singular Value Transformation (QSVT) and Quantum Eigenvalue Transformation for Unitary Matrices (QETU) can themselves be efficiently utilized for BE implementation.<n>We present several examples of using QSVT and QETU algorithms, along with their combinations, to block encode Hamiltonians for lattice bosons.<n>We find that, while using QSVT for BE results in the best gate count scaling with the number of qubits per site, LOVE-LCU outperforms all other methods for operators acting on up to $lesssim11$ qubits.
  arXiv  Detail & Related papers  (2024-08-29T18:00:02Z)
• Non-Unitary Quantum Machine Learning [0.0]
  We introduce several probabilistic quantum algorithms that overcome the normal unitary restrictions in quantum machine learning. We show that residual connections between layers of a variational ansatz can prevent barren plateaus in models which would otherwise contain them. We also demonstrate a novel rotationally invariant encoding for point cloud data via Schur-Weyl duality.
  arXiv  Detail & Related papers  (2024-05-27T17:42:02Z)
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers [0.0]
  We develop three new methods to implement any Linear Combination of Unitaries (LCU) The first method estimates expectation values of observables with respect to any quantum state prepared by an LCU procedure. The second approach is a simple, physically motivated, continuous-time analogue of LCU, tailored to hybrid qubit-qumode systems. The third method (Ancilla-free LCU) requires no ancilla qubit at all and is useful when we are interested in the projection of a quantum state.
  arXiv  Detail & Related papers  (2023-02-27T07:15:14Z)
• Iterative Qubit Coupled Cluster using only Clifford circuits [36.136619420474766]
  An ideal state preparation protocol can be characterized by being easily generated classically. We propose a method that meets these requirements by introducing a variant of the iterative qubit coupled cluster (iQCC) We demonstrate the algorithm's correctness in ground-state simulations and extend our study to complex systems like the titanium-based compound Ti(C5H5)(CH3)3 with a (20, 20) active space.
  arXiv  Detail & Related papers  (2022-11-18T20:31:10Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs) We propose a new protocol for approximating TN states using realistic quantum circuits. Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
  arXiv  Detail & Related papers  (2022-09-01T17:08:41Z)

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.