Reinforcement learning studies how an agent should interact with an environment to maximize its cumulative reward. A standard way to study this question abstractly is to ask how many samples an agent needs from the environment to learn an optimal policy for a $\gamma$-discounted Markov decision process (MDP). For such an MDP, we design quantum algorithms that approximate an optimal policy ($\pi^*$), the optimal value function ($v^*$), and the optimal $Q$-function ($q^*$), assuming the algorithms can access samples from the environment in quantum superposition. This assumption is justified whenever there exists a simulator for the environment; for example, if the environment is a video game or some other program. Our quantum algorithms, inspired by value iteration, achieve quadratic speedups over the best-possible classical sample complexities in the approximation accuracy ($\epsilon$) and two main parameters of the MDP: the effective time horizon ($\frac{1}{1-\gamma}$) and the size of the action space ($A$). Moreover, we show that our quantum algorithm for computing $q^*$ is optimal by proving a matching quantum lower bound.

High-performance quantum circuit simulation in a classic HPC is still imperative in the NISQ era. Observing that the major obstacle of scalable state-vector quantum simulation arises from the massively fine-grained irregular data-exchange with remote nodes, in this paper we present SV-Sim to apply the PGAS-based communication models (i.e., direct peer access for intra-node CPUs/GPUs and SHMEM for inter-node CPU/GPU clusters) for efficient generalpurpose quantum circuit simulation. Through an orchestrated design based on device functional pointer, SV-Sim is able to abstract various quantum gates across multiple heterogeneous backends, including IBM/Intel/AMD CPUs, NVIDIA/AMD GPUs, and Intel Xeon Phi, in a unified framework, but still asserting outstanding performance and tractable interface to higher-level quantum programming environments, such as IBM Qiskit, Microsoft Q# and Google Cirq. Circumventing the obstacle from the lack of polymorphism in GPUs and leveraging the device-initiated one-sided communication, SV-Sim can process circuit that are dynamically generated in Python using a single GPU/CPU kernel without the need of expensive JIT or runtime parsing, significantly simplifying the programming complexity and improving performance for QC simulation. This is especially appealing for the variational quantum algorithms given the circuits are synthesized online per iteration. Evaluations on the latest NVIDIA DGX-A100, V100-DGX-2, ALCF Theta, OLCF Spock, and OLCF Summit HPCs show that SV-Sim can deliver scalable performance on various state-of-the-art HPC platforms, offering a useful tool for quantum algorithm validation and verification. SV-Sim has been released at http://github.com/pnnl/sv-sim. A version specially tweaked for Q#/QDK is also provided.

This work targets fault-tolerant quantum computing and focuses on the problem of mapping reversible circuits into the Clifford+T quantum gate library. We present an automatically-generated database containing minimal-cost quantum circuits for Boolean functions up to 5 inputs. The database contains three circuits for each spectral-equivalent class representative, which are respectively optimized for the T-count, the T-depth, and the number of qubits. We show that any Boolean function can be derived from the implementation of its class representative without increasing any of the stated cost functions.

Approximation errors must be taken into account when compiling quantum programs into a low-level gate set. We present a methodology that tracks such errors automatically and then optimizes accuracy parameters to guarantee a specified overall accuracy while aiming to minimize the implementation cost in terms of quantum gates. The core idea of our approach is to extract functions that specify the optimization problem directly from the high-level description of the quantum program. Then, custom compiler passes optimize these functions, turning them into (near-)symbolic expressions for (1) the total error and (2) the implementation cost (e.g., total quantum gate count). All unspecified parameters of the quantum program will show up as variables in these expressions, including accuracy parameters. After solving the corresponding optimization problem, a circuit can be instantiated from the found solution. We develop two prototype implementations, one in C++ based on Clang/LLVM, and another using the Q# compiler infrastructure. We benchmark our prototypes on typical quantum computing programs, including the quantum Fourier transform, quantum phase estimation, and Shor's algorithm.

Quantum memory management is becoming a pressing problem, especially given the recent research effort to develop new and more complex quantum algorithms. The only existing automatic method for quantum states clean-up relies on the availability of many extra resources. In this work, we propose an automatic tool for quantum memory management. We show how this problem exactly matches the reversible pebbling game. Based on that, we develop a SAT-based algorithm that returns a valid clean-up strategy, taking the limitations of the quantum hardware into account. The developed tool empowers the designer with the flexibility required to explore the trade-off between memory resources and number of operations. We present two show-cases to prove the validity of our approach. First, we apply the algorithm to straight-line programs, widely used in cryptographic applications. Second, we perform a comparison with the existing approach, showing an average improvement of 52.77%.

