Quantum Communication Complexity of L2-Regularized Linear Regression Protocols

• URL: http://arxiv.org/abs/2508.16141v2
• Date: Wed, 10 Sep 2025 06:50:24 GMT
• Title: Quantum Communication Complexity of L2-Regularized Linear Regression Protocols
• Authors: Sayaki Matsushita,
• Abstract summary: This paper investigates distributed linear regression in the quantum coordinator model.<n>We propose improved and extended quantum protocols for solving both ordinary (unregularized) and L2-regularized (Tikhonov) least squares problems.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Linear regression is fundamental to statistical analysis and machine learning, but its application to large-scale datasets necessitates distributed computing. The problem also arises in quantum computing, where handling extensive data requires distributed approaches. This paper investigates distributed linear regression in the quantum coordinator model. Building upon the distributed quantum least squares protocol developed by Montanaro and Shao, we propose improved and extended quantum protocols for solving both ordinary (unregularized) and L2-regularized (Tikhonov) least squares problems. For ordinary least squares methods, our protocol reduces the quantum communication complexity compared to the previous protocol. In particular, this yields a quadratic improvement in the number of digits of precision required for the generated quantum states. This improvement is achieved by incorporating advanced techniques such as branch marking and branch-marked gapped phase estimation developed by Low and Su. Additionally, we introduce a quantum protocol for the L2-regularized least squares problem and derive its quantum communication complexity.

Related papers

• Dual channel multi-product formulas [5.0703493871642715]
  We propose a dual-channel multi-product formula that achieves a two-fold improvement in Trotter error scaling.<n>We demonstrate that, for a fixed CNOT count as a measure of quantum circuit, our proposal yields significantly smaller algorithmic errors.
  arXiv  Detail & Related papers  (2026-02-02T06:48:38Z)
• Accelerating Transpilation in Quantum Machine Learning with Haiqu's Rivet-transpiler [45.88028371034407]
  We develop the Rivet transpiler, which accelerates transpilation by reusing previously transpiled circuits.<n>We demonstrate up to 600% improvement in transpilation time for quantum layerwise learning.
  arXiv  Detail & Related papers  (2025-08-29T06:00:29Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Detecting Errors in a Quantum Network with Pauli Checks [2.692338496884547]
  We apply the quantum error detection scheme Pauli check sandwiching (PCS) to quantum networks by turning it into a distributed multiparty protocol.<n>PCS provides protection on the targeted qubits and generally requires less resource overhead than standard quantum error correction and detection codes.
  arXiv  Detail & Related papers  (2024-05-24T05:56:21Z)
• Near-Term Distributed Quantum Computation using Mean-Field Corrections and Auxiliary Qubits [77.04894470683776]
  We propose near-term distributed quantum computing that involve limited information transfer and conservative entanglement production. We build upon these concepts to produce an approximate circuit-cutting technique for the fragmented pre-training of variational quantum algorithms.
  arXiv  Detail & Related papers  (2023-09-11T18:00:00Z)
• Explainable quantum regression algorithm with encoded data structure [0.0]
  In this paper, we construct the first interpretable quantum regression algorithm.<n>The encoded data structure reduces the time complexity of computing the regression map.<n>We envision potential quantum utilities with multi-qubit gates implemented in neutral cold atoms and ions.
  arXiv  Detail & Related papers  (2023-07-07T00:30:16Z)
• Compilation of a simple chemistry application to quantum error correction primitives [44.99833362998488]
  We estimate the resources required to fault-tolerantly perform quantum phase estimation on a minimal chemical example. We find that implementing even a simple chemistry circuit requires 1,000 qubits and 2,300 quantum error correction rounds.
  arXiv  Detail & Related papers  (2023-07-06T18:00:10Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• Benchmarking multi-qubit gates -- I: Metrological aspects [0.0]
  benchmarking hardware errors in quantum computers has drawn significant attention lately. Existing benchmarks for digital quantum computers involve averaging the global fidelity over a large set of quantum circuits. We develop a new figure-of-merit suitable for multi-qubit quantum gates based on the reduced Choi matrix.
  arXiv  Detail & Related papers  (2022-10-09T19:36:21Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Large-scale quantum hybrid solution for linear systems of equations [0.0]
  We introduce and implement a hybrid quantum algorithm for solving linear systems of equations with exponential speedup. We solve experimentally a $217$-dimensional problem on superconducting IBMQ devices, a record for linear system solution on quantum computers.
  arXiv  Detail & Related papers  (2020-03-28T11:23:05Z)

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.