Ying, M & Feng, Y 2021, Model Checking Quantum Systems Principles and Algorithms, Cambridge University Press, UK.
View/Download from: Publisher's site
View description>>
The first book introducing computer aided verification techniques for quantum systems with quantum computing and communication hardware.
Devitt, S 2021, 'The Quantum Sneakernet' in The Quantum Internet, Cambridge University Press, pp. 177-178.
View/Download from: Publisher's site
View description>>
A highly interdisciplinary overview of the emerging topic of the Quantum Internet.
Arunachalam, S, Chakraborty, S, Lee, T, Paraashar, M & de Wolf, R 2021, 'Two new results about quantum exact learning', Quantum, vol. 5, pp. 587-587.
View/Download from: Publisher's site
View description>>
We present two new results about exact learning by quantum computers. First, we show how to exactly learn a k-Fourier-sparse n-bit Boolean function from O(k1.5(logk)2) uniform quantum examples for that function. This improves over the bound of Θ~(kn) uniformly random classical examples (Haviv and Regev, CCC'15). Additionally, we provide a possible direction to improve our O~(k1.5) upper bound by proving an improvement of Chang's lemma for k-Fourier-sparse B...
Bei, X, Chen, S, Guan, J, Qiao, Y & Sun, X 2021, 'From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces', SIAM Journal on Computing, vol. 50, no. 3, pp. 924-971.
View/Download from: Publisher's site
View description>>
In the 1970s, Lovász built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings [Proceedings of FCT, 1979, pp. 565-574]. A similar connection between bipartite graphs and matrix spaces plays a key role in the recent resolutions of the noncommutative rank problem [A. Garg et al., Proceedings of FOCS, 2016, pp. 109-117; G. Ivanyos, Y. Qiao, and K. V. Subrahmanyam, Comput. Complexity, 26 (2017), pp. 717-763]. In this paper, we lay the foundation for another bridge between graphs and alternating matrix spaces, in the context of independent sets and vertex colorings. The corresponding structures in alternating matrix spaces are isotropic spaces and isotropic decompositions, both useful structures in group theory and manifold theory. We first show that the maximum independent set problem and the vertex c-coloring problem reduce to the maximum isotropic space problem and the isotropic c-decomposition problem, respectively. Next, we show that several topics and results about independent sets and vertex colorings have natural correspondences for isotropic spaces and decompositions. These include algorithmic problems, such as the maximum independent set problem for bipartite graphs, and exact exponential-time algorithms for the chromatic number, as well as mathematical questions, such as the number of maximal independent sets, and the relation between the maximum degree and the chromatic number. These connections lead to new interactions between graph theory and algebra. Some results have concrete applications to group theory and manifold theory, and we initiate a variant of these structures in the context of quantum information theory. Finally, we propose several open questions for further exploration.
Béjanin, JH, Earnest, CT, Sanders, YR & Mariantoni, M 2021, 'Resonant Coupling Parameter Estimation with Superconducting Qubits', PRX Quantum, vol. 2, no. 4, pp. 1-18.
View/Download from: Publisher's site
View description>>
Today’s quantum computers are composed of tens of qubits interacting with each other and the environment in increasingly complex networks. To achieve the best possible performance when operating such systems, it is necessary to have accurate knowledge of all parameters in the quantum computer Hamiltonian. In this paper, we demonstrate theoretically and experimentally a method to efficiently learn the parameters of resonant interactions for quantum computers consisting of frequency-tunable superconducting qubits. Such interactions include, for example, those with other qubits, resonators, two-level systems, or other wanted or unwanted modes. Our method is based on a significantly improved swap spectroscopy calibration and consists of an offline data collection algorithm, followed by an online Bayesian learning algorithm. The purpose of the offline algorithm is to detect and coarsely estimate resonant interactions from a state of zero knowledge. It produces a quadratic speedup in the scaling of the number of measurements. The online algorithm subsequently refines the estimate of the parameters to accuracy comparable with that of traditional swap spectroscopy calibration but in constant time. We perform an experiment implementing our technique with a superconducting qubit. By combining both algorithms, we observe a reduction of the calibration time by 1 order of magnitude. Our method will improve present medium-scale superconducting quantum computers and will also scale up to larger systems. Finally, the two algorithms presented here can be readily adopted by communities working on different physical implementations of quantum computing architectures.
Chen, X, Cheng, B, Li, Z, Nie, X, Yu, N, Yung, M-H & Peng, X 2021, 'Experimental cryptographic verification for near-term quantum cloud computing', Science Bulletin, vol. 66, no. 1, pp. 23-28.
View/Download from: Publisher's site
View description>>
An important task for quantum cloud computing is to make sure that there is a real quantum computer running, instead of classical simulation. Here we explore the applicability of a cryptographic verification scheme for verifying quantum cloud computing. We provided a theoretical extension and implemented the scheme on a 5-qubit NMR quantum processor in the laboratory and a 5-qubit and 16-qubit processors of the IBM quantum cloud. We found that the experimental results of the NMR processor can be verified by the scheme with about 1.4% error, after noise compensation by standard techniques. However, the fidelity of the IBM quantum cloud is currently too low to pass the test (about 42% error). This verification scheme shall become practical when servers claim to offer quantum-computing resources that can achieve quantum supremacy.
Doosti, M, Kumar, N, Delavar, M & Kashefi, E 2021, 'Client-server Identification Protocols with Quantum PUF', ACM Transactions on Quantum Computing, vol. 2, no. 3, pp. 1-40.
View/Download from: Publisher's site
View description>>
Recently, major progress has been made towards the realisation of quantum internet to enable a broad range of classically intractable applications. These applications such as delegated quantum computation require running a secure identification protocol between a low-resource and a high-resource party to provide secure communication. In this work, we propose two identification protocols based on the emerging hardware-secure solutions, the quantum Physical Unclonable Functions (qPUFs). The first protocol allows a low-resource party to prove its identity to a high-resource party and in the second protocol, it is vice versa. Unlike existing identification protocols based on Quantum Read-out PUFs that rely on the security against a specific family of attacks, our protocols provide provable exponential security against any Quantum Polynomial-Time adversary with resource-efficient parties. We provide a comprehensive comparison between the two proposed protocols in terms of resources such as quantum memory and computing ability required in both parties as well as the communication overhead between them.
Elman, SJ, Chapman, A & Flammia, ST 2021, 'Free Fermions Behind the Disguise', Communications in Mathematical Physics, vol. 388, no. 2, pp. 969-1003.
View/Download from: Publisher's site
Feng, Y, Li, S & Ying, M 2021, 'Verification of Distributed Quantum Programs.', CoRR, vol. abs/2104.14796.
View/Download from: Publisher's site
View description>>
Distributed quantum systems and especially the Quantum Internet have the ever-increasing potential to fully demonstrate the power of quantum computation. This is particularly true given that developing a general-purpose quantum computer is much more difficult than connecting many small quantum devices. One major challenge of implementing distributed quantum systems is programming them and verifying their correctness. In this paper, we propose a CSP-like distributed programming language to facilitate the specification and verification of such systems. After presenting its operational and denotational semantics, we develop a Hoare-style logic for distributed quantum programs and establish its soundness and (relative) completeness with respect to both partial and total correctness. The effectiveness of the logic is demonstrated by its applications in the verification of quantum teleportation and local implementation of non-local CNOT gates, two important algorithms widely used in distributed quantum systems.
Gour, G & Tomamichel, M 2021, 'Entropy and Relative Entropy From Information-Theoretic Principles', IEEE Transactions on Information Theory, vol. 67, no. 10, pp. 6313-6327.
View/Download from: Publisher's site
View description>>
We introduce an axiomatic approach to entropies and relative entropies that relies only on minimal information-theoretic axioms, namely monotonicity under mixing and data-processing as well as additivity for product distributions. We find that these axioms induce sufficient structure to establish continuity in the interior of the probability simplex and meaningful upper and lower bounds, e.g., we find that every relative entropy satisfying these axioms must lie between the Rényi divergences of order 0 and infty . We further show simple conditions for positive definiteness of such relative entropies and a characterisation in terms of a variant of relative trumping. Our main result is a one-to-one correspondence between entropies and relative entropies.
Guan, J, Wang, Q & Ying, M 2021, 'quantum walks.', Quantum Inf. Comput., vol. 21, pp. 395-408.
View/Download from: Publisher's site
Guff, T, McMahon, NA, Sanders, YR & Gilchrist, A 2021, 'A resource theory of quantum measurements', Journal of Physics A: Mathematical and Theoretical, vol. 54, no. 22, pp. 225301-225301.
View/Download from: Publisher's site
View description>>
Abstract Resource theories are broad frameworks that capture how useful objects are in performing specific tasks. In this paper we devise a formal resource theory quantum measurements, focusing on the ability of a measurement to acquire information. The objects of the theory are equivalence classes of positive operator-valued measures, and the free transformations are changes to a measurement device that can only deteriorate its ability to report information about a physical system. We show that catalysis and purification, protocols that are possible in other resource theories, are impossible in our resource theory for quantum measurements. Standard measures of information gain are shown to be resource monotones, and the resource theory is applied to the task of quantum state discrimination.
He, X & Qiao, Y 2021, 'On the Baer–Lovász–Tutte construction of groups from graphs: Isomorphism types and homomorphism notions', European Journal of Combinatorics, vol. 98, pp. 103404-103404.
View/Download from: Publisher's site
View description>>
Let p be an odd prime. From a simple undirected graph G, through the classical procedures of Baer (1938), Tutte (1947) and Lovász (1989), there is a p-group PG of class 2 and exponent p that is naturally associated with G. Our first result is to show that this construction of groups from graphs respects isomorphism types. That is, given two graphs G and H, G and H are isomorphic as graphs if and only if PG and PH are isomorphic as groups. Our second contribution is a new homomorphism notion for graphs. Based on this notion, a category of graphs can be defined, and the Baer–Lovász–Tutte construction naturally leads to a functor from this category of graphs to the category of groups.
Hsieh, MH 2021, 'Preface', Leibniz International Proceedings in Informatics, LIPIcs, vol. 197.
View/Download from: Publisher's site
Humble, TS & Ying, M 2021, 'Editorial on Celebrating Quantum Computing with ACM', ACM Transactions on Quantum Computing, vol. 2, no. 4, pp. 1-2.
View/Download from: Publisher's site
Ji, Z, Natarajan, A, Vidick, T, Wright, J & Yuen, H 2021, 'MIP* = RE', Communications of the ACM, vol. 64, no. 11, pp. 131-138.
View/Download from: Publisher's site
View description>>
Note from the Research Highlights Co-Chairs: A Research Highlights paper appearing in Communications is usually peer-reviewed prior to publication. The following paper is unusual in that it is still under review. However, the result has generated enormous excitement in the research community, and came strongly nominated by SIGACT, a nomination seconded by external reviewers. The complexity class NP characterizes the collection of computational problems that have efficiently verifiable solutions. With the goal of classifying computational problems that seem to lie beyond NP, starting in the 1980s complexity theorists have considered extensions of the notion of efficient verification that allow for the use of randomness (the class MA), interaction (the class IP), and the possibility to interact with multiple proofs, or provers (the class MIP). The study of these extensions led to the celebrated PCP theorem and its applications to hardness of approximation and the design of cryptographic protocols. In this work, we study a fourth modification to the notion of efficient verification that originates in the study of quantum entanglement. We prove the surprising result that every problem that is recursively enumerable, including the Halting problem, can be efficiently verified by a classical probabilistic polynomial-time verifier interacting with two all-powerful but noncommunicating provers sharing entanglement. The result resolves lo...
Kwon, S, Tomonaga, A, Lakshmi Bhai, G, Devitt, SJ & Tsai, J-S 2021, 'Gate-based superconducting quantum computing', Journal of Applied Physics, vol. 129, no. 4, pp. 041102-041102.
View/Download from: Publisher's site
View description>>
In this Tutorial, we introduce basic conceptual elements to understand and build a gate-based superconducting quantum computing system.
Leung, D, Nayak, A, Shayeghi, A, Touchette, D, Yao, P & Yu, N 2021, 'Capacity Approaching Coding for Low Noise Interactive Quantum Communication Part I: Large Alphabets', IEEE Transactions on Information Theory, vol. 67, no. 8, pp. 5443-5490.
View/Download from: Publisher's site
View description>>
We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for communication. For an arbitrary protocol with n messages, designed for a noiseless qudit channel over a size alphabet, our main result is a simulation method that fails with probability less than and uses a qudit channel over the same alphabet n(1 + times, of which an fraction can be corrupted adversarially. The simulation is thus capacity achieving to leading order, and we conjecture that it is optimal up to a constant factor in the term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Our work improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al., SICOMP'19] for low.
Leung, D, Winter, A & Yu, N 2021, 'LOCC protocols with bounded width per round optimize convex functions', Reviews in Mathematical Physics, vol. 33, no. 05, pp. 2150013-2150013.
View/Download from: Publisher's site
View description>>
We start with the task of discriminating finitely many multipartite quantum states using LOCC protocols, with the goal to optimize the probability of correctly identifying the state. We provide two different methods to show that finitely many measurement outcomes in every step are sufficient for approaching the optimal probability of discrimination. In the first method, each measurement of an optimal LOCC protocol, applied to a [Formula: see text]-dimensional local system, is replaced by one with at most [Formula: see text] outcomes, without changing the probability of success. In the second method, we decompose any LOCC protocol into a convex combination of a number of “slim protocols” in which each measurement applied to a [Formula: see text]-dimensional local system has at most [Formula: see text] outcomes. To maximize any convex functions in LOCC (including the probability of state discrimination or fidelity of state transformation), an optimal protocol can be replaced by the best slim protocol in the convex decomposition without using shared randomness. For either method, the bound on the number of outcomes per measurement is independent of the global dimension, the number of parties, the depth of the protocol, how deep the measurement is located, and applies to LOCC protocols with infinite rounds, and the “measurement compression” can be done “top-down” — independent of later operations in the LOCC protocol. The second method can be generalized to implement LOCC instruments with finitely many classical outcomes: if the instrument has [Formula: see text] coarse-grained final measurement outcomes, global input dimension [Formula: see text] and global output dimension [Formula: see text] for [Formula: see text] conditioned on the [Formula: see text]th outcome, then one can obtain the instrument as a convex combination of no more than [Formula: see text] slim protocols; that is, [Formula: see text] bits of shared randomness ...
Li, S, Zhou, X & Feng, Y 2021, 'Qubit Mapping Based on Subgraph Isomorphism and Filtered Depth-Limited Search', IEEE Transactions on Computers, vol. 70, no. 11, pp. 1777-1788.
View/Download from: Publisher's site
View description>>
Mapping logical quantum circuits to Noisy Intermediate-Scale Quantum (NISQ) devices is a challenging problem which has attracted rapidly increasing interests from both quantum and classical computing communities. This article proposes an efficient method by (i) selecting an initial mapping that takes into consideration the similarity between the architecture graph of the given NISQ device and a graph induced by the input logical circuit and (ii) searching, in a filtered and depth-limited way, a most useful swap combination that makes executable as many as possible two-qubit gates in the logical circuit. The proposed circuit transformation algorithm can significantly decrease the number of auxiliary two-qubit gates required to be added to the logical circuit, especially when it has a large number of two-qubit gates. For an extensive benchmark set of 131 circuits and IBM's current premium Q system, viz., IBM Q Tokyo, our algorithm needs, in average, 0.3801 extra two-qubit gates per input two-qubit gate, while the corresponding figures for three state-of-the-art algorithms are 0.4705, 0.8154, and 1.0066, respectively.
Mann, RL 2021, 'Simulating quantum computations with Tutte polynomials', npj Quantum Information, vol. 7, no. 1, pp. 1-8.
View/Download from: Publisher's site
View description>>
AbstractWe establish a classical heuristic algorithm for exactly computing quantum probability amplitudes. Our algorithm is based on mapping output probability amplitudes of quantum circuits to evaluations of the Tutte polynomial of graphic matroids. The algorithm evaluates the Tutte polynomial recursively using the deletion–contraction property while attempting to exploit structural properties of the matroid. We consider several variations of our algorithm and present experimental results comparing their performance on two classes of random quantum circuits. Further, we obtain an explicit form for Clifford circuit amplitudes in terms of matroid invariants and an alternative efficient classical algorithm for computing the output probability amplitudes of Clifford circuits.
Mann, RL & Helmuth, T 2021, 'Efficient algorithms for approximating quantum partition functions', Journal of Mathematical Physics, vol. 62, no. 2, pp. 022201-022201.
View/Download from: Publisher's site
View description>>
We establish a polynomial-time approximation algorithm for partition functions of quantum spin models at high temperature. Our algorithm is based on the quantum cluster expansion of Netočný and Redig and the cluster expansion approach to designing algorithms due to Helmuth, Perkins, and Regts. Similar results have previously been obtained by related methods, and our main contribution is a simple and slightly sharper analysis for the case of pairwise interactions on bounded-degree graphs.
Moscato, P, Mathieson, L & Haque, MN 2021, 'Augmented intuition: a bridge between theory and practice', Journal of Heuristics, vol. 27, no. 4, pp. 497-547.
View/Download from: Publisher's site
View description>>
Motivated by the celebrated paper of Hooker (J Heuristics 1(1): 33–42, 1995) published in the first issue of this journal, and by the relative lack of progress of both approximation algorithms and fixed-parameter algorithms for the classical decision and optimization problems related to covering edges by vertices, we aimed at developing an approach centered in augmenting our intuition about what is indeed needed. We present a case study of a novel design methodology by which algorithm weaknesses will be identified by computer-based and fixed-parameter tractable algorithmic challenges on their performance. Comprehensive benchmarkings on all instances of small size then become an integral part of the design process. Subsequent analyses of cases where human intuition “fails”, supported by computational testing, will then lead to the development of new methods by avoiding the traps of relying only on human perspicacity and ultimately will improve the quality of the results. Consequently, the computer-aided design process is seen as a tool to augment human intuition. It aims at accelerating and foster theory development in areas such as graph theory and combinatorial optimization since some safe reduction rules for pre-processing can be mathematically proved via theorems. This approach can also lead to the generation of new interesting heuristics. We test our ideas with a fundamental problem in graph theory that has attracted the attention of many researchers over decades, but for which seems it seems to be that a certain stagnation has occurred. The lessons learned are certainly beneficial, suggesting that we can bridge the increasing gap between theory and practice by a more concerted approach that would fuel human imagination from a data-driven discovery perspective.
Ortiz Marrero, C, Kieferová, M & Wiebe, N 2021, 'Entanglement-Induced Barren Plateaus', PRX Quantum, vol. 2, no. 4, p. 040316.
View/Download from: Publisher's site
Peng, Y, Ying, M & Wu, X 2021, 'Algebraic Reasoning of Quantum Programs via Non-Idempotent Kleene Algebra.', CoRR, vol. abs/2110.07018.
Qiao, Y 2021, 'Enumerating alternating matrix spaces over finite fields with explicit coordinates', Discrete Mathematics, vol. 344, no. 11, pp. 112580-112580.
View/Download from: Publisher's site
View description>>
We initiate the study of enumerating linear subspaces of alternating matrices over finite fields with explicit coordinates. We present q-analogues of Gilbert's formula for enumerating connected graphs (Gilbert (1956) [5]), and Read's formula for enumerating c-coloured graphs (Read (1960) [14]). We also develop an analogue of Riddell's formula relating the exponential generating function of graphs with that of connected graphs (Riddell's (1951) [15]), building on Eulerian generating functions developed by Srinivasan ((2006) [16]).
Quadeer, M, Korzekwa, K & Tomamichel, M 2021, 'Work fluctuations due to partial thermalizations in two-level systems', Phys. Rev. E, vol. 103, p. 042141.
View description>>
We study work extraction processes mediated by finite-time interactions withan ambient bath -- \emph{partial thermalizations} -- as continuous time Markovprocesses for two-level systems. Such a stochastic process results influctuations in the amount of work that can be extracted and is characterizedby the rate at which the system parameters are driven in addition to the rateof thermalization with the bath. We analyze the distribution of work for thecase where the energy gap of a two-level system is driven at a constant rate.We derive analytic expressions for average work and lower bound for thevariance of work showing that such processes cannot be fluctuation-free ingeneral. We also observe that an upper bound for the Monte Carlo estimate ofthe variance of work can be obtained using Jarzynski's fluctuation-dissipationrelation for systems initially in equilibrium. Finally, we analyse workextraction cycles by modifying the Carnot cycle, incorporating processesinvolving partial thermalizations and obtain efficiency at maximum power forsuch finite-time work extraction cycles under different sets of constraints.
Renou, M-O, Trillo, D, Weilenmann, M, Le, TP, Tavakoli, A, Gisin, N, Acín, A & Navascués, M 2021, 'Quantum theory based on real numbers can be experimentally falsified', Nature, vol. 600, no. 7890, pp. 625-629.
View/Download from: Publisher's site
View description>>
AbstractAlthough complex numbers are essential in mathematics, they are not needed to describe physical experiments, as those are expressed in terms of probabilities, hence real numbers. Physics, however, aims to explain, rather than describe, experiments through theories. Although most theories of physics are based on real numbers, quantum theory was the first to be formulated in terms of operators acting on complex Hilbert spaces1,2. This has puzzled countless physicists, including the fathers of the theory, for whom a real version of quantum theory, in terms of real operators, seemed much more natural3. In fact, previous studies have shown that such a ‘real quantum theory’ can reproduce the outcomes of any multipartite experiment, as long as the parts share arbitrary real quantum states4. Here we investigate whether complex numbers are actually needed in the quantum formalism. We show this to be case by proving that real and complex Hilbert-space formulations of quantum theory make different predictions in network scenarios comprising independent states and measurements. This allows us to devise a Bell-like experiment, the successful realization of which would disprove real quantum theory, in the same way as standard Bell experiments disproved local physics.
Shi, H, Hsieh, M-H, Guha, S, Zhang, Z & Zhuang, Q 2021, 'Entanglement-assisted capacity regions and protocol designs for quantum multiple-access channels', npj Quantum Information, vol. 7, no. 1, p. 74.
View/Download from: Publisher's site
View description>>
AbstractWe solve the entanglement-assisted (EA) classical capacity region of quantum multiple-access channels (MACs) with an arbitrary number of senders. As an example, we consider the bosonic thermal-loss MAC and solve the one-shot capacity region enabled by an entanglement source composed of sender-receiver pairwise two-mode squeezed vacuum states. The EA capacity region is strictly larger than the capacity region without entanglement-assistance. With two-mode squeezed vacuum states as the source and phase modulation as the encoding, we also design practical receiver protocols to realize the entanglement advantages. Four practical receiver designs, based on optical parametric amplifiers, are given and analyzed. In the parameter region of a large noise background, the receivers can enable a simultaneous rate advantage of 82.0% for each sender. Due to teleportation and superdense coding, our results for EA classical communication can be directly extended to EA quantum communication at half of the rates. Our work provides a unique and practical network communication scenario where entanglement can be beneficial.
Xie, J, Zhou, L, Zhang, A, Xu, H, Yung, M-H, Xu, P, Yu, N & Zhang, L 2021, 'Entirety of Quantum Uncertainty and Its Experimental Verification', Chinese Physics Letters, vol. 38, no. 7, pp. 070303-070303.
View/Download from: Publisher's site
View description>>
As a foundation of quantum physics, uncertainty relations describe ultimate limit for the measurement uncertainty of incompatible observables. Traditionally, uncertainty relations are formulated by mathematical bounds for a specific state. Here we present a method for geometrically characterizing uncertainty relations as an entire area of variances of the observables, ranging over all possible input states. We find that for the pair of position and momentum operators, Heisenberg’s uncertainty principle points exactly to the attainable area of the variances of position and momentum. Moreover, for finite-dimensional systems, we prove that the corresponding area is necessarily semialgebraic; in other words, this set can be represented via finite polynomial equations and inequalities, or any finite union of such sets. In particular, we give the analytical characterization of the areas of variances of (a) a pair of one-qubit observables and (b) a pair of projective observables for arbitrary dimension, and give the first experimental observation of such areas in a photonic system.
Xu, Z, Ying, M & Valiron, B 2021, 'Reasoning about Recursive Quantum Programs.', CoRR, vol. abs/2107.11679.
Ying, M, Feng, Y & Ying, S 2021, 'Optimal Policies for Quantum Markov Decision Processes.', Int. J. Autom. Comput., vol. 18, no. 3, pp. 410-421.
View/Download from: Publisher's site
View description>>
Markov decision process (MDP) offers a general framework for modelling sequential decision making where outcomes are random. In particular, it serves as a mathematical framework for reinforcement learning. This paper introduces an extension of MDP, namely quantum MDP (qMDP), that can serve as a mathematical model of decision making about quantum systems. We develop dynamic programming algorithms for policy evaluation and finding optimal policies for qMDPs in the case of finite-horizon. The results obtained in this paper provide some useful mathematical tools for reinforcement learning techniques applied to the quantum world.
Yu, N & Zhou, L 2021, 'When is the Chernoff Exponent for Quantum Operations Finite?', IEEE Transactions on Information Theory, vol. 67, no. 7, pp. 4517-4523.
View/Download from: Publisher's site
View description>>
We consider the problem of testing two hypotheses of quantum operations in a setting of many uses where an arbitrary prior probability distribution is given. The Chernoff exponent for quantum operations is investigated to track the minimal average error probability of discriminating two quantum operations asymptotically. We answer the question, 'When is the Chernoff exponent for quantum operations finite?' We show that either two quantum operations can be perfectly distinguished with finite uses, or the minimal discrimination error decays exponentially with respect to the number of uses asymptotically. That is, the Chernoff exponent is finite if and only if the quantum operations can not be perfectly distinguished with finite uses. This rules out the possibility of super-exponential decay of error probability. Upper bounds of the Chernoff exponent for quantum operations are provided.
Yu, N, Lai, C-Y & Zhou, L 2021, 'Protocols for Packet Quantum Network Intercommunication', IEEE Transactions on Quantum Engineering, vol. 2, pp. 1-9.
View/Download from: Publisher's site
Zhang, K, Hsieh, M-H, Liu, L & Tao, D 2021, 'Quantum Gram-Schmidt processes and their application to efficient state readout for quantum algorithms', Physical Review Research, vol. 3, no. 4, p. 043095.
View/Download from: Publisher's site
View description>>
Many quantum algorithms that claim speedup over their classical counterparts only generates quantum states as solutions instead of their final classical description. The additional step to decode quantum states into classical vectors normally will destroy the quantum advantage in most scenarios because all existing tomographic methods require runtime that is polynomial with respect to the state dimension. In this work, we present an efficient readout protocol that yields the classical vector form of the generated state, so it will achieve the end-to-end advantage for those quantum algorithms. Our protocol suits the case in which the output state lies in the row space of the input matrix, of rank r, that is stored in the quantum random access memory. The quantum resources for decoding the state in 2 norm with ϵ error require poly(r,1/ϵ) copies of the output state and poly(r,κr,1/ϵ) queries to the input oracles, where κ is the condition number of the input matrix. With our readout protocol, we completely characterize the end-to-end resources for quantum linear equation solvers and quantum singular value decomposition. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure, which we believe will be of independent interest.
Zhang, W-W, Sanders, YR & Sanders, BC 2021, 'Channel discord and distortion', New Journal of Physics, vol. 23, no. 8, pp. 083025-083025.
View/Download from: Publisher's site
View description>>
Abstract Discord, originally notable as a signature of bipartite quantum correlation, in fact can be nonzero classically, i.e. arising from noisy measurements by one of the two parties. Here we redefine classical discord to quantify channel distortion, in contrast to the previous restriction of classical discord to a state, and we then show a monotonic relationship between classical (channel) discord and channel distortion. We show that classical discord is equivalent to (doubly stochastic) channel distortion by numerically discovering a monotonic relation between discord and total-variation distance for a bipartite protocol with one party having a noiseless channel and the other party having a noisy channel. Our numerical method includes randomly generating doubly stochastic matrices for noisy channels and averaging over a uniform measure of input messages. Connecting discord with distortion establishes discord as a signature of classical, not quantum, channel distortion.
Apers, S & Lee, T 1970, 'Quantum complexity of minimum cut', Leibniz International Proceedings in Informatics, LIPIcs.
View/Download from: Publisher's site
View description>>
The minimum cut problem in an undirected and weighted graph G is to find the minimum total weight of a set of edges whose removal disconnects G. We completely characterize the quantum query and time complexity of the minimum cut problem in the adjacency matrix model. If G has n vertices and edge weights at least 1 and at most τ, we give a quantum algorithm to solve the minimum cut problem using Õ(n3/2√τ) queries and time. Moreover, for every integer 1 ≤ τ ≤ n we give an example of a graph G with edge weights 1 and τ such that solving the minimum cut problem on G requires Ω(n3/2√τ) queries to the adjacency matrix of G. These results contrast with the classical randomized case where Ω(n2) queries to the adjacency matrix are needed in the worst case even to decide if an unweighted graph is connected or not. In the adjacency array model, when G has m edges the classical randomized complexity of the minimum cut problem is Θ̃(m). We show that the quantum query and time complexity are Õ(√mnτ) and Õ(√mnτ + n3/2), respectively, where again the edge weights are between 1 and τ. For dense graphs we give lower bounds on the quantum query complexity of Ω(n3/2) for τ > 1 and Ω(τn) for any 1 ≤ τ ≤ n. Our query algorithm uses a quantum algorithm for graph sparsification by Apers and de Wolf (FOCS 2020) and results on the structure of near-minimum cuts by Kawarabayashi and Thorup (STOC 2015) and Rubinstein, Schramm and Weinberg (ITCS 2018). Our time efficient implementation builds on Karger's tree packing technique (STOC 1996).
Brandhofer, S, Devitt, S & Polian, I 1970, 'ArsoNISQ: Analyzing Quantum Algorithms on Near-Term Architectures', 2021 IEEE European Test Symposium (ETS), 2021 IEEE European Test Symposium (ETS), IEEE, Bruges, Belgium, pp. 1-6.
View/Download from: Publisher's site
View description>>
While scalable, fully error corrected quantum computing is years or even decades away, there is considerable interest in noisy intermediate-scale quantum computing (NISQ). In this paper, we introduce the ArsoNISQ framework that determines the tolerable error rate of a given quantum algorithm computation, i.e. quantum circuits, and the success probability of the computation given a success criterion and a NISQ computer. ArsoNISQ is based on simulations of quantum circuits subject to errors according to the Pauli error model.ArsoNISQ was evaluated on a set of quantum algorithms that can incur a quantum speedup or are otherwise relevant to NISQ computing. Despite optimistic expectations in recent literature, we did not observe quantum algorithms with intrinsic robustness, i.e. algorithms that tolerate one error on average, in this evaluation. The evaluation demonstrated, however, that the quantum circuit size sets an upper bound for its tolerable error rate and quantified the difference in tolerate error rates for quantum circuits of similar sizes. Thus, the framework can assist quantum algorithm developers in improving their implementation and selecting a suitable NISQ computing platform. Extrapolating the results into the quantum advantage regime suggests that the error rate of larger quantum computers must decrease substantially or active quantum error correction will need to be deployed for most of the evaluated algorithms.
Brandhofer, S, Devitt, S & Polian, I 1970, 'Error Analysis of the Variational Quantum Eigensolver Algorithm', 2021 IEEE/ACM International Symposium on Nanoscale Architectures (NANOARCH), 2021 IEEE/ACM International Symposium on Nanoscale Architectures (NANOARCH), IEEE, AB, Canada, pp. 1-6.
View/Download from: Publisher's site
View description>>
Variational quantum algorithms have been one of the most intensively studied applications for near-term quantum computing applications. The noisy intermediate-scale quantum (NISQ) regime, where small enough algorithms can be run successfully on noisy quantum computers expected during the next 5 years, is driving both a large amount of research work and a significant amount of private sector funding. Therefore, it is important to understand whether variational algorithms are effective at successfully converging to the correct answer in presence of noise. We perform a comprehensive study of the variational quantum eigensolver (VQE) and its individual quantum subroutines. Building on asymptotic bounds, we show through explicit simulation that the VQE algorithm effectively collapses already when single errors occur during a quantum processing call. We discuss the significant implications of this result in the context of being able to run any variational type algorithm without resource expensive error correction protocols.
Brandhofer, S, Devitt, S, Wellens, T & Polian, I 1970, 'Special Session: Noisy Intermediate-Scale Quantum (NISQ) Computers—How They Work, How They Fail, How to Test Them?', 2021 IEEE 39th VLSI Test Symposium (VTS), 2021 IEEE 39th VLSI Test Symposium (VTS), IEEE, pp. 1-10.
View/Download from: Publisher's site
Cheng, H-C, Winter, A & Yu, N 1970, 'Discrimination of quantum states under locality constraints in the many-copy setting', 2021 IEEE International Symposium on Information Theory (ISIT), 2021 IEEE International Symposium on Information Theory (ISIT), IEEE, Melbourne, Australia, pp. 1188-1193.
View/Download from: Publisher's site
View description>>
We study the discrimination of a pair of orthogonal quantum states in the many-copy setting. This is not a problem when arbitrary quantum measurements are allowed, as then the states can be distinguished perfectly even with one copy. However, it becomes highly nontrivial when we consider states of a multipartite system and locality constraints are imposed. We hence focus on the restricted families of measurements such as local operation and classical communication (LOCC), separable operations (SEP), and the positive-partial-transpose operations (PPT) in this paper. We first study asymptotic discrimination of an arbitrary multipartite entangled pure state against its orthogonal complement using LOCC/SEP/PPT measurements. We prove that the incurred optimal average error probability always decays exponentially in the number of copies, by proving upper and lower bounds on the exponent. In the special case of discriminating a maximally entangled state against its orthogonal complement, we determine the explicit expression for the optimal average error probability, thus establishing the associated Chernoff exponent. Our technique is based on the idea of using PPT operations to approximate LOCC. Then, we show an infinite asymptotic separation between SEP and PPT operations by providing a pair of states constructed from an unextendible product basis (UPB): they can be distinguished perfectly by PPT measurements, while the optimal error probability using SEP measurements admits an exponential lower bound. On the technical side, we prove this result by providing a quantitative version of the well-known statement that the tensor product of UPBs is UPB.
Grochow, JA & Qiao, Y 1970, 'On p-group isomorphism: Search-to-decision, counting-to-decision, and nilpotency class reductions via tensors', Leibniz International Proceedings in Informatics, LIPIcs.
View/Download from: Publisher's site
View description>>
In this paper we study some classical complexity-theoretic questions regarding Group Isomorphism (GpI). We focus on p-groups (groups of prime power order) with odd p, which are believed to be a bottleneck case for GpI, and work in the model of matrix groups over finite fields. Our main results are as follows. Although search-to-decision and counting-to-decision reductions have been known for over four decades for Graph Isomorphism (GI), they had remained open for GpI, explicitly asked by Arvind & Torán (Bull. EATCS, 2005). Extending methods from Tensor Isomorphism (Grochow & Qiao, ITCS 2021), we show moderately exponential-time such reductions within p-groups of class 2 and exponent p. Despite the widely held belief that p-groups of class 2 and exponent p are the hardest cases of GpI, there was no reduction to these groups from any larger class of groups. Again using methods from Tensor Isomorphism (ibid.), we show the first such reduction, namely from isomorphism testing of p-groups of “small” class and exponent p to those of class two and exponent p. For the first results, our main innovation is to develop linear-algebraic analogues of classical graph coloring gadgets, a key technique in studying the structural complexity of GI. Unlike the graph coloring gadgets, which support restricting to various subgroups of the symmetric group, the problems we study require restricting to various subgroups of the general linear group, which entails significantly different and more complicated gadgets. The analysis of one of our gadgets relies on a classical result from group theory regarding random generation of classical groups (Kantor & Lubotzky, Geom. Dedicata, 1990). For the nilpotency class reduction, we combine a runtime analysis of the Lazard Correspondence with Tensor Isomorphism-completeness results (Grochow & Qiao, ibid.).
Grochow, JA & Qiao, Y 1970, 'On the complexity of isomorphism problems for tensors, groups, and polynomials I: Tensor isomorphism-completeness', Leibniz International Proceedings in Informatics, LIPIcs.
View/Download from: Publisher's site
View description>>
We study the complexity of isomorphism problems for tensors, groups, and polynomials. These problems have been studied in multivariate cryptography, machine learning, quantum information, and computational group theory. We show that these problems are all polynomial-time equivalent, creating bridges between problems traditionally studied in myriad research areas. This prompts us to define the complexity class TI, namely problems that reduce to the Tensor Isomorphism (TI) problem in polynomial time. Our main technical result is a polynomial-time reduction from d-tensor isomorphism to 3-tensor isomorphism. In the context of quantum information, this result gives multipartite-to-tripartite entanglement transformation procedure, that preserves equivalence under stochastic local operations and classical communication (SLOCC).
Guan, J, Fang, W & Ying, M 1970, 'Robustness Verification of Quantum Classifiers.', CAV (1), Springer, pp. 151-174.
View/Download from: Publisher's site
View description>>
Several important models of machine learning algorithms have been successfully generalized to the quantum world, with potential speedup to training classical classifiers and applications to data analytics in quantum physics that can be implemented on the near future quantum computers. However, quantum noise is a major obstacle to the practical implementation of quantum machine learning. In this work, we define a formal framework for the robustness verification and analysis of quantum machine learning algorithms against noises. A robust bound is derived and an algorithm is developed to check whether or not a quantum machine learning algorithm is robust with respect to quantum training data. In particular, this algorithm can find adversarial examples during checking. Our approach is implemented on Google’s TensorFlow Quantum and can verify the robustness of quantum machine learning algorithms with respect to a small disturbance of noises, derived from the surrounding environment. The effectiveness of our robust bound and algorithm is confirmed by the experimental results, including quantum bits classification as the “Hello World” example, quantum phase recognition and cluster excitation detection from real world intractable physical problems, and the classification of MNIST from the classical world.
Hong, X, Ying, M, Feng, Y, Zhou, X & Li, S 1970, 'Approximate Equivalence Checking of Noisy Quantum Circuits.', CoRR.
Hong, X, Ying, M, Feng, Y, Zhou, X & Li, S 1970, 'Approximate Equivalence Checking of Noisy Quantum Circuits.', DAC, IEEE, pp. 637-642.
Lee, T, Li, T, Santha, M & Zhang, S 1970, 'On the cut dimension of a graph', Leibniz International Proceedings in Informatics, LIPIcs.
View/Download from: Publisher's site
View description>>
Let G = (V, w) be a weighted undirected graph with m edges. The cut dimension of G is the dimension of the span of the characteristic vectors of the minimum cuts of G, viewed as vectors in {0, 1}m. For every n ≥ 2 we show that the cut dimension of an n-vertex graph is at most 2n − 3, and construct graphs realizing this bound. The cut dimension was recently defined by Graur et al. [13], who show that the maximum cut dimension of an n-vertex graph is a lower bound on the number of cut queries needed by a deterministic algorithm to solve the minimum cut problem on n-vertex graphs. For every n ≥ 2, Graur et al. exhibit a graph on n vertices with cut dimension at least 3n/2 − 2, giving the first lower bound larger than n on the deterministic cut query complexity of computing mincut. We observe that the cut dimension is even a lower bound on the number of linear queries needed by a deterministic algorithm to solve mincut, where a linear query can ask any vector x ∈ R(n 2) and receives the answer wT x. Our results thus show a lower bound of 2n − 3 on the number of linear queries needed by a deterministic algorithm to solve minimum cut on n-vertex graphs, and imply that one cannot show a lower bound larger than this via the cut dimension. We further introduce a generalization of the cut dimension which we call the ℓ1-approximate cut dimension. The ℓ1-approximate cut dimension is also a lower bound on the number of linear queries needed by a deterministic algorithm to compute minimum cut. It is always at least as large as the cut dimension, and we construct an infinite family of graphs on n = 3k + 1 vertices with ℓ1-approximate cut dimension 2n − 2, showing that it can be strictly larger than the cut dimension.
Lee, T, Santha, M & Zhang, S 1970, 'Quantum algorithms for graph problems with cut queries', Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 939-958.
View description>>
Let G be an n-vertex graph with m edges. When asked a subset S of vertices, a cut query on G returns the number of edges of G that have exactly one endpoint in S. We show that there is a bounded-error quantum algorithm that determines all connected components of G after making O(log(n)6) many cut queries. In contrast, it follows from results in communication complexity that any randomized algorithm even just to decide whether the graph is connected or not must make at least Ω(n/log(n)) many cut queries. We further show that with O(log(n)8) many cut queries a quantum algorithm can with high probability output a spanning forest for G. En route to proving these results, we design quantum algorithms for learning a graph using cut queries. We show that a quantum algorithm can learn a graph with maximum degree d after O(dlog(n)2) many cut queries, and can learn a general graph with O(√mlog(n)3/2) many cut queries. These two upper bounds are tight up to the poly-logarithmic factors, and compare to Ω(dn) and Ω(m/log(n)) lower bounds on the number of cut queries needed by a randomized algorithm for the same problems, respectively. The key ingredients in our results are the Bernstein-Vazirani algorithm, approximate counting with “OR queries”, and learning sparse vectors from inner products as in compressed sensing.
Li, Y, Tan, VYF & Tomamichel, M 1970, 'Optimal Adaptive Strategies for Sequential Quantum Hypothesis Testing', 2021 IEEE Information Theory Workshop (ITW), 2021 IEEE Information Theory Workshop (ITW), IEEE, pp. 1-6.
View/Download from: Publisher's site
Ramakrishnan, N, Tomamichel, M & Berta, M 1970, 'Moderate Deviation Analysis for Quantum State Transfer', 2021 IEEE Information Theory Workshop (ITW), 2021 IEEE Information Theory Workshop (ITW), IEEE, pp. 1-6.
View/Download from: Publisher's site
Rambach, M, Qaryan, M, Kewming, M, Ferrie, C, White, AG & Romero, J 1970, 'Robust and efficient high-dimensional quantum state tomography', Optics InfoBase Conference Papers.
Rambach, M, Qaryan, M, Kewming, M, Ferrie, C, White, AG & Romero, J 1970, 'Robust And Efficient High-Dimensional Quantum State Tomography', 2021 Conference on Lasers and Electro-Optics Europe & European Quantum Electronics Conference (CLEO/Europe-EQEC), 2021 Conference on Lasers and Electro-Optics Europe & European Quantum Electronics Conference (CLEO/Europe-EQEC), IEEE, pp. 1-1.
View/Download from: Publisher's site
Rambach, M, Qaryan, M, Kewming, M, Ferrie, C, White, AG & Romero, J 1970, 'Robust and efficient high-dimensional quantum state tomography', Optics InfoBase Conference Papers.
Sadaf, A, Mathieson, L & Musial, K 1970, 'An insight into network structure measures and number of driver nodes', Proceedings of the 2021 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM '21: International Conference on Advances in Social Networks Analysis and Mining, ACM, pp. 471-478.
View/Download from: Publisher's site
Shi, H, Hsieh, MH, Guha, S, Zhang, Z & Zhuang, Q 1970, 'Entanglement-assisted multiple-access channels: capacity regions and protocol designs', Optics InfoBase Conference Papers.
View description>>
We solve the entanglement-assisted rate region of multiple-access channels, applicable to thermal-loss optical networks. Practical protocols based on spontaneous parametric down-conversion source, phase modulation and optical parametric amplifiers are presented to benefit from entanglement [1].
Shi, H, Hsieh, M-H, Guha, S, Zhang, Z & Zhuang, Q 1970, 'Entanglement-assisted multiple-access channels: capacity regions and protocol designs', 2021 IEEE International Symposium on Information Theory (ISIT), 2021 IEEE International Symposium on Information Theory (ISIT), IEEE, pp. 408-413.
View/Download from: Publisher's site
Xu, M, Mei, J, Guan, J & Yu, N 1970, 'Model Checking Quantum Continuous-Time Markov Chains', Leibniz International Proceedings in Informatics, LIPIcs.
View/Download from: Publisher's site
View description>>
Verifying quantum systems has attracted a lot of interests in the last decades. In this paper, we initialise the model checking of quantum continuous-time Markov chain (QCTMC). As a real-time system, we specify the temporal properties on QCTMC by signal temporal logic (STL). To effectively check the atomic propositions in STL, we develop a state-of-the-art real root isolation algorithm under Schanuel's conjecture; further, we check the general STL formula by interval operations with a bottom-up fashion, whose query complexity turns out to be linear in the size of the input formula by calling the real root isolation algorithm. A running example of an open quantum walk is provided to demonstrate our method.
Ying, M 1970, 'Model Checking for Verification of Quantum Circuits.', CoRR, International Symposium on Formal Methods, Springer, Virtual, pp. 23-39.
View/Download from: Publisher's site
View description>>
In this survey paper, we describe a framework for assertion-based verification of quantum circuits by applying model checking techniques for quantum systems developed in our previous work, in which: Noiseless and noisy quantum circuits are modelled as operator- and super-operator-valued transition systems, respectively, both of which can be further represented by tensor networks.Quantum assertions are specified by a temporal extension of Birkhoff-von Neumann quantum logic. Their semantics is defined based on the following design decision: they will be used in verification of quantum circuits by simulation on classical computers or human reasoning rather than by quantum physics experiments (e.g. testing through measurements);Algorithms for reachability analysis and model checking of quantum circuits are developed based on contraction of tensor networks. We observe that many optimisation techniques for computing relational products used in BDD-based model checking algorithms can be generalised for contracting tensor networks of quantum circuits.
Ying, M 1970, 'Model Checking for Verification of Quantum Circuits.', FM, Springer, pp. 23-39.
Yu, N 1970, 'Sample efficient identity testing and independence testing of quantum states', Leibniz International Proceedings in Informatics, LIPIcs.
View/Download from: Publisher's site
View description>>
In this paper, we study the quantum identity testing problem, i.e., testing whether two given quantum states are identical, and quantum independence testing problem, i.e., testing whether a given multipartite quantum state is in tensor product form. For the quantum identity testing problem of D(Cd) system, we provide a deterministic measurement scheme that uses O(dε22) copies via independent measurements with d being the dimension of the state and ε being the additive error. For the independence testing problem D(Cd1 ⊗ Cd2 ⊗ · · · ⊗ Cdm) system, we show that the sample complexity is Θ(~ Πmi=1ε2di) via collective measurements, and O(Πmi=1ε2d2i) via independent measurements. If randomized choice of independent measurements are allowed, the sample complexity is Θ(d3ε2/2) for the quantum identity testing problem, and Θ(~ Πmi=1ε2d3 i/2) for the quantum independence testing problem.
Yu, N & Palsberg, J 1970, 'Quantum abstract interpretation', Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI '21: 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, ACM, pp. 542-558.
View/Download from: Publisher's site
Zhou, L, Barthe, G, Hsu, J, Ying, M & Yu, N 1970, 'A Quantum Interpretation of Bunched Logic for Quantum Separation Logic.', CoRR, IEEE, pp. 1-14.
View/Download from: Publisher's site
View description>>
We propose a model of the substructural logic of Bunched Implications (BI) that is suitable for reasoning about quantum states. In our model, the separating conjunction of BI describes separable quantum states. We develop a program logic where pre- and post-conditions are BI formulas describing quantum states - the program logic can be seen as a counterpart of separation logic for imperative quantum programs. We exercise the logic for proving the security of quantum one-time pad and secret sharing, and we show how the program logic can be used to discover a flaw in Google Cirq's tutorial on the Variational Quantum Algorithm (VQA).
Clark, R, Bartlett, S, Bremner, M, Lam, PK & Ralph, T Australian Strategic Policy Institute 2021, The impact of quantum technologies on secure communications, pp. 1-47, Australian Strategic Policy Institute.
View description>>
This ASPI report examines the impact of quantum technologies on secure communications. It provides an overview of the key technologies and the status of the field in Australia and internationally (including escalating recent developments in both the US and China), and captures counterpart US, UK and Canadian reports and recommendations to those nations’ defence departments that have recently been released publicly.The report is structured into six sections: an introduction that provides a stand-alone overview and sets out both the threat and the opportunity of quantum technologies for communications security, and more detailed sections that span quantum computing, quantum encryption, the quantum internet, and post-quantum cryptography. The last section of the report makes five substantive recommendations in the Australian context that are implementable and in the national interest.A key message on quantum technologies relates to urgency. Escalating international progress is opening a widening gap in relation to Australia’s status in this field. It is critical that, in addition to its own initiatives, the Defence Department transitions from a largely watching brief on progress across the university sector and start-up companies to a leadership role—to coordinate, resource and harness the full potential of a most capable Australian quantum technologies community to support Defence’s objectives.
Devitt, S, Rohde, P, Brennan, G & Robinson, T Australian Strategic Policy Institute 2021, An Australian strategy for the quantum revolution, no. 43/2021, Australian Strategic Policy Institute.
Apers, S, Auza, A & Lee, T 2021, 'A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs'.
Apers, S, Gawrychowski, P & Lee, T 2021, 'Finding the KT partition of a weighted graph in near-linear time'.
Bagherimehrab, M, Sanders, YR, Berry, DW, Brennen, GK & Sanders, BC 2021, 'Nearly optimal quantum algorithm for generating the ground state of a free quantum field theory'.
Costa, PCS, An, D, Sanders, YR, Su, Y, Babbush, R & Berry, DW 2021, 'Optimal scaling quantum linear systems solver via discrete adiabatic theorem'.
Dietrich, H, Elder, M, Piggott, A, Qiao, Y & Weiß, A 2021, 'The isomorphism problem for plain groups is in $Σ_3^{\mathsf{P}}$'.
Feng, Y, Li, S & Ying, M 2021, 'Verification of Distributed Quantum Programs'.
Figueroa-Romero, P, Modi, K, Stace, TM & Hsieh, M-H 2021, 'Randomized benchmarking for non-Markovian noise'.
Gur, T, Hsieh, M-H & Subramanian, S 2021, 'Sublinear quantum algorithms for estimating von Neumann entropy'.
Kargi, C, Dehollain, JP, Henriques, F, Sieberer, LM, Olsacher, T, Hauke, P, Heyl, M, Zoller, P & Langford, NK 2021, 'Quantum Chaos and Universal Trotterisation Performance Behaviours in Digital Quantum Simulation'.
View description>>
Maximising the power of digital quantum simulators requires careful optimisation of experimental resources. We conclusively demonstrate a direct connection between quantum chaos and the breakdown of Trotterisation, exhibiting surprisingly universal behaviour across diverse simulator systems [arXiv:2110.11113 (2021)].
Kargi, C, Dehollain, JP, Sieberer, LM, Henriques, F, Olsacher, T, Hauke, P, Heyl, M, Zoller, P & Langford, NK 2021, 'Quantum Chaos and Universal Trotterisation Behaviours in Digital Quantum Simulations'.
Le, TP, Meroni, C, Sturmfels, B, Werner, RF & Ziegler, T 2021, 'Quantum Correlations in the Minimal Scenario'.
Leone, H, Miller, NR, Singh, D, Langford, NK & Rohde, PP 2021, 'Cost vector analysis & multi-path entanglement routing in quantum networks'.
Li, Y, Tan, VYF & Tomamichel, M 2021, 'Optimal Adaptive Strategies for Sequential Quantum Hypothesis Testing'.
Liao, Y, Hsieh, M-H & Ferrie, C 2021, 'Quantum Optimization for Training Quantum Neural Networks'.
Lumbreras, J, Haapasalo, E & Tomamichel, M 2021, 'Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states'.
Mądzik, MT, Asaad, S, Youssry, A, Joecker, B, Rudinger, KM, Nielsen, E, Young, KC, Proctor, TJ, Baczewski, AD, Laucht, A, Schmitt, V, Hudson, FE, Itoh, KM, Jakob, AM, Johnson, BC, Jamieson, DN, Dzurak, AS, Ferrie, C, Blume-Kohout, R & Morello, A 2021, 'Precision tomography of a three-qubit donor quantum processor in silicon', arXiv.
View/Download from: Publisher's site
Ramakrishnan, N, Tomamichel, M & Berta, M 2021, 'Moderate deviation expansion for fully quantum tasks'.
Rubboli, R & Tomamichel, M 2021, 'Fundamental Limits on Correlated Catalytic State Transformations'.
Shi, H, Hsieh, M-H, Guha, S, Zhang, Z & Zhuang, Q 2021, 'Entanglement-assisted capacity regions and protocol designs for quantum multiple-access channels'.
Youssry, A, Paz-Silva, GA & Ferrie, C 2021, 'Noise Detection with Spectator Qubits and Quantum Feature Engineering'.
Zhang, K, Hsieh, M-H, Liu, L & Tao, D 2021, 'Toward Trainability of Deep Quantum Neural Networks'.
Zhou, X, Feng, Y & Li, S 2021, 'Supervised Learning Enhanced Quantum Circuit Transformation'.