We present a constructive method to create quantum circuits that implement oracles |x〉|y〉|0〉k→|x〉|y⊕f(x)〉|0〉kfor n-variable Boolean functions f with low T-count. In our method f is given as a 2-regular Boolean logic network over the gate basis {∧, ⊕, 1}. Our construction leads to circuits with a T-count that is at most four times the number of AND nodes in the network. In addition, we propose a SAT-based method that allows us to trade qubits for T gates, and explore the space/complexity trade-off of quantum circuits. Our constructive method suggests a new upper bound for the number of T gates and ancilla qubits based on the multiplicative complexity c∧(f) of the oracle function f, which is the minimum number of AND gates that is required to realize f over the gate basis {∧, ⊕, 1}. There exists a quantum circuit computing f with at most 4c∧(f)T gates using k=c∧(f) ancillae. Results known for the multiplicative complexity of Boolean functions can be transferred. We verify our method by comparing it to different state-of-the-art compilers. Finally, we present our synthesis results for Boolean functions used in quantum cryptoanalysis.

We present a synthesis framework to map logic networks into quantum circuits for quantum computing. The synthesis framework is based on lookup-table (LUT) networks, which play a key role in conventional logic synthesis. Establishing a connection between LUTs in an LUT network and reversible single-target gates in a reversible network allows us to bridge conventional logic synthesis with logic synthesis for quantum computing, despite several fundamental differences. We call our synthesis framework LUT-based hierarchical reversible logic synthesis (LHRS). Input to LHRS is a classical logic network representing an arbitrary Boolean combinational operation; output is a quantum network (realized in terms of Clifford+T gates). The framework allows one to account for qubit count requirements imposed by the overlying quantum algorithm or target quantum computing hardware. In a fast first step, an initial network is derived that only consists of single-target gates and already completely determines the number of qubits in the final quantum network. Different methods are then used to map each single-target gate into Clifford+T gates, while aiming at optimally using available resources. We demonstrate the versatility of our method by conducting a design space exploration using different parameters on a set of large combinational benchmarks. On the same benchmarks, we show that our approach can advance over the state-of-the-art hierarchical reversible logic synthesis algorithms.

Currently, there is a large research interest and a significant economical effort to build the first practical quantum computer. Such quantum computers promise to exceed the capabilities of conventional computers in fields such as computational chemistry, machine learning and cryptanalysis. Automated methods to map logic designs to quantum networks are crucial to fully realizing this dream, however, existing methods can be expensive both in computational time as well as in the size of the resultant quantum networks. This work introduces an efficient method to map reversible single-target gates into a universal set of quantum gates (Clifford+T). This mapping method is called best-fit mapping and aims at reducing the cost of the resulting quantum network. It exploits fc-LUT mapping and the existence of clean ancilla qubits to decompose a large single-target gate into a set of smaller single-target gates. In addition this work proposes a post-synthesis optimization method to reduce the cost of the final quantum network, based on two cost-minimization properties. Results show a cost reduction for the synthesized EPFL benchmark up to 53% in the number T gates.

Recent developments in quantum hardware indicate that systems featuring more than 50 physical qubits are within reach. At this scale, classical simulation will no longer be feasible and there is a possibility that such quantum devices may outperform even classical supercomputers at certain tasks. With the rapid growth of qubit numbers and coherence times comes the increasingly difficult challenge of quantum program compilation. This entails the translation of a high-level description of a quantum algorithm to hardware-specific low-level operations which can be carried out by the quantum device. Some parts of the calculation may still be performed manually due to the lack of efficient methods. This, in turn, may lead to a design gap, which will prevent the programming of a quantum computer. In this paper, we discuss the challenges in fully-automatic quantum compilation. We motivate directions for future research to tackle these challenges. Yet, with the algorithms and approaches that exist today, we demonstrate how to automatically perform the quantum programming flow from algorithm to a physical quantum computer for a simple algorithmic benchmark, namely the hidden shift problem. We present and use two tool flows which invoke RevKit. One which is based on ProjectQ and which targets the IBM Quantum Experience or a local simulator, and one which is based on Microsoft's quantum programming language Q#.

