Chen, J, Duan, R, Ji, Z, Ying, M & Yu, J 2008, 'Existence of universal entangler', JOURNAL OF MATHEMATICAL PHYSICS, vol. 49, no. 1, pp. 1-7.
View/Download from: Publisher's site
View description>>
A gate is called an entangler if it transforms some (pure) product states to entangled states. A universal entangler is a gate which transforms all product states to entangled states. In practice, a universal entangler is a very powerful device for generating entanglements, and thus provides important physical resources for accomplishing many tasks in quantum computing and quantum information. This paper demonstrates that a universal entangler always exists except for a degenerated case. Nevertheless, the problem how to find a universal entangler remains open. © 2008 American Institute of Physics.
de Burgh, MD, Langford, NK, Doherty, AC & Gilchrist, A 2008, 'Choice of measurement sets in qubit tomography', Physical Review A, vol. 78, no. 5.
View/Download from: Publisher's site
Devitt, SJ, Fowler, AG, Stephens, AM, Greentree, AD, Hollenberg, LCL, Munro, WJ & Nemoto, K 2008, 'Architectural design for a topological cluster state quantum computer', New. J. Phys., vol. 11, p. 083032.
View/Download from: Publisher's site
View description>>
The development of a large scale quantum computer is a highly sought aftergoal of fundamental research and consequently a highly non-trivial problem.Scalability in quantum information processing is not just a problem of qubitmanufacturing and control but it crucially depends on the ability to adaptadvanced techniques in quantum information theory, such as error correction, tothe experimental restrictions of assembling qubit arrays into the millions. Inthis paper we introduce a feasible architectural design for large scale quantumcomputation in optical systems. We combine the recent developments intopological cluster state computation with the photonic module, a simple chipbased device which can be used as a fundamental building block for a largescale computer. The integration of the topological cluster model with thiscomparatively simple operational element addresses many significant issues inscalable computing and leads to a promising modular architecture with completeintegration of active error correction exhibiting high fault-tolerantthresholds.
Devitt, SJ, Munro, WJ & Nemoto, K 2008, 'High Performance Quantum Computing', Progress in Informatics 8 (2011): 49-55, no. 8, pp. 49-55.
View/Download from: Publisher's site
View description>>
The architecture scalability afforded by recent proposals of a large scalephotonic based quantum computer, utilizing the theoretical developments oftopological cluster states and the photonic chip, allows us to move on to adiscussion of massively scaled Quantum Information Processing (QIP). In thisletter we introduce the model for a secure and unsecured topological clustermainframe. We consider the quantum analogue of High Performance Computing,where a dedicated server farm is utilized by many users to run algorithms andshare quantum data. The scaling structure of photonics based topologicalcluster computing leads to an attractive future for server based QIP, wherededicated mainframes can be constructed and/or expanded to serve anincreasingly hungry user base with the ideal resource for individual quantuminformation processing.
Duan, R, Feng, Y & Ying, M 2008, 'Local distinguishability of multipartite unitary operations', PHYSICAL REVIEW LETTERS, vol. 100, no. 2, pp. 1-4.
View/Download from: Publisher's site
View description>>
We show that any two different unitary operations acting on an arbitrary multipartite quantum system can be perfectly distinguished by local operations and classical communication when a finite number of runs is allowed. Intuitively, this result indicates that the lost identity of a nonlocal unitary operation can be recovered locally. No entanglement between distant parties is required. © 2008 The American Physical Society.
Duer, W, Bremner, MJ & Briegel, HJ 2008, 'Quantum simulation of interacting high-dimensional systems: The influence of noise', PHYSICAL REVIEW A, vol. 78, no. 5, p. 052325.
View/Download from: Publisher's site
View description>>
We consider the simulation of interacting high-dimensional systems using pairwise interacting qubits. The main tool in this context is the generation of effective many-body interactions, and we examine a number of different protocols for obtaining them. These methods include the usage of higher-order processes commutator method , unitary conjugation or graph state encoding, as well as teleportation-based approaches. We illustrate and compare these methods in detail and analyze the time cost for simulation. In the second part of the paper, we investigate the influence of noise on the simulation process. We concentrate on errors in the interaction Hamiltonians and consider two generic noise models: i timing errors in pairwise interactions and ii noisy pairwise interactions described by Master equations of Lindblad form. We analyze and compare the effect of noise for the different simulation methods and propose a way to significantly reduce the influence of noise by making use of entanglement purification together with a teleportation-based protocol.
Ji, Z, Wang, G, Duan, R, Feng, Y & Ying, M 2008, 'Parameter Estimation of Quantum Channels', IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 54, no. 11, pp. 5172-5185.
View/Download from: Publisher's site
View description>>
The efficiency of parameter estimation of quantum channels is studied in this paper. We introduce the concept of programmable parameters to the theory of estimation. It is found that programmable parameters obey the standard quantum limit strictly; hence, no speedup is possible in its estimation. We also construct a class of nonunitary quantum channels whose parameter can be estimated in a way that the standard quantum limit is broken. The study of estimation of general quantum channels also enables an investigation of the effect of noises on quantum estimation. © 2008 IEEE.
Lanyon, BP, Weinhold, TJ, Langford, NK, O’Brien, JL, Resch, KJ, Gilchrist, A & White, AG 2008, 'Manipulating Biphotonic Qutrits', Physical Review Letters, vol. 100, no. 6.
View/Download from: Publisher's site
Lee, T & Mittal, R 2008, 'Product theorems via semidefinite programming', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5125 LNCS, no. PART 1, pp. 674-685.
View/Download from: Publisher's site
View description>>
The tendency of semidefinite programs to compose perfectly under product hasbeen exploited many times in complexity theory: for example, by Lovasz todetermine the Shannon capacity of the pentagon; to show a direct sum theoremfor non-deterministic communication complexity and direct product theorems fordiscrepancy; and in interactive proof systems to show parallel repetitiontheorems for restricted classes of games. Despite all these examples of product theorems--some going back nearly thirtyyears--it was only recently that Mittal and Szegedy began to develop a generaltheory to explain when and why semidefinite programs behave perfectly underproduct. This theory captured many examples in the literature, but there werealso some notable exceptions which it could not explain--namely, an earlyparallel repetition result of Feige and Lovasz, and a direct product theoremfor the discrepancy method of communication complexity by Lee, Shraibman, andSpalek. We extend the theory of Mittal and Szegedy to explain these cases as well.Indeed, to the best of our knowledge, our theory captures all examples ofsemidefinite product theorems in the literature.
Lee, T & Shraibman, A 2008, 'An approximation algorithm for approximation rank', Proceedings of the Annual IEEE Conference on Computational Complexity, pp. 351-357.
View/Download from: Publisher's site
View description>>
One of the strongest techniques available for showing lower bounds on quantumcommunication complexity is the logarithm of the approximation rank of thecommunication matrix--the minimum rank of a matrix which is entrywise close tothe communication matrix. This technique has two main drawbacks: it isdifficult to compute, and it is not known to lower bound quantum communicationcomplexity with entanglement. Linial and Shraibman recently introduced a norm, called gamma_2^{alpha}, toquantum communication complexity, showing that it can be used to lower boundcommunication with entanglement. Here the parameter alpha is a measure ofapproximation which is related to the allowable error probability of theprotocol. This bound can be written as a semidefinite program and gives boundsat least as large as many techniques in the literature, although it is smallerthan the corresponding alpha-approximation rank, rk_alpha. We show that in factlog gamma_2^{alpha}(A)$ and log rk_{alpha}(A)$ agree up to small factors. Ascorollaries we obtain a constant factor polynomial time approximation algorithmto the logarithm of approximate rank, and that the logarithm of approximationrank is a lower bound for quantum communication complexity with entanglement.
Li, S & Ying, M 2008, 'Soft constraint abstraction based on semiring homomorphism', THEORETICAL COMPUTER SCIENCE, vol. 403, no. 2-3, pp. 192-201.
View/Download from: Publisher's site
View description>>
The semiring-based constraint satisfaction problems (semiring CSPs), proposed by Bistarelli, Montanari and Rossi [S. Bistarelli, U. Montanari, F. Rossi, Semiring-based constraints solving and optimization, Journal of the ACM 44 (2) (1997) 201-236], is a very general framework of soft constraints. In this paper we propose an abstraction scheme for soft constraints that uses semiring homomorphism. To find optimal solutions of the concrete problem, we first work in the abstract problem and find its optimal solutions, and then use them to solve the concrete problem. In particular, we show that a mapping preserves optimal solutions if and only if it is an order-reflecting semiring homomorphism. Moreover, for a semiring homomorphism α and a problem P over S, if t is optimal in α (P), then there is an optimal solution over(t, ̄) of P such that over(t, ̄) has the same value as t in α (P). © 2008 Elsevier B.V. All rights reserved.
Scheidl, T, Ursin, R, Kofler, J, Ramelow, S, Ma, X-S, Herbst, T, Ratschbacher, L, Fedrizzi, A, Langford, NK, Jennewein, T & Zeilinger, A 2008, 'Violation of local realism with freedom of choice', Proc. Natl. Acad. Sci. USA, vol. 107, no. 46, pp. 19708-19713.
View/Download from: Publisher's site
View description>>
Bell's theorem shows that local realistic theories place strong restrictionson observable correlations between different systems, giving rise to Bell'sinequality which can be violated in experiments using entangled quantum states.Bell's theorem is based on the assumptions of realism, locality, and thefreedom to choose between measurement settings. In experimental tests,'loopholes' arise which allow observed violations to still be explained bylocal realistic theories. Violating Bell's inequality while simultaneouslyclosing all such loopholes is one of the most significant still open challengesin fundamental physics today. In this paper, we present an experiment thatviolates Bell's inequality while simultaneously closing the locality loopholeand addressing the freedom-of-choice loophole, also closing the latter within areasonable set of assumptions. We also explain that the locality andfreedom-of-choice loopholes can be closed only within non-determinism, i.e. inthe context of stochastic local realism.
Schirmer, SG, Oi, DKL & Devitt, SJ 2008, 'Physics-based mathematical models for quantum devices via experimental system identification', Journal of Physics: Conference Series, vol. 107, pp. 012011-012011.
View/Download from: Publisher's site
Stephens, AM, Evans, ZWE, Devitt, SJ & Hollenberg, LCL 2008, 'Asymmetric quantum error correction via code conversion', Physical Review A, vol. 77, no. 6.
View/Download from: Publisher's site
Stephens, AM, Evans, ZWE, Devitt, SJ, Greentree, AD, Fowler, AG, Munro, WJ, O’Brien, JL, Nemoto, K & Hollenberg, LCL 2008, 'Deterministic optical quantum computer using photonic modules', Physical Review A, vol. 78, no. 3.
View/Download from: Publisher's site
Tomamichel, M, Colbeck, R & Renner, R 2008, 'A Fully Quantum Asymptotic Equipartition Property', IEEE Trans. on Inf. Theory 55 (2009) p. 5840-5847, vol. 55, no. 12, pp. 5840-5847.
View/Download from: Publisher's site
View description>>
The classical asymptotic equipartition property is the statement that, in thelimit of a large number of identical repetitions of a random experiment, theoutput sequence is virtually certain to come from the typical set, each memberof which is almost equally likely. In this paper, we prove a fully quantumgeneralization of this property, where both the output of the experiment andside information are quantum. We give an explicit bound on the convergence,which is independent of the dimensionality of the side information. Thisnaturally leads to a family of Renyi-like quantum conditional entropies, forwhich the von Neumann entropy emerges as a special case.
Wang, G & Ying, M 2008, 'Deterministic distributed dense coding with stabilizer states', PHYSICAL REVIEW A, vol. 77, no. 3, pp. 1-10.
View/Download from: Publisher's site
View description>>
We consider the possibility of using stabilizer states to perform deterministic dense coding among multiple senders and a single receiver. In the model we studied, the utilized stabilizer state is partitioned into several subsystems and then each subsystem is held by a distinct party. We present a sufficient condition for a stabilizer state to be useful for deterministic distributed dense coding with respect to a given partition plan. The corresponding protocol is also constructed. Furthermore, we propose a method to partially solve a more general problem of finding the set of achievable alphabet sizes for an arbitrary stabilizer state with respect to an arbitrary partition plan. Finally, our work provides a perspective from the stabilizer formalism to view the standard dense coding protocol and also unifies several previous results in a single framework. © 2008 The American Physical Society.
Wang, G & Ying, M 2008, 'Perfect many-to-one teleportation with stabilizer states', PHYSICAL REVIEW A, vol. 77, no. 3, pp. 1-12.
View/Download from: Publisher's site
View description>>
We study the possibility of performing perfect teleportation of unknown quantum states from multiple senders to a single receiver with a previously shared stabilizer state. In the model we considered, the utilized stabilizer state is partitioned into several subsystems and then each subsystem is distributed to a distinct party. We present two sufficient conditions for a stabilizer state to achieve a given nonzero teleportation capacity with respect to a given partition plan. The corresponding teleportation protocols are also explicitly given. Interestingly, we find that even mixed stabilizer states are also useful for perfect many-to-one teleportation. Finally, our work provides a perspective from stabilizer formalism to view the standard teleportation protocol and also suggests a technique for analyzing teleportation capability of multipartite entangled states. © 2008 The American Physical Society.
Witzigmann, B, Tomamichel, M, Steiger, S, Veprek, RG, Kojima, K & Schwarz, UT 2008, 'Analysis of Gain and Luminescence in Violet and Blue GaInN–GaN Quantum Wells', IEEE Journal of Quantum Electronics, vol. 44, no. 2, pp. 144-149.
View/Download from: Publisher's site
Xiao-shan Gao, Dan-tong Ouyang, Ji-gui Sun, San-jiang Li, Tian-shun Yao, Ru-zhan Lu, Chun-yi Shi, Zhan-gang Han, Jue Wang, Cun-gen Cao & Ruqian Lu 2008, 'AI in China: A Survey', IEEE Intelligent Systems, vol. 23, no. 6, pp. 26-32.
View/Download from: Publisher's site
View description>>
This article consists of nine short essays discussing research pursued by AI researchers in China and their perspectives on research in several AI subareas. The article first introduces the mechanization of mathematics, an area in which Chinese scientists have made significant contributions. It then discusses research in automated reasoning, temporal and spatial knowledge representation and reasoning, natural language understanding, intelligent diagnosis, multiagent systems, computational intelligence, large-scale knowledge processing, and several research streams integrating AI techniques with methods from other fields. Finally, the article makes suggestions concerning future AI research in China.
Greentree, AD, Jong, LM, Van Donkelaar, JA, Devitt, SJ, Cole, JH, Stephens, AM, Jamieson, DN & Hollenberg, LCL 1970, 'Spatial adiabatic passage as a quantum wire', 2008 International Conference on Nanoscience and Nanotechnology, 2008 International Conference on Nanoscience and Nanotechnology (ICONN), IEEE, Melbourne, AUSTRALIA, pp. 156-159.
View/Download from: Publisher's site
Lanyon, BP, Weinhold, TJ, Langford, NK, Barbieri, M, De Almeida, MP, Gilchrist, A, James, DFV & White, AG 1970, 'Photonic quantum computing: shor's algorithm and the road to fault-tolerance', Conference on Quantum Electronics and Laser Science (QELS) - Technical Digest Series.
View/Download from: Publisher's site
Lee, T, Shraibman, A & Spalek, R 1970, 'A Direct Product Theorem for Discrepancy', 2008 23rd Annual IEEE Conference on Computational Complexity, Twenty-Third Annual IEEE Conference on Computational Complexity - CCC 2008, IEEE, pp. 71-80.
View/Download from: Publisher's site
Li Jason Jingshi, Kowalski Tomasz, Renz Jochen & Li Sanjiang 1970, 'Combining binary constraint networks in qualitative reasoning', Frontiers in Artificial Intelligence and Applications, European Conference on Artificial Intelligence, IOS Press, Patras, Greece, pp. 515-519.
View/Download from: Publisher's site
View description>>
Constraint networks in qualitative spatial and temporal reasoning are always complete graphs. When one adds an extra element to a given network, previously unknown constraints are derived by intersections and compositions of other constraints, and this may introduce inconsistency to the overall network. Likewise, when combining two consistent networks that share a common part, the combined network may become inconsistent.
Mathieson, L & Szeider, S 1970, 'Parameterized Graph Editing with Chosen Vertex Degrees', COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PROCEEDINGS, 2nd International Conference on Combinatorial Optimization and Applications, Springer Berlin Heidelberg, St Johns, CANADA, pp. 13-22.
View/Download from: Publisher's site
Mathieson, L & Szeider, S 1970, 'The parameterized complexity of regular subgraph problems and generalizations', Conferences in Research and Practice in Information Technology Series.
View description>>
We study variants and generalizations of the problem of finding an r-regular subgraph (where r ≥ 3) in a given graph by deleting at most k vertices. Moser and Thilikos (2006) have shown that the problem is fixed-parameter tractable (FPT) if parameterized by (k, r). They asked whether the problem remains fixed-parameter tractable if parameterized by k alone. We answer this question negatively: we show that if parameterized by k alone the problem is W[1]-hard and therefore very unlikely fixed-parameter tractable. We also give W[1]-hardness results for variants of the problem where the parameter is the number of vertex and edge deletions allowed, and for a new generalized form of the problem where the obtained subgraph is not necessarily regular but its vertices have certain prescribed degrees. Following this we demonstrate fixed-parameter tractability for the considered problems if the parameter includes the regularity r or an upper bound on the prescribed degrees in the generalized form of the problem. These FPT results are obtained via kernelization, so also provide a practical approach to the problems presented. © 2008, Australian Computer Society, Inc.
Qiao, Y & Tartary, C 1970, 'Counting Method for Multi-party Computation over Non-abelian Groups', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Cryptology and Network Security, Springer Berlin Heidelberg, Hong Kong, pp. 162-177.
View/Download from: Publisher's site
View description>>
In the Crypto'07 paper [5], Desmedt et al. studied the problem of achieving secure n-party computation over non-Abelian groups. The function to be computed is f G (x 1,...,x n ) :∈=∈x 1 •...•x n where each participant P i holds an input x i from the non-commutative group G. The settings of their study are the passive adversary model, information-theoretic security and black-box group operations over G. They presented three results. The first one is that honest majority is needed to ensure security when computing f G . Second, when the number of adversary , they reduced building such a secure protocol to a graph coloring problem and they showed that there exists a deterministic secure protocol computing f G using exponential communication complexity. Finally, Desmedt et al. turned to analyze random coloring of a graph to show the existence of a probabilistic protocol with polynomial complexity when t∈<∈n/μ, in which μ is a constant less than 2.948. We call their analysis method of random coloring the counting method as it is based on the counting of the number of a specific type of random walks. This method is inspiring because, as far as we know, it is the first instance in which the theory of self-avoiding walk appears in multiparty computation. In this paper, we first give an altered exposition of their proof. This modification will allow us to adapt this method to a different lattice and reduce the communication complexity by 1/3, which is an important saving for practical implementations of the protocols. We also show the limitation of the counting method by presenting a lower bound for this technique. In particular, we will deduce that this approach would not achieve the optimal collusion resistance. © 2008 Springer Berlin Heidelberg.
Schirmer, SG, Kandasamy, G & Devitt, SJ 1970, 'Control paradigms for quantum engineering', 2008 3rd International Symposium on Communications, Control and Signal Processing, 2008 3rd International Symposium on Communications, Control and Signal Processing (ISCCSP), IEEE, St Julians, MALTA, pp. 966-971.
View/Download from: Publisher's site
Zhang, X, Liu, W, Li, S & Ying, M 1970, 'Reasoning with Cardinal Directions: An Efficient Algorithm.', AAAI, National Conference of the American Association for Artificial Intelligence, AAAI Press, Chicago, Illinois, USA, pp. 387-392.
View description>>
Direction relations between extended spatial objects are important commonsense knowledge. Recently, Goyal and Egenhofer proposed a formal model, called Cardinal Direction Calculus (CDC), for representing direction relations between connected plane regions. CDC is perhaps the most expressive qualitative calculus for directional information, and has attracted increasing interest from areas such as artificial intelligence, geographical information science, and image retrieval. Given a network of CDC constraints, the consistency problem is deciding if the network is realizable by connected regions in the real plane. This paper provides a cubic algorithm for checking consistency of basic CDC constraint networks. As one byproduct, we also show that any consistent network of CDC constraints has a canonical realization in digital plane. The cubic algorithm can also been adapted to cope with disconnected regions, in which case the current best algorithm is of time complexity O(n5).
