Braun, G, Jain, R, Lee, T & Pokutta, S 2017, 'Information-theoretic approximations of the nonnegative rank', computational complexity, vol. 26, no. 1, pp. 147-197.
View/Download from: Publisher's site
Chapman, RJ, Karim, A, Huang, Z, Flammia, ST, Tomamichel, M & Peruzzo, A 2017, 'Beating the Classical Limits of Information Transmission using a Quantum Decoder', Phys. Rev. A, vol. 97, no. 1, p. 012315.
View/Download from: Publisher's site
View description>>
Encoding schemes and error-correcting codes are widely used in informationtechnology to improve the reliability of data transmission over real-worldcommunication channels. Quantum information protocols can further enhance theperformance in data transmission by encoding a message in quantum states,however, most proposals to date have focused on the regime of a large number ofuses of the noisy channel, which is unfeasible with current quantum technology.We experimentally demonstrate quantum enhanced communication over an amplitudedamping noisy channel with only two uses of the channel per bit and a singleentangling gate at the decoder. By simulating the channel using a photonicinterferometric setup, we experimentally increase the reliability oftransmitting a data bit by greater than 20% for a certain damping range overclassically sending the message twice. We show how our methodology can beextended to larger systems by simulating the transmission of a single bit withup to eight uses of the channel and a two-bit message with three uses of thechannel, predicting a quantum enhancement in all cases.
Cheng, H-C, Hsieh, M-H & Tomamichel, M 2017, 'Quantum Sphere-Packing Bounds with Polynomial Prefactors', IEEE Transactions on Information Theory, 65(5):2872-2898, May 2019, vol. 65, no. 5, pp. 2872-2898.
View/Download from: Publisher's site
View description>>
We study lower bounds on the optimal error probability in classical codingover classical-quantum channels at rates below the capacity, commonly termedquantum sphere-packing bounds. Winter and Dalai have derived such bounds forclassical-quantum channels; however, the exponents in their bounds onlycoincide when the channel is classical. In this paper, we show that these twoexponents admit a variational representation and are related by theGolden-Thompson inequality, reaffirming that Dalai's expression is stronger ingeneral classical-quantum channels. Second, we establish a sphere-packing boundfor classical-quantum channels, which significantly improves Dalai's prefactorfrom the order of subexponential to polynomial. Furthermore, the gap betweenthe obtained error exponent for constant composition codes and the best knownclassical random coding exponent vanishes in the order of $o(\log n / n)$,indicating our sphere-packing bound is almost exact in the high rate regime.Finally, for a special class of symmetric classical-quantum channels, we cancompletely characterize its optimal error probability without the constantcomposition code assumption. The main technical contributions are two converseHoeffding bounds for quantum hypothesis testing and the saddle-point propertiesof error exponent functions.
Chubb, CT, Tan, VYF & Tomamichel, M 2017, 'Moderate deviation analysis for classical communication over quantum channels', Communications in Mathematical Physics, vol. 355, no. 3, pp. 1283-1315.
View/Download from: Publisher's site
View description>>
We analyse families of codes for classical data transmission over quantumchannels that have both a vanishing probability of error and a code rateapproaching capacity as the code length increases. To characterise thefundamental tradeoff between decoding error, code rate and code length for suchcodes we introduce a quantum generalisation of the moderate deviation analysisproposed by Altug and Wagner as well as Polyanskiy and Verdu. We derive such atradeoff for classical-quantum (as well as image-additive) channels in terms ofthe channel capacity and the channel dispersion, giving further evidence thatthe latter quantity characterises the necessary backoff from capacity whentransmitting finite blocks of classical data. To derive these results we alsostudy asymmetric binary quantum hypothesis testing in the moderate deviationsregime. Due to the central importance of the latter task, we expect that ourtechniques will find further applications in the analysis of other quantuminformation processing tasks.
Fang, K, Wang, X, Tomamichel, M & Duan, R 2017, 'Non-asymptotic entanglement distillation', IEEE Transactions on Information Theory, vol. 65, no. 10, pp. 6454-6465.
View/Download from: Publisher's site
View description>>
Entanglement distillation, an essential quantum information processing task,refers to the conversion from multiple copies of noisy entangled states to asmaller number of highly entangled states. In this work, we study thenon-asymptotic fundamental limits for entanglement distillation. We investigatethe optimal tradeoff between the distillation rate, the number of preparedstates, and the error tolerance. First, we derive the one-shot distillableentanglement under completely positive partial transpose preserving operationsas a semidefinite program and demonstrate an exact characterization via thequantum hypothesis testing relative entropy. Second, we establish efficientlycomputable second-order estimations of the distillation rate for generalquantum states. In particular, we provide explicit as well as approximateevaluations for various quantum states of practical interest, including purestates, mixture of Bell states, maximally correlated states and isotropicstates.
Granade, C, Ferrie, C & Flammia, ST 2017, 'Practical adaptive quantum tomography', New Journal of Physics, vol. 19, no. 11, pp. 113017-113017.
View/Download from: Publisher's site
View description>>
© 2017 IOP Publishing Ltd and Deutsche Physikalische Gesellschaft. We introduce a fast and accurate heuristic for adaptive tomography that addresses many of the limitations of prior methods. Previous approaches were either too computationally intensive or tailored to handle special cases such as single qubits or pure states. By contrast, our approach combines the efficiency of online optimization with generally applicable and well-motivated data-processing techniques. We numerically demonstrate these advantages in several scenarios includ ing mixed states, higher-dimensional systems, and restricted measurements.
Grochow, JA & Qiao, Y 2017, 'Algorithms for Group Isomorphism via Group Extensions and Cohomology', SIAM Journal on Computing, vol. 46, no. 4, pp. 1153-1216.
View/Download from: Publisher's site
View description>>
© 2017 SIAM. The isomorphism problem for finite groups of order n (GpI) has long been known to be solvable in nlog n+O(1) time, but only recently were polynomial-time algorithms designed for several interesting group classes. Inspired by recent progress, we revisit the strategy for GpI via the extension theory of groups. The extension theory describes how a normal subgroup N is related to G/N via G, and this naturally leads to a divide-and-conquer strategy that 'splits' GpI into two subproblems: one regarding group actions on other groups, and one regarding group cohomology. When the normal subgroup N is abelian, this strategy is well known. Our first contribution is to extend this strategy to handle the case when N is not necessarily abelian. This allows us to provide a unified explanation of all recent polynomial-time algorithms for special group classes. Guided by this strategy, to make further progress on GpI, we consider central-radical groups, proposed in Babai et al. [Code equivalence and group isomorphism, in Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'11), SIAM, Philadelphia, 2011, ACM, New York, pp. 1395-1408]: the class of groups such that G modulo its center has no abelian normal subgroups. This class is a natural extension of the group class considered by Babai et al. [Polynomial-time isomorphism test for groups with no abelian normal subgroups (extended abstract), in International Colloquium on Automata, Languages, and Programming (ICALP), 2012, pp. 51-62], namely those groups with no abelian normal subgroups. Following the above strategy, we solve GpI in nO(log log n) time for central-radical groups, and in polynomial time for several prominent subclasses of centralradical groups. We also solve GpI in nO(log log n) time for groups whose solvable normal subgroups are elementary abelian but not necessarily central. As far as we are aware, this is the first time there have been worst-case guarantees on an n...
Guan, J, Feng, Y & Ying, M 2017, 'Super-activating Quantum Memory with Entanglement', Quantum Information and Computation, vol. 18, no. 13-14, pp. 1115-1124.
View description>>
Noiseless subsystems were proved to be an efficient and faithful approach topreserve fragile information against decoherence in quantum informationprocessing and quantum computation. They were employed to design a general(hybrid) quantum memory cell model that can store both quantum and classicalinformation. In this paper, we find an interesting new phenomenon that thepurely classical memory cell can be super-activated to preserve quantum states,whereas the null memory cell can only be super-activated to encode classicalinformation. Furthermore, necessary and sufficient conditions for thisphenomenon are discovered so that the super-activation can be easily checked byexamining certain eigenvalues of the quantum memory cell without computing thenoiseless subsystems explicitly. In particular, it is found that entangled andseparable stationary states are responsible for the super-activation of storingquantum and classical information, respectively.
Harper, R, Chapman, RJ, Ferrie, C, Granade, C, Kueng, R, Naoumenko, D, Flammia, ST & Peruzzo, A 2017, 'Explaining quantum correlations through evolution of causal models', Physical Review A, vol. 95, no. 4, pp. 1-16.
View/Download from: Publisher's site
View description>>
© 2017 American Physical Society. We propose a framework for the systematic and quantitative generalization of Bell's theorem using causal networks. We first consider the multiobjective optimization problem of matching observed data while minimizing the causal effect of nonlocal variables and prove an inequality for the optimal region that both strengthens and generalizes Bell's theorem. To solve the optimization problem (rather than simply bound it), we develop a genetic algorithm treating as individuals causal networks. By applying our algorithm to a photonic Bell experiment, we demonstrate the trade-off between the quantitative relaxation of one or more local causality assumptions and the ability of data to match quantum correlations.
Herr, D, Nori, F & Devitt, SJ 2017, 'Lattice surgery translation for quantum computation', New Journal of Physics, vol. 19, no. 1, pp. 013034-013034.
View/Download from: Publisher's site
View description>>
© 2017 IOP Publishing Ltd and Deutsche Physikalische Gesellschaft. In this paper we outline a method for a compiler to translate any non fault tolerant quantum circuit to the geometric representation of the lattice surgery error-correcting code using inherent merge and split operations. Since the efficiency of state distillation procedures has not yet been investigated in the lattice surgery model, their translation is given as an example using the proposed method. The resource requirements seem comparable or better to the defect-based state distillation process, but modularity and eventual implementability allow the lattice surgery model to be an interesting alternative to braiding.
Herr, D, Nori, F & Devitt, SJ 2017, 'Optimization of Lattice Surgery is NP-Hard', npj Quantum Information 3, Article number: 35 (2017), vol. 3, no. 1, pp. 1-5.
View/Download from: Publisher's site
View description>>
The traditional method for computation in either the surface code or in theRaussendorf model is the creation of holes or 'defects' within the encodedlattice of qubits that are manipulated via topological braiding to enact logicgates. However, this is not the only way to achieve universal, fault-tolerantcomputation. In this work, we focus on the Lattice Surgery representation,which realizes transversal logic operations without destroying the intrinsic 2Dnearest-neighbor properties of the braid-based surface code and achievesuniversality without defects and braid based logic. For both techniques thereare open questions regarding the compilation and resource optimization ofquantum circuits. Optimization in braid-based logic is proving to be difficultand the classical complexity associated with this problem has yet to bedetermined. In the context of lattice-surgery-based logic, we can introduce anoptimality condition, which corresponds to a circuit with the lowest resourcerequirements in terms of physical qubits and computational time, and prove thatthe complexity of optimizing a quantum circuit in the lattice surgery model isNP-hard.
Ivanyos, G, Qiao, Y & Subrahmanyam, KV 2017, 'Non-commutative Edmonds’ problem and matrix semi-invariants', computational complexity, vol. 26, no. 3, pp. 717-763.
View/Download from: Publisher's site
View description>>
© 2016, Springer International Publishing. In 1967, J. Edmonds introduced the problem of computing the rank over the rational function field of an n× n matrix T with integral homogeneous linear polynomials. In this paper, we consider the non-commutative version of Edmonds’ problem: compute the rank of T over the free skew field. This problem has been proposed, sometimes in disguise, from several different perspectives in the study of, for example, the free skew field itself (Cohn in J Symbol Log 38(2):309–314, 1973), matrix spaces of low rank (Fortin-Reutenauer in Sémin Lothar Comb 52:B52f 2004), Edmonds’ original problem (Gurvits in J Comput Syst Sci 69(3):448–484, 2004), and more recently, non-commutative arithmetic circuits with divisions (Hrubeš and Wigderson in Theory Comput 11:357-393, 2015. doi:10.4086/toc.2015.v011a014). It is known that this problem relates to the following invariant ring, which we call the F-algebra of matrix semi-invariants, denoted as R(n, m). For a field F, it is the ring of invariant polynomials for the action of SL (n, F) × SL (n, F) on tuples of matrices—(A, C) ∈ SL (n, F) × SL (n, F) sends (B1, … , Bm) ∈ M(n, F) ⊕m to (AB1CT, … , ABmCT). Then those T with non-commutative rank < n correspond to those points in the nullcone of R(n, m). In particular, if the nullcone of R(n, m) is defined by elements of degree ≤ σ, then there follows a poly (n, σ) -time randomized algorithm to decide whether the non-commutative rank of T is full. To our knowledge, previously the best bound for σ was O(n2·4n2) over algebraically closed fields of characteristic 0 (Derksen in Proc Am Math Soc 129(4):955–964, 2001). We now state the main contributions of this paper:We observe that by using an algorithm of Gurvits, and assuming the above bound σ for R(n, m) over Q, deciding whether or not T has non-commutative rank < n over Q can be done deterministically in time polynomial in the input size and σ.When F is large enough, we devise an algorithm ...
Kieferová, M & Wiebe, N 2017, 'Tomography and generative training with quantum Boltzmann machines', Physical Review A, vol. 96, no. 6.
View/Download from: Publisher's site
Kong, S, Li, S & Sioutis, M 2017, 'Exploring Directional Path-Consistency for Solving Constraint Networks', The Computer Journal, vol. 61, no. 9.
View/Download from: Publisher's site
View description>>
Among the local consistency techniques used for solving constraint networks,path-consistency (PC) has received a great deal of attention. However,enforcing PC is computationally expensive and sometimes even unnecessary.Directional path-consistency (DPC) is a weaker notion of PC that considers agiven variable ordering and can thus be enforced more efficiently than PC. Thispaper shows that DPC (the DPC enforcing algorithm of Dechter and Pearl) decidesthe constraint satisfaction problem (CSP) of a constraint language if it iscomplete and has the variable elimination property (VEP). However, we also showthat no complete VEP constraint language can have a domain with more than 2values. We then present a simple variant of the DPC algorithm, called DPC*, andshow that the CSP of a constraint language can be decided by DPC* if it isclosed under a majority operation. In fact, DPC* is sufficient for guaranteeingbacktrack-free search for such constraint networks. Examples of majority-closedconstraint classes include the classes of connected row-convex (CRC)constraints and tree-preserving constraints, which have found applications invarious domains, such as scene labeling, temporal reasoning, geometricreasoning, and logical filtering. Our experimental evaluations show that DPC*significantly outperforms the state-of-the-art algorithms for solvingmajority-closed constraints.
Kong, S, Li, S, Li, Y & Long, Z 2017, 'On tree-preserving constraints', Annals of Mathematics and Artificial Intelligence, vol. 81, no. 3-4, pp. 241-271.
View/Download from: Publisher's site
View description>>
© 2017, Springer International Publishing Switzerland. The study of tractable subclasses of constraint satisfaction problems is a central topic in constraint solving. Tree convex constraints are extensions of the well-known row convex constraints. Just like the latter, every path-consistent tree convex constraint network is globally consistent. However, it is NP-complete to decide whether a tree convex constraint network has solutions. This paper studies and compares three subclasses of tree convex constraints, which are called chain-, path-, and tree-preserving constraints respectively. The class of tree-preserving constraints strictly contains the subclasses of path-preserving and arc-consistent chain-preserving constraints. We prove that, when enforcing strong path-consistency on a tree-preserving constraint network, in each step, the network remains tree-preserving. This ensures the global consistency of consistent tree-preserving networks after enforcing strong path-consistency, and also guarantees the applicability of the partial path-consistency algorithms to tree-preserving constraint networks, which is usually much more efficient than the path-consistency algorithms for large sparse constraint networks. As an application, we show that the class of tree-preserving constraints is useful in solving the scene labelling problem.
Lai, CY & Duan, R 2017, 'On the one-shot zero-error classical capacity of classical-quantum channels assisted by quantum non-signalling correlations', Quantum Information and Computation, vol. 17, no. 5&6, pp. 380-398.
View/Download from: Publisher's site
View description>>
© Rinton Press. Duan and Winter studied the one-shot zero-error classical capacity of a quantum channel assisted by quantum non-signalling correlations, and formulated this problem as a semidefinite program depending only on the Kraus operator space of the channel. For the class of classical-quantum channels, they showed that the asymptotic zero-error classical capacity assisted by quantum non-signalling correlations, minimized over all classicalquantum channels with a confusability graph G, is exactly log v(G), where v(G) is the celebrated Lovász theta function. In this paper, we show that the one-shot capacity for a classical-quantum channel, induced from a circulant graph G defined by equal-sized cyclotomic cosets, is log⌊v(G)⌋, which further implies that its asymptotic capacity is log v(G). This type of graphs include the cycle graphs of odd length, the Paley graphs of prime vertices, and the cubit residue graphs of prime vertices. Examples of other graphs are also discussed. This gives Lovász v function another operational meaning in zero-error classical-quantum communication.
Langford, NK, Sagastizabal, R, Kounalakis, M, Dickel, C, Bruno, A, Luthi, F, Thoen, DJ, Endo, A & DiCarlo, L 2017, 'Experimentally simulating the dynamics of quantum light and matter at deep-strong coupling', Nature Communications, vol. 8, no. 1, pp. 1715-1715.
View/Download from: Publisher's site
View description>>
AbstractThe quantum Rabi model describing the fundamental interaction between light and matter is a cornerstone of quantum physics. It predicts exotic phenomena like quantum phase transitions and ground-state entanglement in ultrastrong and deep-strong coupling regimes, where coupling strengths are comparable to or larger than subsystem energies. Demonstrating dynamics remains an outstanding challenge, the few experiments reaching these regimes being limited to spectroscopy. Here, we employ a circuit quantum electrodynamics chip with moderate coupling between a resonator and transmon qubit to realise accurate digital quantum simulation of deep-strong coupling dynamics. We advance the state of the art in solid-state digital quantum simulation by using up to 90 second-order Trotter steps and probing both subsystems in a combined Hilbert space dimension of ∼80, demonstrating characteristic Schrödinger-cat-like entanglement and large photon build-up. Our approach will enable exploration of extreme coupling regimes and quantum phase transitions, and demonstrates a clear first step towards larger complexities such as in the Dicke model.
Lee, T, Wei, Z & de Wolf, R 2017, 'Some upper and lower bounds on PSD-rank', Mathematical Programming, vol. 162, no. 1-2, pp. 495-521.
View/Download from: Publisher's site
Lekitsch, B, Weidt, S, Fowler, AG, Mølmer, K, Devitt, SJ, Wunderlich, C & Hensinger, WK 2017, 'Blueprint for a microwave trapped ion quantum computer', Science Advances, vol. 3, no. 2, pp. 1-11.
View/Download from: Publisher's site
View description>>
Design to build a trapped ion quantum computer with modules connected by ion transport and voltage-driven quantum gate technology.
Li, Y & Qiao, Y 2017, 'On rank-critical matrix spaces', Differential Geometry and its Applications, vol. 55, pp. 68-77.
View/Download from: Publisher's site
View description>>
© 2017 Elsevier B.V. A matrix space of size m×n is a linear subspace of the linear space of m×n matrices over a field F. The rank of a matrix space is defined as the maximal rank over matrices in this space. A matrix space A is called rank-critical, if any matrix space which properly contains it has rank strictly greater than that of A. In this note, we first exhibit a necessary and sufficient condition for a matrix space A to be rank-critical, when F is large enough. This immediately implies the sufficient condition for a matrix space to be rank-critical by Draisma (2006) [5], albeit requiring the field to be slightly larger. We then study rank-critical spaces in the context of compression and primitive matrix spaces. We first show that every rank-critical matrix space can be decomposed into a rank-critical compression matrix space and a rank-critical primitive matrix space. We then prove, using our necessary and sufficient condition, that the block-diagonal direct sum of two rank-critical matrix spaces is rank-critical if and only if both matrix spaces are primitive, when the field is large enough.
Lund, AP, Bremner, MJ & Ralph, TC 2017, 'Quantum Sampling Problems, BosonSampling and Quantum Supremacy', npj Quantum Information (2017) 3:15, vol. 3, no. 1, pp. 1-8.
View/Download from: Publisher's site
View description>>
There is a large body of evidence for the potential of greater computationalpower using information carriers that are quantum mechanical over thosegoverned by the laws of classical mechanics. But the question of the exactnature of the power contributed by quantum mechanics remains only partiallyanswered. Furthermore, there exists doubt over the practicality of achieving alarge enough quantum computation that definitively demonstrates quantumsupremacy. Recently the study of computational problems that produce samplesfrom probability distributions has added to both our understanding of the powerof quantum algorithms and lowered the requirements for demonstration of fastquantum algorithms. The proposed quantum sampling problems do not require aquantum computer capable of universal operations and also permit physicallyrealistic errors in their operation. This is an encouraging step towards anexperimental demonstration of quantum algorithmic supremacy. In this paper, wewill review sampling problems and the arguments that have been used to deducewhen sampling problems are hard for classical computers to simulate. Twoclasses of quantum sampling problems that demonstrate the supremacy of quantumalgorithms are BosonSampling and IQP Sampling. We will present the details ofthese classes and recent experimental progress towards demonstrating quantumsupremacy in BosonSampling.
Mans, B & Mathieson, L 2017, 'Incremental Problems in the Parameterized Complexity Setting', Theory of Computing Systems, vol. 60, no. 1, pp. 3-19.
View/Download from: Publisher's site
View description>>
© 2016, Springer Science+Business Media New York. Dynamic systems are becoming steadily more important with the profusion of mobile and distributed computing devices. Coincidentally incremental computation is a natural approach to deal with ongoing changes. We explore incremental computation in the parameterized complexity setting and show that incrementalization leads to non-trivial complexity classifications. Interestingly, some incremental versions of hard problems become tractable, while others remain hard. Moreover tractability or intractability is not a simple function of the problem’s static complexity, every level of the W-hierarchy exhibits complete problems with both tractable and intractable incrementalizations. For problems that are already tractable in their static form, we also show that incrementalization can lead to interesting algorithms, improving upon the trivial approach of using the static algorithm at each step.
Mukhopadhyay, P & Qiao, Y 2017, 'Sparse multivariate polynomial interpolation on the basis of Schubert polynomials', computational complexity, vol. 26, no. 4, pp. 881-909.
View/Download from: Publisher's site
View description>>
© 2016, Springer International Publishing. Schubert polynomials were discovered by A. Lascoux and M. Schützenberger in the study of cohomology rings of flag manifolds in 1980s. These polynomials generalize Schur polynomials and form a linear basis of multivariate polynomials. In 2003, Lenart and Sottile introduced skew Schubert polynomials, which generalize skew Schur polynomials and expand in the Schubert basis with the generalized Littlewood–Richardson coefficients. In this paper, we initiate the study of these two families of polynomials from the perspective of computational complexity theory. We first observe that skew Schubert polynomials, and therefore Schubert polynomials, are in #P (when evaluating on nonnegative integral inputs) and VNP. Our main result is a deterministic algorithm that computes the expansion of a polynomial f of degree d in Z[ x1, ⋯ , xn] on the basis of Schubert polynomials, assuming an oracle computing Schubert polynomials. This algorithm runs in time polynomial in n, d, and the bit size of the expansion. This generalizes, and derandomizes, the sparse interpolation algorithm of symmetric polynomials in the Schur basis by Barvinok and Fomin (Adv Appl Math 18(3):271–285, 1997). In fact, our interpolation algorithm is general enough to accommodate any linear basis satisfying certain natural properties. Applications of the above results include a new algorithm that computes the generalized Littlewood–Richardson coefficients.
Nemoto, K, Devitt, S & Munro, WJ 2017, 'Noise management to achieve superiority in quantum information systems', Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 375, no. 2099, pp. 20160236-20160236.
View/Download from: Publisher's site
View description>>
Quantum information systems are expected to exhibit superiority compared with their classical counterparts. This superiority arises from the quantum coherences present in these quantum systems, which are obviously absent in classical ones. To exploit such quantum coherences, it is essential to control the phase information in the quantum state. The phase is analogue in nature, rather than binary. This makes quantum information technology fundamentally different from our classical digital information technology. In this paper, we analyse error sources and illustrate how these errors must be managed for the system to achieve the required fidelity and a quantum superiority. This article is part of the themed issue ‘Quantum technology for the 21st century’.
Wang, X, Fang, K & Tomamichel, M 2017, 'On converse bounds for classical communication over quantum channels', IEEE Transactions on Information Theory 65(7): 4609 - 4619, July 2019, vol. 65, no. 7, pp. 4609-4619.
View/Download from: Publisher's site
View description>>
We explore several new converse bounds for classical communication overquantum channels in both the one-shot and asymptotic regimes. First, we showthat the Matthews-Wehner meta-converse bound for entanglement-assistedclassical communication can be achieved by activated, no-signalling assistedcodes, suitably generalizing a result for classical channels. Second, we derivea new efficiently computable meta-converse on the amount of classicalinformation unassisted codes can transmit over a single use of a quantumchannel. As applications, we provide a finite resource analysis of classicalcommunication over quantum erasure channels, including the second-order andmoderate deviation asymptotics. Third, we explore the asymptotic analogue ofour new meta-converse, the $\Upsilon$-information of the channel. We show thatits regularization is an upper bound on the classical capacity, which isgenerally tighter than the entanglement-assisted capacity and other knownefficiently computable strong converse bounds. For covariant channels we showthat the $\Upsilon$-information is a strong converse bound.
Ying, M, Ying, S & Wu, X 2017, 'Invariants of quantum programs: characterisations and generation', ACM SIGPLAN Notices, vol. 52, no. 1, pp. 818-832.
View/Download from: Publisher's site
View description>>
Program invariant is a fundamental notion widely used in program verification and analysis. The aim of this paper is twofold: (i) find an appropriate definition of invariants for quantum programs; and (ii) develop an effective technique of invariant generation for verification and analysis of quantum programs. Interestingly, the notion of invariant can be defined for quantum programs in two different ways -- additive invariants and multiplicative invariants -- corresponding to two interpretations of implication in a continuous valued logic: the Lukasiewicz implication and the Godel implication. It is shown that both of them can be used to establish partial correctness of quantum programs. The problem of generating additive invariants of quantum programs is addressed by reducing it to an SDP (Semidefinite Programming) problem. This approach is applied with an SDP solver to generate invariants of two important quantum algorithms -- quantum walk and quantum Metropolis sampling. Our examples show that the generated invariants can be used to verify correctness of these algorithms and are helpful in optimising quantum Metropolis sampling. To our knowledge, this paper is the first attempt to define the notion of invariant and to develop a method of invariant generation for quantum programs.
Yu, N, Duan, R & Xu, Q 2017, 'Bounds on the Distance Between a Unital Quantum Channel and the Convex Hull of Unitary Channels', IEEE Transactions on Information Theory, vol. 63, no. 2, pp. 1299-1310.
View/Download from: Publisher's site
View description>>
© 2016 IEEE. Motivated by the recent resolution of asymptotic quantum birkhoff conjecture (AQBC), we attempt to estimate the distance between a given unital quantum channel and the convex hull of unitary channels. We provide two lower bounds on this distance by employing techniques from quantum information and operator algebras, respectively. We then show how to apply these results to construct some explicit counterexamples to AQBC. We also point out an interesting connection between the Grothendieck's inequality and AQBC.
Alexander-Floyd, JJ, Entezari, A, Ying, M, Haroon, S & Gidalevitz, T 1970, 'Natural genetic variation modifies polyglutamine aggregation via an imbalance in autophagy.', MOLECULAR BIOLOGY OF THE CELL, Annual Joint Meeting of the American-Society-for-Cell-Biology and the European-Molecular-Biology-Organization (ASCB/EMBO), AMER SOC CELL BIOLOGY, PA, Philadelphia.
Anshu, A, Ben-David, S, Garg, A, Jain, R, Kothari, R & Lee, T 1970, 'Separating quantum communication and approximate rank', Leibniz International Proceedings in Informatics, LIPIcs.
View/Download from: Publisher's site
View description>>
One of the best lower bound methods for the quantum communication complexity of a function H (with or without shared entanglement) is the logarithm of the approximate rank of the communication matrix of H. This measure is essentially equivalent to the approximate 2 norm and generalized discrepancy, and subsumes several other lower bounds. All known lower bounds on quantum communication complexity in the general unbounded-round model can be shown via the logarithm of approximate rank, and it was an open problem to give any separation at all between quantum communication complexity and the logarithm of the approximate rank. In this work we provide the first such separation: We exhibit a total function H with quantum communication complexity almost quadratically larger than the logarithm of its approximate rank. We construct H using the communication lookup function framework of Anshu et al. (FOCS 2016) based on the cheat sheet framework of Aaronson et al. (STOC 2016). From a starting function F, this framework defines a new function H = FG. Our main technical result is a lower bound on the quantum communication complexity of FG in terms of the discrepancy of F, which we do via quantum information theoretic arguments. We show the upper bound on the approximate rank of FG by relating it to the Boolean circuit size of the starting function F.
Anshu, A, Touchette, D, Yao, P & Yu, N 1970, 'Exponential separation of quantum communication and classical information', Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC '17: Symposium on Theory of Computing, ACM, Montreal, Canada, pp. 277-288.
View/Download from: Publisher's site
View description>>
© 2017 ACM. We exhibit a Boolean function for which the quantum communication complexity is exponentially larger than the classical information complexity. An exponential separation in the other direction was already known from the work of Kerenidis et. al. [SICOMP 44, pp. 1550-1572], hence our work implies that these two complexity measures are incomparable. As classical information complexity is an upper bound on quantum information complexity, which in turn is equal to amortized quantum communication complexity, our work implies that a tight direct sum result for distributional quantum communication complexity cannot hold. Motivated by the celebrated results of Ganor, Kol and Raz [FOCS 14, pp. 557-566, STOC 15, pp. 977-986], and by Rao and Sinha [ECCC TR15-057], we use the Symmetric k-ary Pointer Jumping function, whose classical communication complexity is exponentially larger than its classical information complexity. In this paper, we show that the quantum communication complexity of this function is polynomially equivalent to its classical communication complexity. The high-level idea behind our proof is arguably the simplest so far for such an exponential separation between information and communication, driven by a sequence of round-elimination arguments, allowing us to simplify further the approach of Rao and Sinha. As another application of the techniques that we develop, we give a simple proof for an optimal trade-off between Alice's and Bob's communication while computing the related Greater-Than function on n bits: say Bob communicates at most b bits, then Alice must send n/2O(b)bits to Bob. This holds even when allowing pre-shared entanglement. We also present a classical protocol achieving this bound.
Bei, X, Qiao, Y & Zhang, S 1970, 'Networked Fairness in Cake Cutting', Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, Twenty-Sixth International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence Organization, pp. 3632-3638.
View/Download from: Publisher's site
View description>>
We introduce a graphical framework for fair division in cake cutting, where comparisons between agents are limited by an underlying network structure. We generalize the classical fairness notions of envy-freeness and proportionality in this graphical setting. An allocation is called envy-free on a graph if no agent envies any of her neighbor's share, and is called proportional on a graph if every agent values her own share no less than the average among her neighbors, with respect to her own measure. These generalizations enable new research directions in developing simple and efficient algorithms that can produce fair allocations under specific graph structures.On the algorithmic frontier, we first propose a moving-knife algorithm that outputs an envy-free allocation on trees. The algorithm is significantly simpler than the discrete and bounded envy-free algorithm introduced in [Aziz and Mackenzie, 2016] for compete graphs. Next, we give a discrete and bounded algorithm for computing a proportional allocation on transitive closure of trees, a class of graphs by taking a rooted tree and connecting all its ancestor-descendant pairs.
Belovs, A, Ivanyos, G, Qiao, Y, Santha, M & Yang, S 1970, 'On the polynomial parity argument complexity of the combinatorial nullstellensatz', Leibniz International Proceedings in Informatics, LIPIcs.
View/Download from: Publisher's site
View description>>
The complexity class PPA consists of NP-search problems which are reducible to the parity principle in undirected graphs. It contains a wide variety of interesting problems from graph theory, combinatorics, algebra and number theory, but only a few of these are known to be complete in the class. Before this work, the known complete problems were all discretizations or combinatorial analogues of topological fixed point theorems. Here we prove the PPA-completeness of two problems of radically different style. They are PPA-Circuit CNSS and PPA-Circuit Chevalley, related respectively to the Combinatorial Nullstellensatz and to the Chevalley-Warning Theorem over the two elements field F2. The input of these problems contain PPA-circuits which are arithmetic circuits with special symmetric properties that assure that the polynomials computed by them have always an even number of zeros. In the proof of the result we relate the multilinear degree of the polynomials to the parity of the maximal parse subcircuits that compute monomials with maximal multilinear degree, and we show that the maximal parse subcircuits of a PPA-circuit can be paired in polynomial time.
Cheng, H-C, Hsieh, M-H & Tomamichel, M 1970, 'Sphere-packing bound for classical-quantum channels', 2017 IEEE Information Theory Workshop (ITW), 2017 IEEE Information Theory Workshop (ITW), IEEE, Kaohsiung, Taiwan, pp. 479-483.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. We study lower bounds on the optimal error probability in channel coding at rates below capacity, commonly termed sphere-packing bounds. In this work, we establish a sphere-packing bound for classical-quantum channels, which significantly improves previous prefactor from the order of subexponential to polynomial. Furthermore, the gap between the obtained error exponent for constant composition codes and the best known classical random coding exponent vanishes in the order of o(log n/n), indicating our sphere-packing bound is almost exact in the high rate regime. The main technical contributions are two converse Hoeffding bounds for quantum hypothesis testing and the saddle-point properties of error exponent functions.
Cheng, H-C, Hsieh, M-H & Tomamichel, M 1970, 'Sphere-Packing Bound for Symmetric Classical-Quantum Channels', IEEE International Symposium on Information Theory - Proceedings, IEEE International Symposium on Information Theory, IEEE, Aachen, Germany, pp. 286-290.
View/Download from: Publisher's site
View description>>
We provide a sphere-packing lower bound for the optimal error probability infinite blocklengths when coding over a symmetric classical-quantum channel. Ourresult shows that the pre-factor can be significantly improved from the orderof the subexponential to the polynomial. The established pre-factor isessentially optimal because it matches the best known random coding upper boundin the classical case. Our approaches rely on a sharp concentration inequalityin strong large deviation theory and crucial properties of the error-exponentfunction.
Chubb, CT, Tan, VYF & Tomamichel, M 1970, 'Moderate deviation analysis for classical communication over quantum channels', 2017 IEEE International Symposium on Information Theory (ISIT), 2017 IEEE International Symposium on Information Theory (ISIT), IEEE, Vail, CO, USA, pp. 1544-1548.
View/Download from: Publisher's site
Haque, MN, Mathieson, L & Moscato, P 1970, 'A memetic algorithm for community detection by maximising the connected cohesion', 2017 IEEE Symposium Series on Computational Intelligence (SSCI), 2017 IEEE Symposium Series on Computational Intelligence (SSCI), IEEE, Honolulu, Hawaii, USA, pp. 1-8.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. Community detection is an exciting field of research which has attracted the interest of many researchers during the last decade. While many algorithms and heuristics have been proposed to scale existing approaches a relatively smaller number of studies have looked at exploring different measures of quality of the detected community. Recently, a new score called 'cohesion' was introduced in the computing literature. The cohesion score is based comparing the number of triangles in a given group of vertices to the number of triangles only partly in that group. In this contribution, we propose a memetic algorithm that aims to find a subset of the vertices of an undirected graph that maximizes the cohesion score. The associated combinatorial optimisation problem is known to be NP-Hard and we also prove it to be W[1]-hard when parameterized by the score. We used a Local Search individual improvement heuristic to expand the putative solution. Then we removed all vertices from the group which are not a part of any triangle and expand the neighbourhood by adding triangles which have at least two nodes already in the group. Finally we compute the maximum connected component of this group. The highest quality solutions of the memetic algorithm have been obtained for four real-world network scenarios and we compare our results with ground-truth information about the graphs. We also compare the results to those obtained with eight other community detection algorithms via interrater agreement measures. Our results give a new lower bound on the parameterized complexity of this problem and give novel insights on its potential usefulness as a new natural score for community detection.
Ivanyos, G, Qiao, Y & Venkata Subrahmanyam, K 1970, 'Constructive non-commutative rank computation is in deterministic polynomial time', Leibniz International Proceedings in Informatics Lipics, Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl, Berkeley, CA, USA, pp. 1-18.
View/Download from: Publisher's site
View description>>
Let B be a linear space of matrices over a field F spanned by n × n matrices B1, . . . ,Bm. The non-commutative rank of B is the minimum r € N such that there exists U < Fn satisfying dim(U) - dim(B(U)) n - r, where B(U) := span(Ui2€[m]Bi (U)). Computing the non-commutative rank generalizes some well-known problems including the bipartite graph maximum matching problem and the linear matroid intersection problem. In this paper we give a deterministic polynomial-Time algorithm to compute the non-commutative rank over any field F. Prior to our work, such an algorithm was only known over the rational number field Q, a result due to Garg et al, [20]. Our algorithm is constructive and produces a witness certifying the non-commutative rank, a feature that is missing in the algorithm from [20]. Our result is built on techniques which we developed in a previous paper [24], with a new reduction procedure that helps to keep the blow-up parameter small. There are two ways to realize this reduction. The first involves constructivizing a key result of Derksen and Makam [12] which they developed in order to prove that the null cone of matrix semi-invariants is cut out by generators whose degree is polynomial in the size of the matrices involved. We also give a second, simpler method to achieve this. This gives another proof of the polynomial upper bound on the degree of the generators cutting out the null cone of matrix semi-invariants. Both the invariant-Theoretic result and the algorithmic result rely crucially on the regularity lemma proved in [24]. In this paper we improve on the constructive version of the regularity lemma from [24] by removing a technical coprime condition that was assumed there.
Ji, Z 1970, 'Compression of quantum multi-prover interactive proofs', Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC '17: Symposium on Theory of Computing, ACM, Montreal, Canada, pp. 289-302.
View/Download from: Publisher's site
View description>>
© 2017 ACM. We present a protocol that transforms any quantum multi-prover interactive proof into a nonlocal game in which questions consist of logarithmic number of bits and answers of constant number of bits. As a corollary, it follows that the promise problem corresponding to the approximation of the nonlocal value to inverse polynomial accuracy is complete for QMIP∗, and therefore NEXP-hard. This establishes that nonlocal games are provably harder than classical games without any complexity theory assumptions. Our result also indicates that gap amplification for nonlocal games may be impossible in general and provides a negative evidence for the feasibility of the gap amplification approach to the multi-prover variant of the quantum PCP conjecture.
Kong, S, Lee, JH & Li, S 1970, 'A deterministic distributed algorithm for reasoning with connected row-convex constraints', Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, International Conference on Autonomous Agents and Multiagent System, International Foundation for Autonomous Agents and Multiagent Systems, São Paulo, Brazil, pp. 203-211.
View description>>
The class of CRC constraints generalizes several tractable classes of constraints and is expressive enough to model problems in domains such as temporal reasoning, geometric reasoning, and scene labelling. This paper presents the first distributed deterministic algorithm for connected row-convex (CRC) constraints. Our distributed (partial) path consistency algorithm efficiently transforms a CRC constraint network into an equivalent constraint network, where all constraints are minimal (i.e., they are the tightest constraints) and generating all solutions can be done in a backtrack- free manner. When compared with the state-of-ihe-Art distributed algorithm for CRC constraints, which is a randomized one, our algorithm guarantees to generate a solution for satisfiable CRC constraint networks and it is applicable to solve large networks in real distributed systems. The experimental evaluations show that our algorithm outperforms the statc-of-Thc-Art algorithm in both practice and theory.
Li, S, Long, Z, Liu, W, Duckham, M & Both, A 1970, 'On Redundant Topological Constraints (Extended Abstract)', Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, Twenty-Sixth International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence Organization, Melbourne, Australia, pp. 5020-5024.
View/Download from: Publisher's site
View description>>
Redundancy checking is an important task in AI subfields such as knowledge representation and constraint solving. This paper considers redundant topological constraints, defined in the region connection calculus RCC8. We say a constraint in a set C of RCC8 constraints is redundant if it is entailed by the rest of C. A prime subnetwork of C is a subset of C which contains no redundant constraints and has the same solution set as C. It is natural to ask how to compute such a prime subnetwork, and when it is unique. While this problem is in general intractable, we show that, if S is a subalgebra of RCC8 in which weak composition distributes over nonempty intersections, then C has a unique prime subnetwork, which can be obtained in cubic time by removing all redundant constraints simultaneously from C. As a by-product, we show that any path-consistent network over such a distributive subalgebra is minimal.
Li, Y & Qiao, Y 1970, 'Linear Algebraic Analogues of the Graph Isomorphism Problem and the Erdős-Rényi Model', 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, Berkeley, CA, USA, pp. 463-474.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. A classical difficult isomorphism testing problem is to test isomorphism of p-groups of class 2 and exponent p in time polynomial in the group order. It is known that this problem can be reduced to solving the alternating matrix space isometry problem over a finite field in time polynomial in the underlying vector space size. We propose a venue of attack for the latter problem by viewing it as a linear algebraic analogue of the graph isomorphism problem. This viewpointleads us to explore the possibility of transferring techniques for graph isomorphism to this long-believed bottleneck case of group isomorphism.In 1970s, Babai, Erds, and Selkow presented the first average-case efficient graph isomorphism testing algorithm (SIAM J Computing, 1980). Inspired by that algorithm, we devise an average-case efficient algorithm for the alternating matrix space isometry problem over a key range of parameters, in a random model of alternating matrix spaces in vein of the Erdos-R4;enyi model of random graphs. For this, we develop a linear algebraic analogue of the classical individualisation technique, a technique belonging to a set of combinatorial techniques that has been critical for the progress on the worst-case time complexity for graph isomorphism, but was missing in the group isomorphism context. This algorithm also enables us to improve Higmans 57-year-old lower bound on the number of p-groups (Proc. of the LMS, 1960). We finally show that Luks dynamic programming technique for graph isomorphism (STOC 1999) can be adapted to slightly improve the worst-case time complexity of the alternating matrix space isometry problem in a certain range of parameters.Most notable progress on the worst-case time complexity of graph isomorphism, including Babais recent breakthrough (STOC 2016) and Babai and Luks previous record (STOC 1983), has relied on both group theoretic and combinatorial techniques. By developing a linear algebraic analogue of the individu...
Sutter, D, Berta, M & Tomamichel, M 1970, 'Quantum Markov chains and logarithmic trace inequalities', 2017 IEEE International Symposium on Information Theory (ISIT), 2017 IEEE International Symposium on Information Theory (ISIT), IEEE, Aachen, Germany, pp. 1988-1992.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. A Markov chain is a tripartite quantum state ρABC where there exists a recovery map RB→BC such that ρABC = RB→BC(ρAB). More generally, an approximate Markov chain ρABC is a state whose distance to the closest recovered state RB→BC(ρAB) is small. Recently it has been shown that this distance can be bounded from above by the conditional mutual information I(A: C|B)ρ of the state. We improve on this connection by deriving the first bound that is tight in the commutative case and features an explicit recovery map that only depends on the reduced state pBC. The key tool in our proof is a multivariate extension of the Golden-Thompson inequality, which allows us to extend logarithmic trace inequalities from two to arbitrarily many matrices.
Wilde, MM, Tomamichel, M & Berta, M 1970, 'A meta-converse for private communication over quantum channels', 2017 IEEE International Symposium on Information Theory (ISIT), 2017 IEEE International Symposium on Information Theory (ISIT), IEEE, Aachen, Germany, pp. 291-295.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. We establish a converse bounds on the private transmission capabilities of a quantum channel. The main conceptual development builds firmly on the notion of a private state, which is a powerful, uniquely quantum method for simplifying the tripartite picture of privacy involving local operations and public classical communication to a bipartite picture of quantum privacy involving local operations and classical communication. This approach has previously led to some of the strongest upper bounds on secret key rates, including the squashed entanglement and the relative entropy of entanglement. Here we use this approach along with a "privacy test" to establish a general meta-converse bound for private communication.
Ying, M, Ying, S & Wu, X 1970, 'Invariants of quantum programs: characterisations and generation.', POPL, ACM SIGPLAN Symposium on Principles of Programming Languages, ACM, Paris, France, pp. 818-832.
View/Download from: Publisher's site
View description>>
© 2017 ACM. Program invariant is a fundamental notion widely used in program verification and analysis. The aim of this paper is twofold: (i) find an appropriate definition of invariants for quantum programs; and (ii) develop an effective technique of invariant generation for ver- ification and analysis of quantum programs. Interestingly, the no- tion of invariant can be defined for quantum programs in two d- ifferent ways - additive invariants and multiplicative invariants - corresponding to two interpretations of implication in a continuous valued logic: the £ukasiewicz implication and the Godel implica- tion. It is shown that both of them can be used to establish partial correctness of quantum programs. The problem of generating ad- ditive invariants of quantum programs is addressed by reducing it to an SDP (Semidefinite Programming) problem. This approach is applied with an SDP solver to generate invariants of two important quantum algorithms - quantum walk and quantum Metropolis sam- pling. Our examples show that the generated invariants can be used to verify correctness of these algorithms and are helpful in optimis- ing quantum Metropolis sampling. To our knowledge, this paper is the first attempt to define the notion of invariant and to develop a method of invariant generation for quantum programs.
Zhou, L & Ying, M 1970, 'Differential Privacy in Quantum Computation.', CSF, IEEE Computer Security Foundations Symposium, IEEE Computer Society, Santa Barbara, CA, USA, pp. 249-262.
View/Download from: Publisher's site
View description>>
© 2017 IEEE. More and more quantum algorithms have been designed for solving problems in machine learning, database search and data analytics. An important problem then arises: how privacy can be protected when these algorithms are used on private data? For classical computing, the notion of differential privacy provides a very useful conceptual framework in which a great number of mechanisms that protect privacy by introducing certain noises into algorithms have been successfully developed. This paper defines a notion of differential privacy for quantum information processing. We carefully examine how the mechanisms using three important types of quantum noise, the amplitude/phase damping and depolarizing, can protect differential privacy. A composition theorem is proved that enables us to combine multiple privacy-preserving operations in quantum information processing.
Aggarwal, D, Brennen, GK, Lee, T, Santha, M & Tomamichel, M 2017, 'Quantum attacks on Bitcoin, and how to protect against them'.
View description>>
The key cryptographic protocols used to secure the internet and financialtransactions of today are all susceptible to attack by the development of asufficiently large quantum computer. One particular area at risk arecryptocurrencies, a market currently worth over 150 billion USD. We investigatethe risk of Bitcoin, and other cryptocurrencies, to attacks by quantumcomputers. We find that the proof-of-work used by Bitcoin is relativelyresistant to substantial speedup by quantum computers in the next 10 years,mainly because specialized ASIC miners are extremely fast compared to theestimated clock speed of near-term quantum computers. On the other hand, theelliptic curve signature scheme used by Bitcoin is much more at risk, and couldbe completely broken by a quantum computer as early as 2027, by the mostoptimistic estimates. We analyze an alternative proof-of-work called Momentum,based on finding collisions in a hash function, that is even more resistant tospeedup by a quantum computer. We also review the available post-quantumsignature schemes to see which one would best meet the security and efficiencyrequirements of blockchain applications.
Berry, DW, Kieferová, M, Scherer, A, Sanders, YR, Low, GH, Wiebe, N, Gidney, C & Babbush, R 2017, 'Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians'.
Chubb, CT, Tomamichel, M & Korzekwa, K 2017, 'Beyond the thermodynamic limit: finite-size corrections to state interconversion rates'.
View description>>
Thermodynamics is traditionally constrained to the study of macroscopicsystems whose energy fluctuations are negligible compared to their averageenergy. Here, we push beyond this thermodynamic limit by developing amathematical framework to rigorously address the problem of thermodynamictransformations of finite-size systems. More formally, we analyse stateinterconversion under thermal operations and between arbitraryenergy-incoherent states. We find precise relations between the optimal rate atwhich interconversion can take place and the desired infidelity of the finalstate when the system size is sufficiently large. These so-called second-orderasymptotics provide a bridge between the extreme cases of single-shotthermodynamics and the asymptotic limit of infinitely large systems. Weillustrate the utility of our results with several examples. We first show howthermodynamic cycles are affected by irreversibility due to finite-sizeeffects. We then provide a precise expression for the gap between thedistillable work and work of formation that opens away from the thermodynamiclimit. Finally, we explain how the performance of a heat engine gets affectedwhen one of the heat baths it operates between is finite. We find that whileperfect work cannot generally be extracted at Carnot efficiency, there areconditions under which these finite-size effects vanish. In deriving ourresults we also clarify relations between different notions of approximatemajorisation.
Herr, D, Paler, A, Devitt, SJ & Nori, F 2017, 'A local and scalable lattice renormalization method for ballistic quantum computation'.
Herr, D, Paler, A, Devitt, SJ & Nori, F 2017, 'Lattice Surgery on the Raussendorf Lattice'.
Kong, S, Lee, JH & Li, S 2017, 'Multiagent Simple Temporal Problem: The Arc-Consistency Approach'.
View description>>
The Simple Temporal Problem (STP) is a fundamental temporal reasoning problemand has recently been extended to the Multiagent Simple Temporal Problem(MaSTP). In this paper we present a novel approach that is based on enforcingarc-consistency (AC) on the input (multiagent) simple temporal network. We showthat the AC-based approach is sufficient for solving both the STP and MaSTP andprovide efficient algorithms for them. As our AC-based approach does not imposenew constraints between agents, it does not violate the privacy of the agentsand is superior to the state-of-the-art approach to MaSTP. Empiricalevaluations on diverse benchmark datasets also show that our AC-basedalgorithms for STP and MaSTP are significantly more efficient than existingapproaches.
Liu, S, Wang, X, Zhou, L, Guan, J, Li, Y, He, Y, Duan, R & Ying, M 2017, '$Q|SI\rangle$: A Quantum Programming Environment', Symposium on Real-Time and Hybrid Systems.
View description>>
This paper describes a quantum programming environment, named $Q|SI\rangle$.It is a platform embedded in the .Net language that supports quantumprogramming using a quantum extension of the $\mathbf{while}$-language. Theframework of the platform includes a compiler of the quantum$\mathbf{while}$-language and a suite of tools for simulating quantumcomputation, optimizing quantum circuits, and analyzing and verifying quantumprograms. Throughout the paper, using $Q|SI\rangle$ to simulate quantumbehaviors on classical platforms with a combination of components isdemonstrated. The scalable framework allows the user to program customizedfunctions on the platform. The compiler works as the core of $Q|SI\rangle$bridging the gap from quantum hardware to quantum software. The built-indecomposition algorithms enable the universal quantum computation on thepresent quantum hardware.
Madhav, KV, Biswas, T & Ghosh, S 2017, 'Coarse-graining of measurement and quantum-to-classical transition in the bipartite scenario'.
View description>>
The connection between coarse-graining of measurement and emergence of
classicality has been investigated for some time, if not well understood.
Recently in (PRL $\textbf{112}$, 010402, (2014)) it was pointed out that
coarse-graining measurements can lead to non-violation of Bell-type
inequalities by a state which would violate it under sharp measurements. We
study here the effects of coarse-grained measurements on bipartite cat states.
We show that while it is true that coarse-graining does indeed lead to
non-violation of a Bell-type inequality, this is not reflected at the state
level. Under such measurements the post-measurement states can be non-classical
(in the quantum optical sense) and in certain cases coarse-graning can lead to
an increase in this non-classicality with respect to the coarse-graining
parameter. While there is no universal way to quantify non-classicality, we do
so using well understood notions in quantum optics such as the negativity of
the Wigner function and the singular nature of the Gluaber-Sudharshan P
distribution.
Mann, RL & Bremner, MJ 2017, 'On the Complexity of Random Quantum Computations and the Jones Polynomial'.
View description>>
There is a natural relationship between Jones polynomials and quantum
computation. We use this relationship to show that the complexity of evaluating
relative-error approximations of Jones polynomials can be used to bound the
classical complexity of approximately simulating random quantum computations.
We prove that random quantum computations cannot be classically simulated up to
a constant total variation distance, under the assumption that (1) the
Polynomial Hierarchy does not collapse and (2) the average-case complexity of
relative-error approximations of the Jones polynomial matches the worst-case
complexity over a constant fraction of random links. Our results provide a
straightforward relationship between the approximation of Jones polynomials and
the complexity of random quantum computations.
Mills, PW, Rundle, RP, Samson, JH, Devitt, SJ, Tilma, T, Dwyer, VM & Everitt, MJ 2017, 'On quantum invariants and the graph isomorphism problem'.
Paler, A & Devitt, SJ 2017, 'A Specification Format and a Verification Method of Fault-Tolerant Quantum Circuits'.
Ying, S, Ying, M & Feng, Y 2017, 'Quantum Privacy-Preserving Data Analytics.'.
Ying, S, Ying, M & Feng, Y 2017, 'Quantum Privacy-Preserving Perceptron.'.
Zhang, J, Devitt, SJ, You, JQ & Nori, F 2017, 'Holonomic Surface Codes for Fault-Tolerant Quantum Computation'.