In this paper, we improve the layered implementation of arbitrary stabilizer circuits introduced by Aaronson and Gottesman in Phys. Rev. A 70 (052328), 2004: to implement a general stabilizer circuit, we reduce their 11-stage computation -H-C-P-C-P-C-H-P-C-P-Cover the gate set consisting of Hadamard, controlled-NOT, and phase gates, into a 7-stage computation of the form -C-CZ-P-H-P-CZ-C-. We show arguments in support of using -CZ- stages over the -C- stages: not only the use of -CZ- stages allows a shorter layered expression, but -CZ- stages are simpler and appear to be easier to implement compared to the -C- stages. Based on this decomposition, we develop a two-qubit gate depth(14n-4) implementation of stabilizer circuits over the gate library {H, P, CNOT}, executable in the Linear Nearest Neighbor (LNN) architecture, improving best previously known depth25n circuit, also executable in the LNN architecture. Our constructions rely on Bruhat decomposition of the symplectic group and on folding arbitrarily long sequences of the form (-P-C-)minto a three-stage computation -P-CZ-C-. Our results include the reduction of the 11-stage decomposition -H-C-P-C-PC-H-P-C-P-Cinto a 9-stage decomposition of the form -C-P-C-PH-C-P-C-P-. This reduction is based on the Bruhat decomposition of the symplectic group. This result also implies a new normal form for stabilizer circuits. We show that a circuit in this normal form is optimal in the number of Hadamard gates used. We also show that the normal form has an asymptotically optimal number of parameters.

Today's rapid advances in the physical implementation of quantum computers demand for scalable synthesis methods in order to map practical logic designs to quantum architectures. We present a synthesis algorithm for quantum computing based on k-LUT networks, which can be derived from Verilog netlists using state-of-the-art and off-the-shelf mapping algorithms. We demonstrate the effectiveness of our method in automatically synthesizing several floating point networks up to double precision. As many quantum algorithms target scientific simulation applications, they can make rich use of floating point arithmetic components. But due to the lack of quantum circuit descriptions for those components, it is not possible to find a realistic cost estimation for the algorithms. Our synthesized benchmarks provide cost estimates that allow quantum algorithm designers to provide the first complete cost estimates for a host of quantum algorithms. This is an essential step towards the goal of understanding which quantum algorithms will be practical in the first generations of quantum computers.

We survey recent strides made towards building a software framework that is capable of compiling quantum algorithms from a high-level description down to physical gates that can be implemented on a fault-tolerant quantum computer. We discuss why compilation and design automation tools such as the ones in our framework are key for tackling the grand challenge of building a scalable quantum computer. We then describe specialized libraries that have been developed using the LIQUi|〉 programming language. This includes reversible circuits for arithmetic as well as new, truly quantum approaches that rely on quantum computer architectures that allow the probabilistic execution of gates, a model that can reduce time and space overheads in some cases. We highlight why these libraries are useful for the implementation of many quantum algorithms. Finally, we survey the tool Revs that facilitate resource efficient compilation of higher-level irreversible programs into lower-level reversible circuits while trying to optimize the memory footprint of the resulting reversible networks. This is motivated by the limited availability of qubits for the foreseeable future.

A major hurdle to the deployment of quantum linear systems algorithms and recent quantum simulation algorithms lies in the difficulty to find inexpensive reversible circuits for arithmetic using existing hand coded methods. Motivated by recent advances in reversible logic synthesis, we synthesize arithmetic circuits using classical design automation flows and tools. The combination of classical and reversible logic synthesis enables the automatic design of large components in reversible logic starting from well-known hardware description languages such as Verilog. As a prototype example for our approach we automatically generate high quality networks for the reciprocal 1/x, which is necessary for quantum linear systems algorithms.

We address the task of switching off the Hamiltonian of a system by removing all internal and system-environment couplings. We propose dynamical decoupling schemes that use only bounded-strength controls for quantum many-body systems with local system Hamiltonians and local environmental couplings. To do so, we introduce the combinatorial concept of balanced-cycle orthogonal arrays (BOAs) and show how to construct them from classical error-correcting codes. The derived decoupling schemes may be useful as a primitive for more complex schemes, e.g., for Hamiltonian simulation. For the case of n qubits and a two-local Hamiltonian, the length of the resulting decoupling scheme scales as O(n logn), improving over the previously best-known schemes that scaled quadratically with n. More generally, using BOAs constructed from families of Bose-Chaudhuri-Hocquenghem (BCH) codes, we show that bounded-strength decoupling for any ℓ-local Hamiltonian, where ℓ ≥ 2, can be achieved using decoupling schemes of length at most O(nℓ-1log n).

