Quantum computers use the quantum interference of different computational paths to enhance correct outcomes and suppress erroneous computations. A common pattern underpinning algorithms can be identified when computation is viewed as multi-particle interference. We this approach review (and improve) some existing show how they are related instances phase estimation. provide an explicit algorithm for generating any prescribed with arbitrary precision.

We examine the number of queries to input variables that a quantum algorithm requires compute Boolean functions on {0,1} N in black-box model. show exponential speed-up obtained for partial (i.e., problems involving promise input) by Deutsch and Jozsa, Simon, Shor cannot be any total function: if computes some function f with small error probability using T queries, then there is classical deterministic exactly O ( Ts 6 ) queries. also give asymptotically tight characterizations all...

We present an algorithm for computing depth-optimal decompositions of logical operations, leveraging a meet-in-the-middle technique to provide significant speed-up over simple brute force algorithms. As illustration our method we implemented this and found factorizations the commonly used quantum operations into elementary gates in Clifford+T set. In particular, report decomposition Toffoli gate set Clifford T gates. Our achieves total T-depth 3, thereby providing 40% reduction previously...

Most work in quantum circuit optimization has been performed isolation from the results of fault-tolerance. Here we present a polynomial-time algorithm for optimizing circuits that takes actual implementation fault-tolerant logical gates into consideration. Our re-synthesizes composed Clifford group and T gates, latter being typically most costly gate models, e.g., those based on Steane or surface codes, with purpose minimizing both T-count T-depth. A major feature is ability to...

Organizations must understand their specific risks and plan for systems to be resilient quantum attacks. Assessment is based on three quantities: the security shelf life of information assets, migration time designed resist attacks, remaining before computers break security.

Quantum computing shows great promise for the solution of many difficult problems, such as simulation quantum systems and factorization large numbers. While theory is fairly well understood, it has proved to implement computers in real physical systems. It recently been shown that nuclear magnetic resonance (NMR) can be used small using spin states nuclei carefully chosen molecules. Here we demonstrate use a NMR computer based on pyrimidine base cytosine, implementation algorithm solve...

The authors analyze the computational power and limitations of recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for design algorithms; it truly in sense that can be used to speed up searching by quadratic factor over any classical algorithm. On question whether this new may efficiently solve NP-complete problems on computer, we show usual query complexity arguments cannot rule out polynomial time solution. other hand, argue approach...

We investigate how a classical private key can be used by two players, connected an insecure one-way quantum channel, to perform communication of information. In particular, we show that in order transmit n qubits privately, 2n bits shared are necessary and sufficient. This result may viewed as the analogue one-time pad encryption scheme.

We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0,1}^N in black-box model. show that, model, exponential speed-up obtained for partial (i.e. problems involving promise input) by Deutsch and Jozsa Simon cannot be any total function: if algorithm computes some function f with bounded-error using then there is classical deterministic exactly O(T^6) queries. also give asymptotically tight characterizations all symmetric exact,...

In this paper, we show the equivalence of set unitaries computable by circuits over Clifford and T library ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$, in single-qubit case. We report an efficient synthesis algorithm, with exact optimality guarantee on number Hadamard gates used. conjecture that sets implementable $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$ holds $n$-qubit

Decomposing unitaries into a sequence of elementary operations is at the core quantum computing. Information theoretic arguments show that approximating random unitary with precision $\ensuremath{\epsilon}$ requires $\ensuremath{\Omega}\mathbf{(}\mathrm{log}(1/\ensuremath{\epsilon})\mathbf{)}$ gates. Prior to our work, state art in single qubit included Solovay-Kitaev algorithm $O\mathbf{(}{log}^{3+\ensuremath{\delta}}(1/\ensuremath{\epsilon})\mathbf{)}$ gates and does not use ancillae phase...

We study the robustness of bucket brigade quantum random access memory model introduced by Giovannetti et al (2008 Phys. Rev. Lett.100 160501). Due to a result Regev and Schiff (ICALP '08 733), we show that for class error models rate per gate in has be order (where is size memory) whenever used as an oracle searching problem. conjecture this case any realistic will encountered practice, algorithms with super-polynomially many queries must small, which further motivates need correction. By...

Currently available quantum computing hardware platforms have limited 2-qubit connectivity among their addressable qubits. In order to run a generic algorithm on such platform, one has transform the initial logical circuit describing into an equivalent that obeys restrictions. this work we construct synthesis scheme takes as input qubit graph and over gate set generated by outputs respects of device. As concrete application, apply our techniques Google's Bristlecone 72-qubit chip...

Quantum random-access look-up of a string classical bits is necessary ingredient in several important quantum algorithms. In some cases, the cost such memory (qRAM) limiting factor implementation algorithm. this paper we study fault-tolerantly implementing qRAM. We construct and analyze generic families circuits that function as qRAM, discuss opportunities for qubit-time tradeoffs, estimate their resource costs when embedded surface code.

We examine the number T of queries that a quantum network requires to compute several Boolean functions on {0,1}/sup N/ in black-box model. show that, model, exponential speed-up obtained for partial (i.e. problems involving promise input) by Deutsch and Jozsa Simon cannot be any total function: if algorithm computes some function f with bounded-error using then there is classical deterministic exactly O(T/sup 6/) queries. also give asymptotically tight characterizations all symmetric exact,...

We study the problem of practical realization an abstract quantum circuit when executed on hardware. By practical, we mean adapting to particulars physical environment which restricts/complicates establishment certain direct interactions between qubits. This is a version classical placement problem. theoretical aspects and also present empirical results that match best known solutions have been developed by experimentalists. Finally, discuss efficiency approach scalability its implementation...

By applying a quantum search algorithm to various heuristic and provable sieve algorithms from the literature, we obtain improved asymptotic results for solving shortest vector problem on lattices. With computers can provably find in time 21.799n+o(n) , improving upon classical complexities of 22.465n+o(n) Pujol Stehlé 22n+o(n) Micciancio Voulgaris, while heuristically expect 20.268n+o(n) complexity 20.298n+o(n) Laarhoven De Weger. These will be an important guide selection parameters...

We consider quantum circuits composed of Clifford and $T$ gates. In this context the gate has a special status since it confers universal computation when added to (classically simulable) However can be very expensive implement fault-tolerantly. therefore view as resource which should used only necessary. Given an $n$-qubit unitary $U$ we are interested in computing circuit that implements using minimum possible number gates (called $T$-count $U$). A related task is decide if less than or...