Synthesizing Toffoli-optimal quantum circuits for arbitrary multi-qubit unitaries

• URL: http://arxiv.org/abs/2401.08950v1
• Date: Wed, 17 Jan 2024 03:53:37 GMT
• Title: Synthesizing Toffoli-optimal quantum circuits for arbitrary multi-qubit unitaries
• Authors: Priyanka Mukhopadhyay
• Abstract summary: We study the Clifford+Toffoli universal fault-tolerant gate set. We develop Toffoli-count optimal synthesis algorithms for both approximately and exactly implementable multi-qubit unitaries.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper we study the Clifford+Toffoli universal fault-tolerant gate set. We introduce a generating set in order to represent any unitary implementable by this gate set and with this we derive a bound on the Toffoli-count of arbitrary multi-qubit unitaries. We analyse the channel representation of the generating set elements, with the help of which we infer $|\mathcal{J}_n^{Tof}|<|\mathcal{J}_n^T|$, where $\mathcal{J}_n^{Tof}$ and $\mathcal{J}_n^T$ are the set of unitaries exactly implementable by the Clifford+Toffoli and Clifford+T gate set, respectively. We develop Toffoli-count optimal synthesis algorithms for both approximately and exactly implementable multi-qubit unitaries. With the help of these we prove $|\mathcal{J}_n^{Tof}|=|\mathcal{J}_n^{CS}|$, where $\mathcal{J}_n^{CS}$ is the set of unitaries exactly implementable by the Clifford+CS gate set.

Related papers

• Multi-qutrit exact synthesis [0.0]
  We present an exact synthesis algorithm for qutrit unitaries in $mathcalU_3n(mathbbZ[/3,e2pi i/3])$ over the Clifford$+T$ gate set with at most one ancilla. This, in particular, gives an exact synthesis algorithm of single-qutrit Clifford$+mathcalD$ over the multi-qutrit Clifford$+T$ gate set with at most two ancillas.
  arXiv  Detail & Related papers  (2024-05-13T19:48:10Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  We introduce two oblivious mirror descent algorithms based on a complementary composite setting. Remarkably, both algorithms work without prior knowledge of the Lipschitz constant or smoothness of the objective function. We show how to extend our framework to scale and demonstrate the efficiency and robustness of our methods on large scale semidefinite programs.
  arXiv  Detail & Related papers  (2023-06-30T08:34:29Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  We introduce a new tool for BFG convex optimization (SCO): a Reweighted Query (ReSQue) estimator for the gradient of a function convolved with a (Gaussian) probability density. We develop algorithms achieving state-of-the-art complexities for SCO in parallel and private settings.
  arXiv  Detail & Related papers  (2023-01-01T18:51:29Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Shorter quantum circuits via single-qubit gate approximation [1.2463824156241843]
  We give a novel procedure for approximating general single-qubit unitaries from a finite universal gate set. We show that taking probabilistic mixtures of channels to solve (arXiv:1409.3552) and magnitude approximation problems saves factor of two in approximation costs.
  arXiv  Detail & Related papers  (2022-03-18T17:14:35Z)
• On Submodular Contextual Bandits [92.45432756301231]
  We consider the problem of contextual bandits where actions are subsets of a ground set and mean rewards are modeled by an unknown monotone submodular function. We show that our algorithm efficiently randomizes around local optima of estimated functions according to the Inverse Gap Weighting strategy.
  arXiv  Detail & Related papers  (2021-12-03T21:42:33Z)
• Approximate 3-designs and partial decomposition of the Clifford group representation using transvections [14.823143667165382]
  Scheme implements a random Pauli once followed by the implementation of a random transvection Clifford by using state twirling. We show that when this scheme is implemented $k$ times, then, in the $k rightarrow infty$ limit, the overall scheme implements a unitary $3$-design.
  arXiv  Detail & Related papers  (2021-11-26T18:59:42Z)
• T-count and T-depth of any multi-qubit unitary [1.933681537640272]
  We design provable algorithm to determine T-count of any $n$-qubit ($ngeq 1$) unitary $W$ of size $2ntimes 2n$, over the Clifford+T gate set. Our algorithm can also be used to determine the (minimum possible) T-depth of any multi-qubit unitary.
  arXiv  Detail & Related papers  (2021-10-19T22:16:00Z)
• Halving the width of Toffoli based constant modular addition to n+3 qubits [69.43216268165402]
  We present an arithmetic circuit performing constant modular addition having $mathcalO(n)$ depth of Toffoli gates. This is an improvement by a factor of two compared to the width of the state-of-the-art Toffoli-based constant modular adder.
  arXiv  Detail & Related papers  (2021-02-06T17:07:48Z)
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits [1.933681537640272]
  We use nested meet-in-the-middle technique to develop algorithms for synthesizing provably emphdepth-optimal and emphT-depth-optimal circuits. For synthesizing T-depth-optimal circuits, we get an algorithm with space and time complexity $Oleft(left(4n2right)lceil d/crceilright)$. Our algorithm has space and time complexity $poly(n,25.6n,d)$ (or $poly(nlog n,
  arXiv  Detail & Related papers  (2021-01-08T18:13:36Z)

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.