We consider quantum MDS (QMDS) codes for quantum systems of dimension q with lengths up to q2+ 2 and minimum distances up to q + 1. We show how starting from QMDS codes of length q2+ 1 based on cyclic and constacyclic codes, new QMDS codes can be obtained by shortening. We provide numerical evidence for our conjecture that almost all admissible lengths, from a lower bound n0(q, d) on, are achievable by shortening. Some additional codes that fill gaps in the list of achievable lengths are presented as well along with a construction of a family of QMDS codes of length q2+2, where q = 2m, that appears to be new.

Fault-tolerant quantum computation is a technique that is necessary to build a scalable quantum computer from noisy physical building blocks. Key for the implementation of fault-tolerant computations is the ability to perform a universal set of quantum gates that act on the code space of an underlying quantum code. To implement such a universal gate set fault-tolerantly is an expensive task in terms of physical operations, and any possible shortcut to save operations is potentially beneficial and might lead to a reduction in overhead for fault-tolerant computations. We show how the automorphism group of a quantum code can be used to implement some operators on the encoded quantum states in a fault-tolerant way by merely permuting the physical qubits. We derive conditions that a code has to satisfy in order to have a large group of operations that can be implemented transversally when combining transversal CNOT with automorphisms. We give several examples for quantum codes with large groups, including codes with parameters [8, 3, 3], [15, 7, 3], [22, 8, 4], and [31, 11, 5].

We present an algorithm for computing depth-optimal decompositions of logical operations, leveraging a meet-in-the-middle technique to provide a significant speedup over simple brute force algorithms. As an illustration of our method, we implemented this algorithm and found factorizations of commonly used quantum logical operations into elementary gates in the Clifford+Tset. In particular, we report a decomposition of the Toffoli gate over the set of Clifford andTgates. Our decomposition achieves a totalT-depth of 3, thereby providing a 40% reduction over the previously best known decomposition for the Toffoli gate. Due to the size of the search space, the algorithm is only practical for small parameters, such as the number of qubits, and the number of gates in an optimal implementation.

Rejection sampling is a well-known method to sample from a target distribution, given the ability to sample from a given distribution. The method has been first formalized by von Neumann (1951) and has many applications in classical computing. We define a quantum analogue of rejection sampling: given a black box producing a coherent superposition of (possibly unknown) quantum states with some amplitudes, the problem is to prepare a coherent superposition of the same states, albeit with different target amplitudes. The main result of this paper is a tight characterization of the query complexity of this quantum state generation problem. We exhibit an algorithm, which we call quantum rejection sampling, and analyze its cost using semidefinite programming. Our proof of a matching lower bound is based on the automorphism principle which allows to symmetrize any algorithm over the automorphism group of the problem. Our main technical innovation is an extension of the automorphism principle to continuous groups that arise for quantum state generation problems where the oracle encodes unknown quantum states, instead of just classical data. Furthermore, we illustrate how quantum rejection sampling may be used as a primitive in designing quantum algorithms, by providing three different applications. We first show that it was implicitly used in the quantum algorithm for linear systems of equations by Harrow, Hassidim and Lloyd. Secondly, we show that it can be used to speed up the main step in the quantum Metropolis sampling algorithm by Temme et al.. Finally, we derive a new quantum algorithm for the hidden shift problem of an arbitrary Boolean function and relate its query complexity to "water-filling" of the Fourier spectrum.

We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem. This problem encompasses both, the computation of partial or total functions and the preparation of target quantum states. There has been hope for quite some time that quantum state generation might be a route to tackle the GRAPH-ISOMORPHISM problem. We show that for the related problem of INDEX-ERASURE our method leads to a lower bound of square root of N which matches an upper bound obtained via reduction to quantum search on N elements. This closes an open problem first raised by Shi [FOCS'02]. Our approach is based on two ideas: (i) on the one hand we generalize the known additive and multiplicative adversary methods to the case of quantum state generation, (ii) on the other hand we show how the symmetries of the underlying problem can be leveraged for the design of optimal adversary matrices and dramatically simplify the computation of adversary bounds. Taken together, these two ideas give the new result for INDEX-ERASURE by using the representation theory of the symmetric group. Also, the method can lead to lower bounds even for small success probability, contrary to the standard adversary method. Furthermore, we answer an open question due to Spalek [CCC'08] by showing that the multiplicative version of the adversary method is stronger than the additive one for any problem. Finally, we prove that the multiplicative bound satisfies a strong direct product theorem, extending a result by Spalek to quantum state generation problems.

