Shallow quantum circuit for generating O(1)-entangled approximate state designs

• URL: http://arxiv.org/abs/2507.17871v2
• Date: Wed, 30 Jul 2025 02:50:09 GMT
• Title: Shallow quantum circuit for generating O(1)-entangled approximate state designs
• Authors: Wonjun Lee, Minki Hhan, Gil Young Cho, Hyukjoon Kwon,
• Abstract summary: We find a new ensemble of quantum states that serve as an $epsilon$-approximate state $t$-design while possessing extremely low entanglement, magic, and coherence.<n>These resources can reach their theoretical lower bounds, $Omega(log (t/epsilon))$, which are also proven in this work.<n>A class of quantum circuits proposed in our work offers reduced cost for classical simulation of random quantum states.
• Score: 6.161617062225404
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Random quantum states have various applications in quantum information science. In this work, we discover a new ensemble of quantum states that serve as an $\epsilon$-approximate state $t$-design while possessing extremely low entanglement, magic, and coherence. These resources can reach their theoretical lower bounds, $\Omega(\log (t/\epsilon))$, which are also proven in this work. This implies that for fixed $t$ and $\epsilon$, entanglement, magic, and coherence do not scale with the system size, i.e., $O(1)$ with respect to the total number of qubits $n$. Moreover, we explicitly construct an ancilla-free shallow quantum circuit for generating such states by transforming $k$-qubit approximate state designs into $n$-qubit ones without increasing the support size. The depth of such a quantum circuit, $O(t [\log t]^3 \log n \log(1/\epsilon))$, is the most efficient among existing algorithms without ancilla qubits. A class of quantum circuits proposed in our work offers reduced cost for classical simulation of random quantum states, leading to potential applications in quantum information processing. As a concrete example, we propose classical shadow tomography using an estimator with superpositions between only two states, which improves the runtime of a state certification task by requiring only $O(1)$ measurements and queries.

Related papers

• 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$.<n>This framework holds broad applicability across a range of distributed quantum computing tasks.
  arXiv  Detail & Related papers  (2025-03-12T14:28:22Z)
• Efficient Quantum Circuit Compilation for Near-Term Quantum Advantage [17.38734393793605]
  We propose an approximate method for compiling target quantum circuits into brick-wall layouts.<n>This new circuit design consists of two-qubit CNOT gates that can be directly implemented on real quantum computers.
  arXiv  Detail & Related papers  (2025-01-13T15:04:39Z)
• Resource-efficient algorithm for estimating the trace of quantum state powers [1.5133368155322298]
  Estimating the trace of quantum state powers, $textTr(rhok)$, for $k$ identical quantum states is a fundamental task.<n>We introduce an algorithm that requires only $mathcalO(tilder)$ qubits and $mathcalO(tilder)$ multi-qubit gates.<n>We extend our algorithm to the estimation of $textTr(rhok)$ for arbitrary observables and $textTr(rhok)
  arXiv  Detail & Related papers  (2024-08-01T06:23:52Z)
• A Novel Quantum-Classical Hybrid Algorithm for Determining Eigenstate Energies in Quantum Systems [1.9714447272714082]
  This paper presents a novel quantum algorithm, XZ24, for efficiently computing the eigen-energy spectra of arbitrary quantum systems. XZ24 has three key advantages: It removes the need for eigenstate preparation, requiring only a reference state with non-negligible overlap. It enables simultaneous computation of multiple eigen-energies, depending on the reference state.
  arXiv  Detail & Related papers  (2024-06-01T04:31:43Z)
• 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)
• A generalized framework for quantum state discrimination, hybrid algorithms, and the quantum change point problem [3.4683494246563606]
  We present a hybrid quantum-classical algorithm based on semidefinite programming to calculate the maximum reward when the states are pure and have efficient circuits. We give now-possible algorithms for the quantum change point identification problem which asks, given a sequence of quantum states, determine the time steps when the quantum states changed.
  arXiv  Detail & Related papers  (2023-12-07T03:42:40Z)
• 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)
• Fast Quantum Algorithms for Trace Distance Estimation [8.646488471216262]
  We propose efficient quantum algorithms for estimating the trace distance within additive error $varepsilon$ between mixed quantum states of rank $r$. We show that the decision version of low-rank trace distance estimation is $mathsfBQP$-complete.
  arXiv  Detail & Related papers  (2023-01-17T10:16:14Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Multi-state Swap Test Algorithm [2.709321785404766]
  Estimating the overlap between two states is an important task with several applications in quantum information. We design a quantum circuit to measure overlaps of multiple quantum states.
  arXiv  Detail & Related papers  (2022-05-15T03:31:57Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications [10.436969366019015]
  We show that any $Theta(n)$-depth circuit can be prepared with a $Theta(log(nd)) with $O(ndlog d)$ ancillary qubits. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories.
  arXiv  Detail & Related papers  (2022-01-27T13:16:30Z)
• Exponential separations between learning with and without quantum memory [17.763817187554096]
  We study the power of quantum memory for learning properties of quantum systems and dynamics. Many state-of-the-art learning algorithms require access to an additional external quantum memory. We show that this trade-off is inherent in a wide range of learning problems.
  arXiv  Detail & Related papers  (2021-11-10T19:03:49Z)
• 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)
• Efficient Verification of Anticoncentrated Quantum States [0.38073142980733]
  I present a novel method for estimating the fidelity $F(mu,tau)$ between a preparable quantum state $mu$ and a classically specified target state $tau$. I also present a more sophisticated version of the method, which uses any efficiently preparable and well-characterized quantum state as an importance sampler.
  arXiv  Detail & Related papers  (2020-12-15T18:01:11Z)
• Quantum simulation with hybrid tensor networks [20.177464200362337]
  We introduce the framework of hybrid tensor networks with building blocks consisting of measurable quantum states and classically contractable tensors. We numerically benchmark our method for finding the ground state of 1D and 2D spin systems of up to $8times 8$ and $9times 8$ qubits with operations only acting on $8+1$ and $9+1$ qubits. Our approach sheds light on simulation of large practical problems with intermediate-scale quantum computers, with potential applications in chemistry, quantum many-body physics, quantum field theory, and quantum gravity thought experiments.
  arXiv  Detail & Related papers  (2020-07-02T08:29:32Z)
• 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.