Calculable lower bounds on the efficiency of universal sets of quantum gates

• URL: http://arxiv.org/abs/2201.11774v2
• Date: Thu, 24 Feb 2022 00:17:48 GMT
• Title: Calculable lower bounds on the efficiency of universal sets of quantum gates
• Authors: Oskar S{\l}owik, Adam Sawicki
• Abstract summary: Currently available quantum computers, so called Noisy Intermediate-Scale Quantum (NISQ) devices, are characterized by relatively low number of qubits and moderate gate fidelities. In this paper we derive lower bounds on $mathrmgap_r(mathcalS)$ and, as a consequence, on the efficiency of universal sets of $d$-dimensional quantum gates.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Currently available quantum computers, so called Noisy Intermediate-Scale Quantum (NISQ) devices, are characterized by relatively low number of qubits and moderate gate fidelities. In such scenario, the implementation of quantum error correction is impossible and the performance of those devices is quite modest. In particular, the depth of circuits implementable with reasonably high fidelity is limited, and the minimization of circuit depth is required. Such depths depend on the efficiency of the universal set of gates $\mathcal{S}$ used in computation, and can be bounded using the Solovay-Kitaev theorem. However, it is known that much better, asymptotically tight bounds of the form $\mathcal{O}(\mathrm{log}(\epsilon^{-1}))$, can be obtained for specific $\mathcal{S}$. Those bounds are controlled by, so called, spectral gap at a certain scale $r(\epsilon)$, denoted $\mathrm{gap}_r(\mathcal{S})$. In this paper we derive lower bounds on $\mathrm{gap}_r(\mathcal{S})$ and, as a consequence, on the efficiency of universal sets of $d$-dimensional quantum gates $\mathcal{S}$ satisfying an additional condition. The condition is naturally met for generic quantum gates, such as e.g. Haar random gates. Our bounds are explicit in the sense that all parameters can be determined by numerical calculations on existing computers, at least for small $d$. This is in contrast with known lower bounds on $\mathrm{gap}_r(\mathcal{S})$ which involve parameters with ambiguous values.

Related papers

• 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)
• 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)
• 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)
• 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)
• 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)
• On quantum algorithms for the Schr\"odinger equation in the semi-classical regime [27.175719898694073]
  We consider Schr"odinger's equation in the semi-classical regime. Such a Schr"odinger equation finds many applications, including in Born-Oppenheimer molecular dynamics and Ehrenfest dynamics.
  arXiv  Detail & Related papers  (2021-12-25T20:01:54Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• 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 Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)
• Trading T gates for dirty qubits in state preparation and unitary synthesis [0.0]
  We present a quantum algorithm for preparing any dimension-$N$ pure quantum state specified by a list of $N$ classical numbers. Our scheme uses $mathcalO(fracNlambda+lambdalogfracNepsilonlogfraclogNepsilon)$ to reduce the T-gate cost to $mathcalO(fracNlambda+lambdalogfracNepsilonlogfraclogNepsilon)$
  arXiv  Detail & Related papers  (2018-12-03T18:24:32Z)

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.