The k-pair problem in network coding theory asks to send k messages simultaneously between k source-target pairs over a directed acyclic graph. In a previous paper [ICALP 2009, Part I, pages 622-633] the present authors showed that if a classical k-pair problem is solvable by means of a linear coding scheme, then the quantum k-pair problem over the same graph is also solvable, provided that classical communication can be sent for free between any pair of nodes of the graph. Here we address the main case that remained open in our previous work, namely whether nonlinear classical network coding schemes can also give rise to quantum network coding schemes. This question is motivated by the fact that there are networks for which no linear solutions exist to the k-pair problem, whereas nonlinear solutions exist. In the present paper we overcome the limitation to linear protocols and describe a new communication protocol for perfect quantum network coding that improves over the previous one as follows: (i) the new protocol does not put any condition on the underlying classical coding scheme, that is, it can simulate nonlinear communication protocols as well, and (ii) the amount of classical communication sent in the protocol is significantly reduced.

This paper considers a problem of quantum communication between parties that are connected through a network of quantum channels. The model in this paper assumes that there is no prior entanglement shared among any of the parties, but that classical communication is free. The task is to perfectly transfer an unknown quantum state from a source subsystem to a target subsystem, where both source and target are formed by ordered sets of some of the nodes. It is proved that a lower bound of the rate at which this quantum communication task is possible is given by the classical min-cut max-flow theorem of network coding, where the capacities in question are the quantum capacities of the edges of the network.

We consider the problem of computing an encoding circuit for a quantum convolutional code given by a polynomial stabilizer matrix S(D) = (X(D) | Z(D)). We present an algorithm that is very similar to a polynomial-time algorithm for computing the Smith form of a polynomial matrix. This is a step towards the conjecture that any quantum convolutional code has an encoder with polynomially bounded depth.

Attempts to separate the power of classical and quantum models of computation have a long history. The ultimate goal is to find exponential separations for computational problems. However, such separations do not come a dime a dozen: while there were some early successes in the form of hidden subgroup problems for abelian groups–which generalize Shor's factoring algorithm perhaps most faithfully–only for a handful of non-abelian groups efficient quantum algorithms were found. Recently, problems have gotten increased attention that seek to identify hidden sub-structures of other combinatorial and algebraic objects besides groups. In this paper we provide new examples for exponential separations by considering hidden shift problems that are defined for several classes of highly non-linear Boolean functions. These so-called bent functions arise in cryptography, where their property of having perfectly flat Fourier spectra on the Boolean hypercube gives them resilience against certain types of attack. We present new quantum algorithms that solve the hidden shift problems for several well-known classes of bent functions in polynomial time and with a constant number of queries, while the classical query complexity is shown to be exponential. Our approach uses a technique that exploits the duality between bent functions and their Fourier transforms.

It has been known for some time that graph isomorphism reduces to the hidden subgroup problem (HSP). What is more, most exponential speedups in quantum computation are obtained by solving instances of the HSP. A common feature of the resulting algorithms is the use of quantum coset states, which encode the hidden subgroup. An open question has been how hard it is to use these states to solve graph isomorphism. It was recently shown by Moore et al. [2005] that only an exponentially small amount of information is available from one, or a pair of coset states. A potential source of power to exploit are entangled quantum measurements that act jointly on many states at once. We show that entangled quantum measurements on at least Ω( n log n ) coset states are necessary to get useful information for the case of graph isomorphism, matching an information theoretic upper bound. This may be viewed as a negative result because in general it seems hard to implement a given highly entangled measurement. Our main theorem is very general and also rules out using joint measurements on few coset states for some other groups, such as GL( n ,F p m ) and G n where G is finite and satisfies a suitable property.

