Logarithmic-Depth Quantum Circuits for Hamming Weight Projections

• URL: http://arxiv.org/abs/2404.07151v3
• Date: Thu, 24 Oct 2024 14:02:43 GMT
• Title: Logarithmic-Depth Quantum Circuits for Hamming Weight Projections
• Authors: Soorya Rethinasamy, Margarite L. LaBorde, Mark M. Wilde,
• Abstract summary: We propose several quantum algorithms that realize a coherent Hamming weight projective measurement on an input pure state. We analyze a depth-width trade-off for the corresponding quantum circuits, allowing for a depth reduction of the circuits at the cost of more control qubits.
• Score: 3.481985817302898
• License:
• Abstract: A pure state of fixed Hamming weight is a superposition of computational basis states such that each bitstring in the superposition has the same number of ones. Given a Hilbert space of the form $\mathcal{H} = (\mathbb{C}_2)^{\otimes n}$, or an $n$-qubit system, the identity operator can be decomposed as a sum of projectors onto subspaces of fixed Hamming weight. In this work, we propose several quantum algorithms that realize a coherent Hamming weight projective measurement on an input pure state, meaning that the post-measurement state of the algorithm is the projection of the input state onto the corresponding subspace of fixed Hamming weight. We analyze a depth-width trade-off for the corresponding quantum circuits, allowing for a depth reduction of the circuits at the cost of more control qubits. For an $n$-qubit input, the depth-optimal algorithm uses $O(n)$ control qubits and the corresponding circuit has depth $O(\log (n))$, assuming that we have the ability to perform qubit resets. Furthermore, the proposed algorithm construction uses only one- and two-qubit gates.

Related papers

• 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)
• Rank Is All You Need: Estimating the Trace of Powers of Density Matrices [1.5133368155322298]
  Estimating the trace of powers of identical $k$ density matrices is a crucial subroutine for many applications. Inspired by the Newton-Girard method, we developed an algorithm that uses only $mathcalO(r)$ qubits and $mathcalO(r)$ multi-qubit gates.
  arXiv  Detail & Related papers  (2024-08-01T06:23:52Z)
• Quantum encoder for fixed Hamming-weight subspaces [0.0]
  We present an exact $n$-qubit computational-basis amplitude encoder of real- or complex-principle data vectors of $d=binomnk$ provided in analytical form. We also perform an experimental proof-of-principle demonstration of our scheme on a commercial trapped-ion quantum computer.
  arXiv  Detail & Related papers  (2024-05-30T18:26:41Z)
• Polynomial-depth quantum algorithm for computing matrix determinant [46.13392585104221]
  We propose an algorithm for calculating the determinant of a square matrix, and construct a quantum circuit realizing it. Each row of the matrix is encoded as a pure state of some quantum system. The admitted matrix is therefore arbitrary up to the normalization of quantum states of those systems.
  arXiv  Detail & Related papers  (2024-01-29T23:23:27Z)
• A two-circuit approach to reducing quantum resources for the quantum lattice Boltzmann method [41.66129197681683]
  Current quantum algorithms for solving CFD problems use a single quantum circuit and, in some cases, lattice-based methods. We introduce the a novel multiple circuits algorithm that makes use of a quantum lattice Boltzmann method (QLBM) The problem is cast as a stream function--vorticity formulation of the 2D Navier-Stokes equations and verified and tested on a 2D lid-driven cavity flow.
  arXiv  Detail & Related papers  (2024-01-20T15:32:01Z)
• 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)
• QuIP: 2-Bit Quantization of Large Language Models With Guarantees [44.212441764241]
  This work studies post-training parameter quantization in large language models (LLMs) We introduce quantization with incoherence processing (QuIP), a new method based on the insight that quantization benefits from $textitincoherent$ weight and Hessian matrices.
  arXiv  Detail & Related papers  (2023-07-25T07:44:06Z)
• Digital-analog co-design of the Harrow-Hassidim-Lloyd algorithm [0.0]
  Harrow-Hassidim-Lloyd quantum algorithm was proposed to solve linear systems of equations $Avecx = vecb$. There is not an explicit quantum circuit for the subroutine which maps the inverse of the problem matrix $A$ into an ancillary qubit. We present a co-designed quantum processor which reduces the depth of the algorithm.
  arXiv  Detail & Related papers  (2022-07-27T13:58:13Z)
• K-sparse Pure State Tomography with Phase Estimation [1.2183405753834557]
  Quantum state tomography (QST) for reconstructing pure states requires exponentially increasing resources and measurements with the number of qubits. QST reconstruction for any pure state composed of the superposition of $K$ different computational basis states of $n$bits in a specific measurement set-up is presented.
  arXiv  Detail & Related papers  (2021-11-08T09:43:12Z)
• Low-depth Quantum State Preparation [3.540171881768714]
  A crucial subroutine in quantum computing is to load the classical data of $N$ complex numbers into the amplitude of a superposed $n=lceil logNrceil$-qubit state. Here we investigate this space-time tradeoff in quantum state preparation with classical data. We propose quantum algorithms with $mathcal O(n2)$ circuit depth to encode any $N$ complex numbers.
  arXiv  Detail & Related papers  (2021-02-15T13:11:43Z)
• 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.