Quantum Programmable Reflections

• URL: http://arxiv.org/abs/2411.03648v1
• Date: Wed, 06 Nov 2024 04:12:42 GMT
• Title: Quantum Programmable Reflections
• Authors: Eddie Schoute, Dmitry Grinko, Yigit Subasi, Tyler Volkoff,
• Abstract summary: The present work focuses on a class of simple programmable quantum processors for implementing reflection operators. We identify the worst-case optimal algorithm among all processors of the form $texttr_textProgram[V (lvertphiranglelanglephirvert otimes (lvertpsiranglelanglepsirvert)otimes n) Vdagger]$ where the algorithm $V$ is a unitary linear combination of permutations.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Similar to a classical processor, which is an algorithm for reading a program and executing its instructions on input data, a universal programmable quantum processor is a fixed quantum channel that reads a quantum program $\lvert\psi_{U}\rangle$ that causes the processor to approximately apply an arbitrary unitary $U$ to a quantum data register. The present work focuses on a class of simple programmable quantum processors for implementing reflection operators, i.e. $U = e^{i \pi \lvert\psi\rangle\langle\psi\rvert}$ for an arbitrary pure state $\lvert\psi\rangle$ of finite dimension $d$. Unlike quantum programs that assume query access to $U$, our program takes the form of independent copies of the state to be reflected about $\lvert\psi_U\rangle = \lvert\psi\rangle^{\otimes n}$. We then identify the worst-case optimal algorithm among all processors of the form $\text{tr}_{\text{Program}}[V (\lvert\phi\rangle\langle\phi\rvert \otimes (\lvert\psi\rangle\langle\psi\rvert)^{\otimes n}) V^\dagger]$ where the algorithm $V$ is a unitary linear combination of permutations. By generalizing these algorithms to processors for arbitrary-angle rotations, $e^{i \alpha \lvert\psi\rangle\langle\psi\rvert}$ for $\alpha \in \mathbb R$, we give a construction for a universal programmable processor with better scaling in $d$. For programming reflections, we obtain a tight analytical lower bound on the program dimension by bounding the Holevo information of an ensemble of reflections applied to an entangled probe state. The lower bound makes use of a block decomposition of the uniform ensemble of reflected states with respect to irreps of the partially transposed permutation matrix algebra, and two representation-theoretic conjectures based on extensive numerical evidence.

Related papers

• Quantum oracles for the finite element method [45.200826131319815]
  This study examines the quantum routines required for the implementation of oracles used in the block-encoding of the $N times N stiffness and mass matrices. We show how to construct the necessary oracles, which require the calculation of element geometry, square root and the implementation of conditional operations.
  arXiv  Detail & Related papers  (2025-04-28T14:28:31Z)
• Distributed quantum algorithm for divergence estimation and beyond [16.651306526783564]
  We propose a distributed quantum algorithm framework to compute $rm Tr(f(A)g(B))$ within an additive error $varepsilon$. This framework holds broad applicability across a range of distributed quantum computing tasks.
  arXiv  Detail & Related papers  (2025-03-12T14:28:22Z)
• Quantum algorithm for the gradient of a logarithm-determinant [0.0]
  The inverse of a sparse-rank input operator may be determined efficiently. Measuring an expectation value of the quantum state--instead of all $N2$ elements of the input operator--can be accomplished in $O(ksigma)$ time. The algorithm is envisioned for fully error-corrected quantum computers but may be implementable on near-term machines.
  arXiv  Detail & Related papers  (2025-01-16T09:39:31Z)
• Learning quantum states prepared by shallow circuits in polynomial time [1.127500169412367]
  We learn a constant depth quantum circuit that prepares $vertpsirangle$ on a finite-dimensional lattice. The algorithm extends to the case when the depth of $U$ is $mathrmpolylog(n)$, with a quasi-polynomial run-time. As an application, we give an efficient algorithm to test whether an unknown quantum state on a lattice has low or high quantum circuit complexity.
  arXiv  Detail & Related papers  (2024-10-31T04:12:49Z)
• Simplified projection on total spin zero for state preparation on quantum computers [0.5461938536945723]
  We introduce a simple algorithm for projecting on $J=0$ states of a many-body system.<n>Our approach performs the necessary projections using the one-body operators $J_x$ and $J_z$.<n>Given the reduced complexity in terms of gates, this approach can be used to prepare approximate ground states of even-even nuclei.
  arXiv  Detail & Related papers  (2024-10-03T17:44:24Z)
• 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)
• 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 hashing algorithm implementation [0.0]
  We implement a quantum hashing algorithm which is based on a fingerprinting technique presented by Ambainis and Frievalds, 1988, on gate-based quantum computers. We consider 16-qubit and 27-qubit IBMQ computers with the special graphs of qubits representing nearest neighbor architecture that is not Linear Nearest Neighbor (LNN) one.
  arXiv  Detail & Related papers  (2024-07-14T09:41:16Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Purely quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  We propose quantum algorithms for the computation of the determinant and inverse of an $(N-1) times (N-1)$ matrix. This approach is a straightforward modification of the existing algorithm for determining the determinant of an $N times N$ matrix. We provide suitable circuit designs for all three algorithms, each estimated to require $O(N log N)$ in terms of space.
  arXiv  Detail & Related papers  (2024-01-29T23:23:27Z)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPs were introduced by Macchi as a model in quantum optics the 1970s. Most applications require sampling from a DPP, and given their quantum origin, it is natural to wonder whether sampling a DPP on a classical computer is easier than on a classical one. Vanilla sampling consists in two steps, of respective costs $mathcalO(N3)$ and $mathcalO(Nr2)$ operations on a classical computer, where $r$ is the rank of the kernel matrix.
  arXiv  Detail & Related papers  (2023-05-25T08:43:11Z)
• Quantum majority vote [1.43494686131174]
  Majority vote is a basic method for amplifying correct outcomes that is widely used in computer science and beyond. We show that an optimal algorithm for this problem achieves worst-case fidelity of $1/2 + Theta (1/sqrtn)$. Under the promise that at least $2/3$ of the input qubits are in the majority state, the fidelity increases to $1 - Theta (1/n)$ and approaches $1$ as $n$ increases.
  arXiv  Detail & Related papers  (2022-11-21T18:47:46Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits [20.270300647783003]
  Controlled quantum state preparation (CQSP) aims to provide the transformation of $|irangle |0nrangle to |irangle |psi_irangle $ for all $iin 0,1k$ for the given $n$-qubit states. We construct a quantum circuit for implementing CQSP, with depth $Oleft(n+k+frac2n+kn+k+mright)$ and size $Oleft(2n+kright)$
  arXiv  Detail & Related papers  (2022-02-23T04:19:57Z)
• How to simulate quantum measurement without computing marginals [3.222802562733787]
  We describe and analyze algorithms for classically computation measurement of an $n$-qubit quantum state $psi$ in the standard basis. Our algorithms reduce the sampling task to computing poly(n)$ amplitudes of $n$-qubit states.
  arXiv  Detail & Related papers  (2021-12-15T21:44:05Z)
• 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 algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• 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)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)

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.