Widespread emergence of multicore processors will spur development of parallel applications, exposing programmers to degrees of hardware concurrency hitherto unavailable. Dependable multithreaded software will have to rely on the ability to dynamically detect non-deterministic and notoriously hard to reproduce synchronization bugs manifested through data races. Previous solutions to dynamic data race detection have required specialized hardware, at additional power, design and area costs. We propose RaceTM, a novel approach to data race detection that exploits hardware that will likely be present in future multiprocessors, albeit for a different purpose. In particular, we show how emerging hardware support for transactional memory can be leveraged to aid data race detection. We propose the concept of lightweight debug transactions that exploit the conflict detection mechanisms of transactional memory systems to perform data race detection. We present a proof-of-concept simulation prototype, and evaluate it on data races injected into applications from the SPLASH-2 suite. Our experiments show that this technique is effective at discovering data races and has low performance overhead.

In this paper we give new decoding algorithms for the generalized Shor codes and a class of subsystem codes due to Bacon and Casaccino. Our interest in these codes stems from the fact these codes can allow us to construct quantum codes from non-dual containing codes. In this paper we show how to decode these codes efficiently.

As the end of the semiconductor roadmap for CMOS approaches, architectures based on nanoscale molecular devices are attracting attention. Among several alternatives, silicon nanowires and carbon nanotubes are the two most promising nanotechnologies according to the ITRS. These technologies may enable scaling deep into the nanometer regime. However, they suffer from very defect-prone manufacturing processes. Although the reconfigurability property of the nanoscale devices can be used to tolerate high defect rates, it may not be possible to locate all defects. With very high device densities, testing each component may not be possible because of time or technology restrictions. This points to a scenario in which even though the devices are tested, the tests are not very comprehensive at locating defects, and hence the shipped chips are still defective. Moreover, the devices in the nanometer range will be susceptible to transient faults which can produce arbitrary soft errors. Despite these drawbacks, it is possible to make nanoscale architectures practical and realistic by introducing defect and fault tolerance. In this article, we propose and evaluate a hybrid nanowire-CMOS architecture that addresses all three problems—namely high defect rates, unlocated defects, and transient faults—at the same time. This goal is achieved by using multiple levels of redundancy and majority voters. A key aspect of the architecture is that it contains a judicious balance of both nanoscale and traditional CMOS components. A companion to the architecture is a compiler with heuristics to quickly determine if logic can be mapped onto partially defective nanoscale elements. The heuristics make it possible to introduce defect-awareness in placement and routing. The architecture and compiler are evaluated by applying the complete design flow to several benchmarks.

We present a family of non-additive quantum codes based on Goethals and Preparata codes with parameters ((2m, 22m-5m+1, 8)). The dimension of these codes is eight times higher than the dimension of the best known additive quantum codes of equal length and minimum distance.

Recently, quantum error-correcting codes were proposed that capitalize on the fact that many physical error models lead to a significant asymmetry between the probabilities for bit flip and phase flip errors. An example for a channel which exhibits such asymmetry is the combined amplitude damping and dephasing channel, where the probabilities of bit flips and phase flips can be related to relaxation and dephasing time, respectively. We give systematic constructions of asymmetric quantum stabilizer codes that exploit this asymmetry. Our approach is based on a CSS construction that combines BCH and finite geometry LDPC codes.

We extend the stabilizer formalism to a class of nonadditive quantum codes which are constructed from non-linear classical codes. As an example, we present infinite families of nonadditive codes which are derived from Goethals and Preparata codes.

Widespread emergence of multicore processors will spur development of parallel applications, exposing programmers to more hardware concurrency. Dependable multithreaded software will have to rely on the ability to dynamically detect data races, which are non-deterministic and notoriously hard to reproduce symptoms of synchronization bugs. In this paper, we propose RaceTM, a novel approach that exploits transactional memory support to detect data races. We introduce the concept of lightweight debug transactions that exploit the conflict detection mechanisms of transactional memory systems to perform data race detection. Debug transactions differ from regular transactions in that they do not need to be rolled back, and therefore require no versioning or checkpointing support. Debug transactions do not overlap with a regular transaction, thus providing a transparent mechanism to leverage existing transactional memory support for data race detection.

We address the problems of constructing quantum convolutional codes (QCCs) and of encoding them. The first construction is a CSS-type construction which allows us to find QCCs of rate 2/4. The second construction yields a quantum convolutional code by applying a product code construction to an arbitrary classical convolutional code and an arbitrary quantum block code. We show that the resulting codes have highly structured and efficient encoders. Furthermore, we show that the resulting quantum circuits have finite depth, independent of the lengths of the input stream, and show that this depth is polynomial in the degree and frame size of the code.

