An efficient quantum algorithm for preparation of uniform quantum superposition states

• URL: http://arxiv.org/abs/2306.11747v1
• Date: Sun, 18 Jun 2023 17:59:00 GMT
• Title: An efficient quantum algorithm for preparation of uniform quantum superposition states
• Authors: Alok Shukla, Prakash Vedula
• Abstract summary: We show that the superposition state $ketPsi$ can be efficiently prepared with a gate complexity and circuit depth of only $O(logM)$ for all $M$. Neither ancillabits nor any quantum gates with multiple controls are needed in our approach for creating the uniform superposition state $ketPsi$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum state preparation involving a uniform superposition over a non-empty subset of $n$-qubit computational basis states is an important and challenging step in many quantum computation algorithms and applications. In this work, we address the problem of preparation of a uniform superposition state of the form $\ket{\Psi} = \frac{1}{\sqrt{M}}\sum_{j = 0}^{M - 1} \ket{j}$, where $M$ denotes the number of distinct states in the superposition state and $2 \leq M \leq 2^n$. We show that the superposition state $\ket{\Psi}$ can be efficiently prepared with a gate complexity and circuit depth of only $O(\log_2~M)$ for all $M$. This demonstrates an exponential reduction in gate complexity in comparison to other existing approaches in the literature for the general case of this problem. Another advantage of the proposed approach is that it requires only $n=\ceil{\log_2~M}$ qubits. Furthermore, neither ancilla qubits nor any quantum gates with multiple controls are needed in our approach for creating the uniform superposition state $\ket{\Psi}$. It is also shown that a broad class of nonuniform superposition states that involve a mixture of uniform superposition states can also be efficiently created with the same circuit configuration that is used for creating the uniform superposition state $\ket{\Psi}$ described earlier, but with modified parameters.

Related papers

• Circuit Complexity of Sparse Quantum State Preparation [0.0]
  We show that any $n$-qubit $d$-sparse quantum state can be prepared by a quantum circuit of size $O(fracdnlog d)$ and depth $Theta(log dn)$ using at most $O(fracndlog d )$ ancillary qubits. We also establish the lower bound $Omega(fracdnlog(n + m) + log d + n)$ on the circuit size with $m$ ancillary qubits available.
  arXiv  Detail & Related papers  (2024-06-23T15:28:20Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
  A subset state with respect to $S$, a subset of the computational basis, is [ frac1sqrt|S|sum_iin S |irangle. We show that for any fixed subset size $|S|=s$ such that $s = 2n/omega(mathrmpoly(n))$ and $s=omega(mathrmpoly(n))$, a random subset state is information-theoretically indistinguishable from a Haar random state even provided
  arXiv  Detail & Related papers  (2023-12-23T15:52:46Z)
• Quantum mutual information redistribution by Number Partitioning algorithm [9.818805141128935]
  We show how a bipartite unitary transformation $U_AB$ redistributes quantum mutual information with the third party $C$ in a tripartite pure state $|psirangle_ABC$ in a $d_Atimes d_Btimes d_C$ dimensional Hilbert space. Our approximate algorithm provides a practical protocol to implement redistribution of quantum mutual information for a tripartite quantum state with high dimensions.
  arXiv  Detail & Related papers  (2023-06-17T09:00:11Z)
• Constructions of $k$-uniform states in heterogeneous systems [65.63939256159891]
  We present two general methods to construct $k$-uniform states in the heterogeneous systems for general $k$. We can produce many new $k$-uniform states such that the local dimension of each subsystem can be a prime power.
  arXiv  Detail & Related papers  (2023-05-22T06:58:16Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Quantum Approximation of Normalized Schatten Norms and Applications to Learning [0.0]
  This paper addresses the problem of defining a similarity measure for quantum operations that can be textitefficiently estimated We develop a quantum sampling circuit to estimate the normalized Schatten 2-norm of their difference and prove a Poly$(frac1epsilon)$ upper bound on the sample complexity. We then show that such a similarity metric is directly related to a functional definition of similarity of unitary operations using the conventional fidelity metric of quantum states.
  arXiv  Detail & Related papers  (2022-06-23T07:12:10Z)
• 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)
• Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis [24.555887999356646]
  The problem is of fundamental importance in quantum algorithm design, Hamiltonian simulation and quantum machine learning, yet its circuit depth and size complexity remain open when ancillary qubits are available. In this paper, we study efficient constructions of quantum circuits with $m$ ancillary qubits that can prepare $psi_vrangle$ in depth. Our circuits are deterministic, prepare the state and carry out the unitary precisely, utilize the ancillary qubits tightly and the depths are optimal in a wide range of parameter regime.
  arXiv  Detail & Related papers  (2021-08-13T09:47:11Z)
• 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.