Search

While implementing a quantum algorithm it is crucial to reduce the quantum resources, in order to obtain the desired computational advantage. For most fault-tolerant quantum error-correcting codes the cost of implementing the non-Clifford gate is the highest among all the gates in a universal fault-tolerant gate set. In this paper we design provable algorithm to determine T-count of any $n$-qubit ($n\geq 1$) unitary $W$ of size $2^n\times 2^n$, over the Clifford+T gate set. The space and time complexity of our algorithm are $O\left(2^{2n}\right)$ and $O\left(2^{2n\mathcal{T}_{\epsilon}(W)+4n}\right)$ respectively. $\mathcal{T}_{\epsilon}(W)$ ($\epsilon$-T-count) is the (minimum possible) T-count of an exactly implementable unitary $U$ i.e. $\mathcal{T}(U)$, such that $d(U,W)\leq\epsilon$ and $\mathcal{T}(U)\leq\mathcal{T}(U')$ where $U'$ is any exactly implementable unitary with $d(U',W)\leq\epsilon$. $d(.,.)$ is the global phase invariant distance. Our algorithm can also be used to determine the (minimum possible) T-depth of any multi-qubit unitary and the complexity has exponential dependence on $n$ and $\epsilon$-T-depth. This is the first algorithm that gives T-count or T-depth of any multi-qubit ($n\geq 1$) unitary. For small enough $\epsilon$, we can synthesize the T-count and T-depth-optimal circuits. Our results can be used to determine the minimum count (or depth) of non-Clifford gates required to implement any multi-qubit unitary with a universal gate set consisting of Clifford and non-Clifford gates like Clifford+CS, Clifford+V, etc. To the best of our knowledge, there were no such optimal-synthesis algorithm for arbitrary multi-qubit unitaries in any universal gate set., Comment: Accepted for publication in Nature Partner Journal Quantum Information. Not structured according to the journal policies. Compared to v3 : A note about implementation of 2-qubit QFT in Table 3

We investigate the problem of synthesizing T-depth optimal quantum circuits over the Clifford+T gate set. First we construct a special subset of T-depth 1 unitaries, such that it is possible to express the T-depth-optimal decomposition of any unitary as product of unitaries from this subset and a Clifford (up to global phase). The cardinality of this subset is at most $n\cdot 2^{5.6n}$. We use nested meet-in-the-middle (MITM) technique to develop algorithms for synthesizing provably \emph{depth-optimal} and \emph{T-depth-optimal} circuits for exactly implementable unitaries. Specifically, for synthesizing T-depth-optimal circuits, we get an algorithm with space and time complexity $O\left(\left(4^{n^2}\right)^{\lceil d/c\rceil}\right)$ and $O\left(\left(4^{n^2}\right)^{(c-1)\lceil d/c\rceil}\right)$ respectively, where $d$ is the minimum T-depth and $c\geq 2$ is a constant. This is much better than the complexity of the algorithm by Amy et al.(2013), the previous best with a complexity $O\left(\left(3^n\cdot 2^{kn^2}\right)^{\lceil \frac{d}{2}\rceil}\cdot 2^{kn^2}\right)$, where $k>2.5$ is a constant. We design an even more efficient algorithm for synthesizing T-depth-optimal circuits. The claimed efficiency and optimality depends on some conjectures, which have been inspired from the work of Mosca and Mukhopadhyay (2020). To the best of our knowledge, the conjectures are not related to the previous work. Our algorithm has space and time complexity $poly(n,2^{5.6n},d)$ (or $poly(n^{\log n},2^{5.6n},d)$ under some weaker assumptions)., Published in Nature Partner Journal Quantum Information. Compared to v4: Minor changes. Not the exact journal version

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

While mapping a quantum circuit to the physical layer one has to consider the numerous constraints imposed by the underlying hardware architecture. Connectivity of the physical qubits is one such constraint that restricts two-qubit operations, such as CNOT, to "connected" qubits. SWAP gates can be used to place the logical qubits on admissible physical qubits, but they entail a significant increase in CNOT-count. In this paper we consider the problem of reducing the CNOT-count in Clifford+T circuits on connectivity constrained architectures, like noisy intermediate-scale quantum (NISQ) computing devices. We "slice" the circuit at the position of Hadamard gates and "build" the intermediate {CNOT,T} sub-circuits using Steiner trees, significantly improving on previous methods. We compared the performance of our algorithms while mapping different benchmark and random circuits to some well-known architectures such as 9-qubit square grid, 16-qubit square grid, Rigetti 16-qubit Aspen, 16-qubit IBM QX5 and 20-qubit IBM Tokyo. Our methods give less CNOT-count compared to Qiskit and TKET transpiler as well as using SWAP gates. Assuming most of the errors in a NISQ circuit implementation are due to CNOT errors, then our method would allow circuits with few times more CNOT gates be reliably implemented than the previous methods would permit., Accepted in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD). This is an extended version with more illustrations. Comparison with Qiskit and TKET added

Heart failure, a complex clinical syndrome affecting millions of Americans, is associated with high morbidity and mortality and a significant financial burden on the health care system. Recent health care reform efforts have focused on reducing 30-day heart failure hospital readmissions, increasing the cost-effectiveness of care provided to heart failure patients, and improving health outcomes for these patients. This case report describes an acutely ill patient with multiple comorbidities who was not initially admitted for heart failure but who developed acute decompensated heart failure during his hospital stay. The purpose of this in-depth analysis is to discuss the role of bedside nurses and advanced practice nurses in managing heart failure, describe the challenges of identifying secondary heart failure in patients with complex conditions, and suggest methods of improving health-related outcomes to prevent hospital readmissions.

Quantum variants of lattice sieve algorithms are routinely used to assess the security of lattice based cryptographic constructions. In this work we provide a heuristic, non-asymptotic, analysis of the cost of several algorithms for near neighbour search on high dimensional spheres. These algorithms are key components of lattice sieves. We design quantum circuits for near neighbour search algorithms and provide software that numerically optimises algorithm parameters according to various cost metrics. Using this software we estimate the cost of classical and quantum near neighbour search on spheres. For the most performant near neighbour search algorithm that we analyse we find a small quantum speedup in dimensions of cryptanalytic interest. Achieving this speedup requires several optimistic physical and algorithmic assumptions.

We describe 'staq', a full-stack quantum processing toolkit written in standard C++. 'staq' is a quantum compiler toolkit, comprising of tools that range from quantum optimizers and translators to physical mappers for quantum devices with restricted connectives. The design of 'staq' is inspired from the UNIX philosophy of "less is more", i.e. 'staq' achieves complex functionality via combining (piping) small tools, each of which performs a single task using the most advanced current state-of-the-art methods. We also provide a set of illustrative benchmarks., Comment: Replaced with the published version, comments are welcome

Topological quantum error-correcting codes are a promising candidate for building fault-tolerant quantum computers. Decoding topological codes optimally, however, is known to be a computationally hard problem. Various decoders have been proposed that achieve approximately optimal error thresholds. Due to practical constraints, it is not known if there exists an obvious choice for a decoder. In this paper, we introduce a framework which can combine arbitrary decoders for any given code to significantly reduce the logical error rates. We rely on the crucial observation that two different decoding techniques, while possibly having similar logical error rates, can perform differently on the same error syndrome. We use machine learning techniques to assign a given error syndrome to the decoder which is likely to decode it correctly. We apply our framework to an ensemble of Minimum-Weight Perfect Matching (MWPM) and Hard-Decision Re-normalization Group (HDRG) decoders for the surface code in the depolarizing noise model. Our simulations show an improvement of 38.4%, 14.6%, and 7.1% over the pseudo-threshold of MWPM in the instance of distance 5, 7, and 9 codes, respectively. Lastly, we discuss the advantages and limitations of our framework and applicability to other error-correcting codes. Our framework can provide a significant boost to error correction by combining the strengths of various decoders. In particular, it may allow for combining very fast decoders with moderate error-correcting capability to create a very fast ensemble decoder with high error-correcting capability., Comment: Replaced with the published version, comments welcome!

We investigate stabilizer codes with carrier qudits of equal dimension $D$, an arbitrary integer greater than 1. We prove that there is a direct relation between the dimension of a qudit stabilizer code and the size of its corresponding stabilizer, and this implies that the code and its stabilizer are dual to each other. We also show that any qudit stabilizer can be put in a standard, or canonical, form using a series of Clifford gates, and we provide an explicit efficient algorithm for doing this. Our work generalizes known results that were valid only for prime dimensional systems and may be useful in constructing efficient encoding/decoding quantum circuits for qudit stabilizer codes and better qudit quantum error correcting codes., RevTeX 4.1, 6 pages, 3 tables. Any comments are welcome!

We introduce and analyze a new type of decoding algorithm called General Color Clustering (GCC), based on renormalization group methods, to be used in qudit color codes. The performance of this decoder is analyzed under code capacity depolarizing noise, and is used to obtain the first fault-tolerant threshold estimates for qudit 6-6-6 color codes. The proposed decoder is compared with similar decoding schemes for qudit surface codes as well as the current leading qubit decoders for both sets of codes. We find that, as with surface codes, clustering performs sub-optimally for qubit color codes, giving a threshold of $9.75\%$ compared to the $11.4\%$ obtained through surface projection decoding methods. However, the threshold rate increases by up to $75\%$ for large qudit dimensions, plateauing around $17.1\%$. All the analysis is performed using QTop, a new open-source software for simulating and visualizing topological quantum error correcting codes., Replaced with the published version, small typos corrected, any comments are welcome! QTop software available at https://github.com/jacobmarks/QTop

We investigate the cost of Grover’s quantum search algorithm when used in the context of pre-image attacks on the SHA-2 and SHA-3 families of hash functions. Our cost model assumes that the attack is run on a surface code based fault-tolerant quantum computer. Our estimates rely on a time-area metric that costs the number of logical qubits times the depth of the circuit in units of surface code cycles. As a surface code cycle involves a significant classical processing stage, our cost estimates allow for crude, but direct, comparisons of classical and quantum algorithms.

We study the robustness of the bucket brigade quantum random access memory model introduced by Giovannetti, Lloyd, and Maccone [Phys. Rev. Lett. 100, 160501 (2008)]. Due to a result of Regev and Schiff [ICALP '08 pp. 773], we show that for a class of error models the error rate per gate in the bucket brigade quantum memory has to be of order $o(2^{-n/2})$ (where $N=2^n$ is the size of the memory) whenever the memory is used as an oracle for the quantum searching problem. We conjecture that this is the case for any realistic error model that will be encountered in practice, and that for algorithms with super-polynomially many oracle queries the error rate must be super-polynomially small, which further motivates the need for quantum error correction. By contrast, for algorithms such as matrix inversion [Phys. Rev. Lett. 103, 150502 (2009)] or quantum machine learning [Phys. Rev. Lett. 113, 130503 (2014)] that only require a polynomial number of queries, the error rate only needs to be polynomially small and quantum error correction may not be required. We introduce a circuit model for the quantum bucket brigade architecture and argue that quantum error correction for the circuit causes the quantum bucket brigade architecture to lose its primary advantage of a small number of "active" gates, since all components have to be actively error corrected., Replaced with the published version. 13 pages, 9 figures

Quantum discord is the quantitative difference between two alternative expressions for bipartite mutual information, given respectively in terms of two distinct definitions for the conditional entropy. By constructing a stochastic model of shared states, classical discord can be similarly defined, quantifying the presence of some stochasticity in the measurement process. Therefore, discord can generally be understood as a quantification of the system's state disturbance due to local measurements, be it quantum or classical. We establish an operational meaning of classical discord in the context of state merging with noisy measurement and thereby show the quantum-classical separation in terms of a negative conditional entropy., Replaced by the published version

Motivated from the theory of quantum error correcting codes, we investigate a combinatorial problem that involves a symmetric $n$-vertices colourable graph and a group of operations (colouring rules) on the graph: find the minimum sequence of operations that maps between two given graph colourings. We provide an explicit algorithm for computing the solution of our problem, which in turn is directly related to computing the distance (performance) of an underlying quantum error correcting code. Computing the distance of a quantum code is a highly non-trivial problem and our method may be of use in the construction of better codes., 8 pages and 3 figures

Uncertainty relations are a distinctive characteristic of quantum theory that impose intrinsic limitations on the precision with which physical properties can be simultaneously determined. The modern work on uncertainty relations employs \emph{entropic measures} to quantify the lack of knowledge associated with measuring non-commuting observables. However, there is no fundamental reason for using entropies as quantifiers; any functional relation that characterizes the uncertainty of the measurement outcomes defines an uncertainty relation. Starting from a very reasonable assumption of invariance under mere relabelling of the measurement outcomes, we show that Schur-concave functions are the most general uncertainty quantifiers. We then discover a fine-grained uncertainty relation that is given in terms of the majorization order between two probability vectors, \textcolor{black}{significantly extending a majorization-based uncertainty relation first introduced in [M. H. Partovi, Phys. Rev. A \textbf{84}, 052117 (2011)].} Such a vector-type uncertainty relation generates an infinite family of distinct scalar uncertainty relations via the application of arbitrary uncertainty quantifiers. Our relation is therefore universal and captures the essence of uncertainty in quantum theory., Comment: 5 + 5 pages, 4 figures, replaced with the published version. Additional references added. Comments are welcome!

Quantum secret-sharing and quantum error-correction schemes rely on multipartite decoding protocols, yet the non-local operations involved are challenging and sometimes infeasible. Here we construct a quantum secret-sharing protocol with a reduced number of quantum communication channels between the players. Our scheme is based on embedding a classical linear code into a quantum error-correcting code. Our work paves the way towards the more general problem of simplifying the decoding of quantum error-correcting codes., Comment: 5 pages, 2 figures, replaced with the PRA published version

We investigate quantum secret sharing schemes constructed from $[[n,k,\delta]]_D$ non-binary stabilizer quantum error correcting codes with carrier qudits of prime dimension $D$. We provide a systematic way of determining the access structure, which completely determines the forbidden and intermediate structures. We then show that the information available to the intermediate structure can be fully described and quantified by what we call the *information group*, a subgroup of the Pauli group of $k$ qudits, and employ this group structure to construct a method for hiding the information from the intermediate structure via twirling of the information group and sharing of classical bits between the dealer and the players. Our scheme allows the transformation of a ramp (intermediate) quantum secret sharing scheme into a semi-quantum perfect secret sharing scheme with the same access structure as the ramp one but without any intermediate subsets, and is optimal in the amount of classical bits the dealer has to distribute., Comment: Replaced by published version, typos corrected

We study how multi-partite entanglement evolves under the paradigm of separable operations, which include the local operations and classical communication (LOCC) as a special case. We prove that the average "decay" of entanglement induced by a separable operation is measure independent (among SL-invariant ones) and state independent: the ratio between the average output entanglement and the initial entanglement is solely a function of the separable operation, regardless of the input state and of the SL-invariant entanglement measure being used. We discuss the "disentangling power" of a quantum channel and show that it exhibits a similar state invariance as the average entanglement decay ratio. Our Rapid Communication significantly extends the bipartite results of Ref. [1-3] as well as the multi-partite one of Ref. [4], all of the previous work being restricted to one-sided or particular noise models., Comment: Replaced by the published version, comments are welcome!

We investigate the conditions under which a set $\SC$ of pure bipartite quantum states on a $D\times D$ system can be locally cloned deterministically by separable operations, when at least one of the states is full Schmidt rank. We allow for the possibility of cloning using a resource state that is less than maximally entangled. Our results include that: (i) all states in $\SC$ must be full Schmidt rank and equally entangled under the $G$-concurrence measure, and (ii) the set $\SC$ can be extended to a larger clonable set generated by a finite group $G$ of order $|G|=N$, the number of states in the larger set. It is then shown that any local cloning apparatus is capable of cloning a number of states that divides $D$ exactly. We provide a complete solution for two central problems in local cloning, giving necessary and sufficient conditions for (i) when a set of maximally entangled states can be locally cloned, valid for all $D$; and (ii) local cloning of entangled qubit states with non-vanishing entanglement. In both of these cases, a maximally entangled resource is necessary and sufficient, and the states must be related to each other by local unitary "shift" operations. These shifts are determined by the group structure, so need not be simple cyclic permutations. Assuming this shifted form and partially entangled states, then in D=3 we show that a maximally entangled resource is again necessary and sufficient, while for higher dimensional systems, we find that the resource state must be strictly more entangled than the states in $\SC$. All of our necessary conditions for separable operations are also necessary conditions for LOCC, since the latter is a proper subset of the former. In fact, all our results hold for LOCC, as our sufficient conditions are demonstrated for LOCC, directly., REVTEX 15 pages, 1 figure, minor modifications. Same as the published version. Any comments are welcome!

Recently [Karimipour and Memarzadeh, Phys. Rev. A 73, 012329 (2006)] studied the problem of finding a family of orthonormal bases in a bipartite space each of dimension $D$ with the following properties: (i) The family continuously interpolates between the product basis and the maximally entangled basis as some parameter $t$ is varied, and (ii) for a fixed $t$, all basis states have the same amount of entanglement. The authors derived a necessary condition and provided explicit solutions for $D \leq 5$ but the existence of a solution for arbitrary dimensions remained an open problem. We prove that such families exist in arbitrary dimensions by providing two simple solutions, one employing the properties of quadratic Gauss sums and the other using graph states. The latter can be generalized to multipartite equientangled bases with more than two parties., Comment: Minor changes, replaced by the published version. Any comments are welcome!

A Holevo measure is used to discuss how much information about a given POVM on system $a$ is present in another system $b$, and how this influences the presence or absence of information about a different POVM on $a$ in a third system $c$. The main goal is to extend information theorems for mutually unbiased bases or general bases to arbitrary POVMs, and especially to generalize "all-or-nothing" theorems about information located in tripartite systems to the case of \emph{partial information}, in the form of quantitative inequalities. Some of the inequalities can be viewed as entropic uncertainty relations that apply in the presence of quantum side information, as in recent work by Berta et al. [Nature Physics 6, 659 (2010)]. All of the results also apply to quantum channels: e.g., if $\EC$ accurately transmits certain POVMs, the complementary channel $\FC$ will necessarily be noisy for certain other POVMs. While the inequalities are valid for mixed states of tripartite systems, restricting to pure states leads to the basis-invariance of the difference between the information about $a$ contained in $b$ and $c$., 21 pages. An earlier version of this paper attempted to prove our main uncertainty relation, Theorem 5, using the achievability of the Holevo quantity in a coding task, an approach that ultimately failed because it did not account for locking of classical correlations, e.g. see [DiVincenzo et al. PRL. 92, 067902 (2004)]. In the latest version, we use a very different approach to prove Theorem 5

The location of quantum information in various subsets of the qudit carriers of an additive graph code is discussed using a collection of operators on the coding space which form what we call the information group. It represents the input information through an encoding operation constructed as an explicit quantum circuit. Partial traces of these operators down to a particular subset of carriers provide an isomorphism of a subgroup of the information group, and this gives a precise characterization of what kinds of information they contain. All carriers are assumed to have the same dimension D, an arbitrary integer greater than 1., Comments are welcome. 17 pages with 4 figures

We show that the possible ensembles produced when a separable operation acts on a single pure bipartite entangled state are completely characterized by a majorization condition, a collection of inequalities for Schmidt coefficients, which is identical to that already known for the particular case of local operations and classical communication (LOCC). As a consequence, various known results for LOCC, including some involving monotonicity of entanglement, can be extended to the class of all separable operations., Typo corrected in the abstract

We study conditions for the deterministic transformation $\ket{\psi}\longrightarrow\ket{\phi}$ of a bipartite entangled state by a separable operation. If the separable operation is a local operation with classical communication (LOCC), Nielsen's majorization theorem provides necessary and sufficient conditions. For the general case we derive a necessary condition in terms of products of Schmidt coefficients, which is equivalent to the Nielsen condition when either of the two factor spaces is of dimension 2, but is otherwise weaker. One implication is that no separable operation can reverse a deterministic map produced by another separable operation, if one excludes the case where the Schmidt coefficients of $\ket{\psi}$ and are the same as those of $\ket{\phi}$. The question of sufficient conditions in the general separable case remains open. When the Schmidt coefficients of $\ket{\psi}$ are the same as those of $\ket{\phi}$, we show that the Kraus operators of the separable transformation restricted to the supports of $\ket{\psi}$ on the factor spaces are proportional to unitaries. When that proportionality holds and the factor spaces have equal dimension, we find conditions for the deterministic transformation of a collection of several full Schmidt rank pure states $\ket{\psi_j}$ to pure states $\ket{\phi_j}$., Comment: Replaced with the published version. Any comments are welcome