We develop the framework for signal processing on a spatial, or undirected, 2-D hexagonal lattice for both an infinite and a finite array of signal samples. This framework includes the proper notions of z-transform, boundary conditions, filtering or convolution, spectrum, frequency response, and Fourier transform. In the finite case, the Fourier transform is called discrete triangle transform. Like the hexagonal lattice, this transform is nonseparable. The derivation of the framework makes it a natural extension of the algebraic signal processing theory that we recently introduced. Namely, we construct the proper signal models, given by polynomial algebras, bottom-up from a suitable definition of hexagonal space shifts using a procedure provided by the algebraic theory. These signal models, in turn, then provide all the basic signal processing concepts. The framework developed in this paper is related to Mersereau's early work on hexagonal lattices in the same way as the discrete cosine and sine transforms are related to the discrete Fourier transform-a fact that will be made rigorous in this paper.

We present an algorithm to construct quantum circuits for encoding and inverse encoding of quantum convolutional codes. We show that any quantum convolutional code contains a subcode of finite index which has a non-catastrophic encoding circuit. Our work generalizes the conditions for non-catastrophic encoders derived in a paper by Oliver and Tillich (quant-ph/0401134) which are applicable only for a restricted class of quantum convolutional codes We also show that the encodes and their inverse constructed by our method naturally can be applied online, i.e., qubits can be sent and received with constant delay

It has been known for some time that graph isomorphism reduces to the hidden subgroup problem (HSP). What is more, most exponential speedups in quantum computation are obtained by solving instances of the HSP. A common feature of the resulting algorithms is the use of quantum coset states, which encode the hidden subgroup. An open question has been how hard it is to use these states to solve graph isomorphism. It was recently shown by Moore, Russell, and Schulman [30] that only an exponentially small amount of information is available from one, or a pair of coset states. A potential source of power to exploit are entangled quantum measurements that act jointly on many states at once. We show that entangled quantum measurements on at least Ω(n log n) coset states are necessary to get useful information for the case of graph isomorphism, matching an information theoretic upper bound. This may be viewed as a negative result because highly entangled measurements seem hard to implement in general. Our main theorem is very general and also rules out using joint measurements on few coset states for some other groups, such as GL(n,Fpm) and Gn where G is finite and satisfies a suitable property.

Decoupling schemes are used in quantum information processing to selectively switch off unwanted interactions in a multipartite Hamiltonian. A decoupling scheme consists of a sequence of local unitary operations which are applied to the system's qudits and alternate with the natural time evolution of the Hamiltonian. Several constructions of decoupling schemes have been given in the literature. Here we focus on two such schemes. The first is based on certain triples of submatrices of Hadamard matrices that are closed under pointwise multiplication (see Leung, “Simulation and reversal of$n$-qubit Hamiltonians using Hadamard matrices,” J. Mod. Opt., vol. 49, pp. 1199–1217, 2002), the second uses orthogonal arrays (see Stollsteimer and Mahler, “Suppression of arbitrary internal couplings in a quantum register,” Phys. Rev. A., vol. 64, p. 052301, 2001). We show that both methods lead to the same class of decoupling schemes. We extend the first method to$2$-local qudit Hamiltonians, where$d geq 2$. Furthermore, we extend the second method to$t$-local qudit Hamiltonians, where$t geq 2$and$d geq 2$, by using orthogonal arrays of strength$t$. We also establish a characterization of orthogonal arrays of strength$t$by showing that they are equivalent to decoupling schemes for$t$-local Hamiltonians which have the property that they can be refined to have time-slots of equal length. The methods used to derive efficient decoupling schemes are based on classical error-correcting codes.

We introduce a new signal transform for computing the spectrum of a signal given on a two-dimensional directional quincunx lattice. The transform is non-separable, but closely related to a two-dimensional (separable) discrete Fourier transform. We derive the transform using recently discovered connections between signal transforms and polynomial algebras. These connections also yield several important properties of the new transform.

We derive a new, two-dimensional nonseparable signal transform for computing the spectrum of spatial signals residing on a finite quincunx lattice. The derivation uses the connection between transforms and polynomial algebras, which has long been known for the discrete Fourier transform (DFT), and was extended to other transforms in recent research. We also show that the new transform can be computed with O(n/sup 2/ log(n)) operations, which puts it in the same complexity class as its separable counterparts.

