Binary Tree Block Encoding of Classical Matrix

• URL: http://arxiv.org/abs/2504.05624v1
• Date: Tue, 08 Apr 2025 02:53:43 GMT
• Title: Binary Tree Block Encoding of Classical Matrix
• Authors: Zexian Li, Xiao-Ming Zhang, Chunlin Yang, Guofeng Zhang,
• Abstract summary: Block-encoding is a critical computation in quantum computing.<n>Our protocol is named Binary Tree Block-encoding (textttBITBLE)
• Score: 6.334095794072344
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Block-encoding is a critical subroutine in quantum computing, enabling the transformation of classical data into a matrix representation within a quantum circuit. The resource trade-offs in simulating a block-encoding can be quantified by the circuit size, the normalization factor, and the time and space complexity of parameter computation. Previous studies have primarily focused either on the time and memory complexity of computing the parameters, or on the circuit size and normalization factor in isolation, often neglecting the balance between these trade-offs. In early fault-tolerant quantum computers, the number of qubits is limited. For a classical matrix of size $2^{n}\times 2^{n}$, our approach not only improves the time of decoupling unitary for block-encoding with time complexity $\mathcal{O}(n2^{2n})$ and memory complexity $\Theta(2^{2n})$ using only a few ancilla qubits, but also demonstrates superior resource trade-offs. Our proposed block-encoding protocol is named Binary Tree Block-encoding (\texttt{BITBLE}). Under the benchmark, \textit{size metric}, defined by the product of the number of gates and the normalization factor, numerical experiments demonstrate the improvement of both resource trade-off and classical computing time efficiency of the \texttt{BITBLE} protocol. The algorithms are all open-source.

Related papers

• An Efficient Quantum Classifier Based on Hamiltonian Representations [50.467930253994155]
  Quantum machine learning (QML) is a discipline that seeks to transfer the advantages of quantum computing to data-driven tasks. We propose an efficient approach that circumvents the costs associated with data encoding by mapping inputs to a finite set of Pauli strings. We evaluate our approach on text and image classification tasks, against well-established classical and quantum models.
  arXiv  Detail & Related papers  (2025-04-13T11:49:53Z)
• Information Theoretic One-Time Programs from Geometrically Local $\text{QNC}_0$ Adversaries [0.0]
  We build one-time memories from random linear codes and quantum random access codes (QRACs) We place no restrictions on the adversary's classical computational power, number of qubits it can use, or the coherence time of its qubits. We leave open the question of whether one can construct a time information theoretically secure one-time memory from geometrically local quantum circuits.
  arXiv  Detail & Related papers  (2025-03-27T22:10:42Z)
• Extractors: QLDPC Architectures for Efficient Pauli-Based Computation [42.95092131256421]
  We propose a new primitive that can augment any QLDPC memory into a computational block well-suited for Pauli-based computation.<n>In particular, any logical Pauli operator supported on the memory can be fault-tolerantly measured in one logical cycle.<n>Our architecture can implement universal quantum circuits via parallel logical measurements.
  arXiv  Detail & Related papers  (2025-03-13T14:07:40Z)
• Entanglement-Assisted Coding for Arbitrary Linear Computations Over a Quantum MAC [34.32444379837011]
  We study a linear computation problem over a quantum multiple access channel (LC-QMAC)<n>We propose an achievable scheme for LC-QMAC based on the stabilizer formalism and the ideas from entanglement-assisted quantum error-correcting codes (EAQECC)
  arXiv  Detail & Related papers  (2025-01-27T18:35:33Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose arbitrary exponentials into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions. We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Linear Circuit Synthesis using Weighted Steiner Trees [45.11082946405984]
  CNOT circuits are a common building block of general quantum circuits. This article presents state-of-the-art algorithms for optimizing the number of CNOT gates. A simulated evaluation shows that the suggested is almost always beneficial and reduces the number of CNOT gates by up to 10%.
  arXiv  Detail & Related papers  (2024-08-07T19:51:22Z)
• Block encoding of matrix product operators [0.0]
  We present a procedure to block-encode a Hamiltonian based on its matrix product operator (MPO) representation. More specifically, we encode every MPO tensor in a larger unitary of dimension $D+2$, where $D = lceillog(chi)rceil$ is the number of subsequently contracted qubits that scales logarithmically with the virtual bond dimension.
  arXiv  Detail & Related papers  (2023-12-14T12:34:24Z)
• Logical quantum processor based on reconfigurable atom arrays [27.489364850707926]
  We report the realization of a programmable quantum processor based on encoded logical qubits operating with up to 280 physical qubits. Results herald the advent of early error-corrected quantum computation.
  arXiv  Detail & Related papers  (2023-12-07T01:54:45Z)
• Circuit complexity of quantum access models for encoding classical data [4.727325187683489]
  We study the Clifford$+T$ complexity of constructing some typical quantum access models. We show that both sparse-access input models and block-encoding require nearly linear circuit complexities. Our protocols are built upon improved quantum state preparation and a selective oracle for Pauli strings.
  arXiv  Detail & Related papers  (2023-11-19T16:23:57Z)
• Training Multi-layer Neural Networks on Ising Machine [41.95720316032297]
  This paper proposes an Ising learning algorithm to train quantized neural network (QNN) As far as we know, this is the first algorithm to train multi-layer feedforward networks on Ising machines.
  arXiv  Detail & Related papers  (2023-11-06T04:09:15Z)
• An Improved QFT-Based Quantum Comparator and Extended Modular Arithmetic Using One Ancilla Qubit [4.314578336989336]
  We propose a quantum-classical comparator based on the quantum Fourier transform (QFT) Proposed operators only require one ancilla qubit, which is optimal for qubit resources. The proposed algorithms reduce computing resources and make them valuable for Noisy Intermediate-Scale Quantum (NISQ) computers.
  arXiv  Detail & Related papers  (2023-05-16T02:09:41Z)
• Quantum algorithms for classical Boolean functions via adaptive measurements: Exponential reductions in space-time resources [0.0]
  We formulate computation of a variety of Boolean functions in the framework of adaptive measurement-based quantum computation.<n>Our results constitute an alternative proof of an old theorem regarding an oracular separation between the power of constant-depth quantum circuits and constant-depth classical circuits.
  arXiv  Detail & Related papers  (2022-11-02T16:33:32Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• FABLE: Fast Approximate Quantum Circuits for Block-Encodings [0.0]
  We propose FABLE, a method to generate approximate quantum circuits for block-encodings of matrices in a fast manner. FABLE circuits have a simple structure and are directly formulated in terms of one- and two-qubit gates. We show that FABLE circuits can be compressed and sparsified.
  arXiv  Detail & Related papers  (2022-04-29T21:06:07Z)
• Quantum Compiling by Deep Reinforcement Learning [30.189226681406392]
  The architecture of circuital quantum computers requires layers devoted to compiling high-level quantum algorithms into lower-level circuits of quantum gates. The general problem of quantum compiling is to approximate any unitary transformation that describes the quantum computation, as a sequence of elements selected from a finite base of universal quantum gates. We exploit the deep reinforcement learning method as an alternative strategy, which has a significantly different trade-off between search time and exploitation time.
  arXiv  Detail & Related papers  (2021-05-31T15:32:15Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• 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)

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.