Succinct Fermion Data Structures

• URL: http://arxiv.org/abs/2410.04015v1
• Date: Sat, 5 Oct 2024 03:16:36 GMT
• Title: Succinct Fermion Data Structures
• Authors: Joseph Carolan, Luke Schaeffer,
• Abstract summary: Simulating fermionic systems on a quantum computer requires representing fermionic states using qubits. We present two new second-quantized fermion encodings of $F$ fermions in $M$ modes.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Simulating fermionic systems on a quantum computer requires representing fermionic states using qubits. The complexity of many simulation algorithms depends on the complexity of implementing rotations generated by fermionic creation-annihilation operators, and the space depends on the number of qubits used. While standard fermion encodings like Jordan-Wigner are space optimal for arbitrary fermionic systems, physical symmetries like particle conservation can reduce the number of physical configurations, allowing improved space complexity. Such space saving is only feasible if the gate overhead is small, suggesting a (quantum) data structures problem, wherein one would like to minimize space used to represent a fermionic state, while still enabling efficient rotations. We define a structure which naturally captures mappings from fermions to systems of qubits. We then instantiate it in two ways, giving rise to two new second-quantized fermion encodings of $F$ fermions in $M$ modes. An information theoretic minimum of $\mathcal{I}:=\lceil\log \binom{M}{F}\rceil$ qubits is required for such systems, a bound we nearly match over the entire parameter regime. (1) Our first construction uses $\mathcal I+o(\mathcal I)$ qubits when $F=o(M)$, and allows rotations generated by creation-annihilation operators in $O(\mathcal I)$ gates and $O(\log M \log \log M)$ depth. (2) Our second construction uses $\mathcal I+O(1)$ qubits when $F=\Theta(M)$, and allows rotations generated by creation-annihilation operators in $O(\mathcal I^3)$ gates. In relation to comparable prior work, the first represents a polynomial improvement in both space and gate complexity (against Kirby et al. 2022), and the second represents an exponential improvement in gate complexity at the cost of only a constant number of additional qubits (against Harrison et al. or Shee et al. 2022), in the described parameter regimes.

Related papers

• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Qubit encoding for a mixture of localized functions [0.0]
  We develop moderately specialized encoding techniques that generate an arbitrary linear combination of localized complex functions. We also show the results on real superconducting quantum computers to confirm the validity of our techniques.
  arXiv  Detail & Related papers  (2024-04-29T09:14:35Z)
• 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)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
  arXiv  Detail & Related papers  (2023-02-13T22:51:07Z)
• Reducing the qubit requirement of Jordan-Wigner encodings of $N$-mode, $K$-fermion systems from $N$ to $\lceil \log_2 {N \choose K} \rceil$ [1.0884863227198973]
  We show that for particle number conserving systems of $K$ fermions and $N$ modes, the qubit requirement can be reduced to theoretic minimum. This will improve the feasibility of simulation of molecules and many-body systems on near-term quantum computers with limited qubit number.
  arXiv  Detail & Related papers  (2022-11-08T19:01:09Z)
• 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)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  We show that the eigenspectrum of $bf K$ is independent of the distribution of the i.i.d. entries of $bf w$. We propose a novel random technique, called Ternary Random Feature (TRF) The computation of the proposed random features requires no multiplication and a factor of $b$ less bits for storage compared to classical random features.
  arXiv  Detail & Related papers  (2021-10-05T09:33:49Z)
• Second-quantized fermionic operators with polylogarithmic qubit and gate complexity [0.0]
  We present a method for encoding second-quantized fermionic systems in qubits when the number of fermions is conserved. This is the first second-quantized encoding of fermions in qubits whose costs in qubits and gates are both polylogarithmic in $M$.
  arXiv  Detail & Related papers  (2021-09-29T14:53:23Z)
• 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)
• Exponentially faster implementations of Select(H) for fermionic Hamiltonians [0.0]
  We present a framework for constructing quantum circuits that implement the multiply-controlled unitary $textSelect(H) equiv sum_ell. $textSelect(H)$ is one of the main subroutines of several quantum algorithms.
  arXiv  Detail & Related papers  (2020-04-08T18:00:04Z)

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.