We present a construction of self-orthogonal codes using product codes. From the resulting codes, one can construct both block quantum error-correcting codes and quantum convolutional codes. We show that from the examples of convolutional codes found, we can derive ordinary quantum error-correcting codes using tail-biting with parameters [42N, 24N, 3]2. While it is known that the product construction cannot improve the rate in the classical case, we show that this can happen for quantum codes: we show that a code [15, 7, 3]2is obtained by the product of a code [5,1,3]2with a suitable code

Mutually unbiased bases (MUBs) are a primitive used in quantum information processing to capture the principle of complementarity. While constructions of maximal sets of d+1 such bases are known for system of prime power dimension d, it is unknown whether this bound can be achieved for any non-prime power dimension. In this paper we demonstrate that maximal sets of MUBs come with a rich combinatorial structure by showing that they actually are the same objects as the complex projective 2-designs with angle set {0, 1/d}. We also give a new and simple proof that symmetric informationally complete POVMs are complex projective 2-designs with angle set {1/(d+1)}

Unitary error bases generalize the Pauli matrices to higher dimensional systems. Two basic constructions of unitary error bases are known: An algebraic construction by Knill that yields nice error bases, and a combinatorial construction by Werner that yields shift-and-multiply bases. An open problem posed by Schlingemann and Werner relates these two constructions and asks whether each nice error basis is equivalent to a shift-and-multiply basis. We solve this problem and show that the answer is negative. However, we find that nice error bases have more structure than one can anticipate from their definition. In particular, we show that nice error bases can be written in a form in which at least half of the matrix entries are 0.

We introduce the discrete triangle transform (DTT), a non-separable transform for signal processing on a two-dimensional equispaced triangular grid. The DTT is, in a strict mathematical sense, a generalization of the DCT, type III, to two dimensions, since the DTT is built from Chebyshev polynomials in two variables in the same way as the DCT, type III, is built from Chebyshev polynomials in one variable. We provide boundary conditions, signal extension, and diagonalization properties for the DTT. Finally, we give evidence that the DTT has Cooley-Tukey FFT like algorithms that enable its efficient computation.

Clifford codes are quantum error control codes that generalize stabilizer codes. These codes were introduced in 1996 by Knill, but only a single nonstabilizer Clifford code was known to date. We derive a necessary and sufficient condition that allows one to decide when a Clifford code is a stabilizer code. We compile a table of all true Clifford codes for error groups of small order

We construct maximum distance separable quantum error-correcting codes. The codes are defined over q-dimensional quantum systems, where q is any prime power. The construction yields quantum MDS codes of length up to q+1 for all possible dimensions and some quantum MDS codes of length up to q2+1. In particular, those families contain codes [[6,2,3]]pand [[7,3,3]]pfor pges3 (cf. [K. Feng (2002)])

Nice error bases have been introduced by Knill (1996) as a generalization of the Pauli basis. These bases are shown to be projective representations of finite groups. We classify all nice error bases of small degree, and all nice error bases with Abelian index groups. We show that, in general, an index group of a nice error basis is necessarily solvable.

For pt. I see ibid., vol.48, no.8, p.2392-95 (2002). Knill (1996) introduced a generalization of stabilizer codes, called Clifford codes. It remained unclear whether or not Clifford codes can be superior to stabilizer codes. We show that Clifford codes are stabilizer codes provided that the abstract error group has an Abelian index group. In particular, if the errors are modeled by tensor products of Pauli matrices, then the associated Clifford codes are necessarily stabilizer codes.

The behaviour of two field extensions with respect to each other can be described by the notions of linear disjointness and freeness. This paper gives methods for effectively deciding linear disjointness and freeness for fields lying under a finitely generated field k(X) = Quot(k[X1 ; : : : ; Xs ]=I(X)). Furthermore the methods developed can be used to decide for two given fields if there exists a field over which they are linear disjoint. This field (if it exists) is always the intersection of the two fields given. Thus we are able to compute the intersection of finitely generated fields which are linear disjoint. All methods used rely on a correspondence from (pairs of) fields to ideals namely the ideal of syzygies of the generators of one field which have coefficients lying in the other field. We thereby generalize existing correspondences associating single fields or field extensions to ideals. Our contribution concludes with an outlook to the problem of computing the intersectio...