检索结果-内蒙古大学图书馆

Optical quantum communication complexity in the simultaneous-message-passing model

Physical Review A 2020年第6期102卷 062608-062608页

作者： Ashutosh Marwah Dave Touchette Institute for Quantum Computing Department of Physics and Astronomy University of Waterloo 200 University Ave W Waterloo N2L 3G1 ON Canada Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo 200 University Ave W Waterloo N2L 3G1 ON Canada Perimeter Institute for Theoretical Physics 31 Caroline St N Waterloo N2L 2Y5 ON Canada

The communication cost of a classical protocol is typically measured in terms of the number of bits communicated for this determines the time required for communication during the protocol. Similarly, for quantum communication protocols, which use finite-dimensional quantum states, the communication cost is measured in terms of the number of qubits communicated. However, in quantum physics, one can also use infinite-dimensional states, like optical quantum states, for communication protocols. Communication cost measures based on counting the (equivalent) number of qubits transmitted during communication cannot be directly used to measure the cost of such protocols, which use infinite-dimensional states. Moreover, one cannot infer any physical property of infinite-dimensional protocols using such qubit-based communication costs. In this paper, we provide a framework to understand the growth of physical resources in infinite-dimensional protocols. We focus on optical protocols for the sake of concreteness. The time required for communication and the energy expended during communication are identified as the important physical resources of such protocols. In an optical protocol, the time required for communication is determined by the number of time-bin modes that are transmitted from one party to another. The mean photon number of the messages sent determines the energy required during communication in the protocol. We prove a lower bound on the tradeoff between the growth of these two quantities with the growth of the problem size. We call such tradeoff relations optical quantum communication complexity relations.

关键词： quantum communication quantum protocols

来源：评论

学校读者我要写书评

暂无评论

quantum circuit placement

Quantum circuit placement

引用

作者： Maslov, Dmitri Falconer, Sean M. Mosca, Michele Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo Waterloo ON N2L 3G1 Canada Department of Computer Science University of Victoria Victoria BC V8W 3P6 Canada St. Jerome's University Waterloo ON N2L 3G3 Canada Perimeter Institute for Theoretical Physics Waterloo ON N2L 2Y5 Canada

We study the problem of the practical realization of an abstract quantum circuit when executed on a quantum hardware. By practical, we mean adapting the circuit to particulars of the physical environment which restricts/complicates the establishment of certain direct interactions between qubits. This is a quantum version of the classical circuit placement problem. We study the theoretical aspects of the problem and also present empirical results that match the best known solutions that have been developed by experimentalists. Finally, we discuss the efficiency of the approach and the scalability of its implementation with regard to the future development of quantum hardware. © 2006 IEEE.

关键词： Networks (circuits)

来源：评论

学校读者我要写书评

暂无评论

Reducing the CNOT count for Clifford+T circuits on NISQ architectures

arXiv

引用

arXiv 2020年

作者： Gheorghiu, Vlad Huang, Jiaxin Li, Sarah Meng Mosca, Michele Mukhopadhyay, Priyanka Institute for Quantum Computing University of Waterloo WaterlooON Canada SoftwareQ Inc. KitchenerON Canada Faculty of Mathematics University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo WaterlooON Canada Perimeter Institute for Theoretical Physics Waterloo WaterlooON Canada

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

关键词： Qubits

来源：评论

学校读者我要写书评

暂无评论

A unified approach to source and message compression

arXiv

引用

arXiv 2017年

作者： Anshu, Anurag Jain, Rahul Warsi, Naqueeb Ahmad Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Perimeter Institute for Theoretical Physics Canada Center for Quantum Technologies National University of Singapore and MajuLab UMI 3654 Singapore Center for Quantum Technologies National University of Singapore School of Physical and Mathematical Sciences Nanyang Technological University Singapore IIITD Delhi India

We study the problem of source and message compression in the one-shot setting for the point-to-point and multiparty scenarios (with and without side information). We derive achievability results for these tasks in a unified manner, using the techniques of convex-split, which was introduced in [1] and position-based decoding introduced in [2], which in turn uses hypothesis testing between distributions. These results are in terms of smooth max divergence and smooth hypothesis testing divergence. As a by-product of the tasks studied in this work, we obtain several known source compression results (originally studied in the asymptotic and i.i.d. setting) in the one-shot case. One of our achievability results includes the problem of message compression with side information, originally studied in [3]. We show that both our result and the result in [3] are near optimal in the one-shot setting by proving a converse bound. Copyright © 2017, The Authors. All rights reserved.

关键词： Machine learning

来源：评论

学校读者我要写书评

暂无评论

On the complexity of sampling from shallow Brownian circuits

arXiv

引用

arXiv 2024年

作者： Bentsen, Gregory Fefferman, Bill Ghosh, Soumik Gullans, Michael J. Liu, Yinchen Department of Physics The College of William & Mary United States Department of Computer Science The University of Chicago United States Joint Center for Quantum Information and Computer Science University of Maryland and NIST United States Department of Combinatorics and Optimization University of Waterloo Canada Institute for Quantum Computing University of Waterloo Canada

While many statistical properties of deep random quantum circuits can be deduced, often rigorously and other times heuristically, by an approximation to global Haar-random unitaries, the statistics of constant-depth random quantum circuits are generally less well-understood due to a lack of amenable tools and techniques. We circumvent this barrier by considering a related constant-time Brownian circuit model which shares many similarities with constant-depth random quantum circuits but crucially allows for direct calculations of higher order moments of its output distribution. Using mean-field (large-n) techniques, we fully characterize the output distributions of Brownian circuits at shallow depths and show that they follow a Porter-Thomas distribution, just like in the case of deep circuits, but with a truncated Hilbert space. The access to higher order moments allows for studying the expected and typical Linear Cross-entropy (XEB) benchmark scores achieved by an ideal quantum computer versus the state-of-the-art classical spoofers for shallow Brownian circuits. We discover that for these circuits, while the quantum computer typically scores within a constant factor of the expected value, the classical spoofer suffers from an exponentially larger variance. Numerical evidence suggests that the same phenomenon also occurs in constant-depth discrete random quantum circuits, like those defined over the all-to-all architecture. We conjecture that the same phenomenon is also true for random brickwork circuits in high enough spatial dimension. Copyright © 2024, The Authors. All rights reserved.

关键词： quantum computers

来源：评论

学校读者我要写书评

暂无评论

On the CNOT-complexity of CNOT-phase circuits

arXiv

引用

arXiv 2017年

作者： Amy, Matthew Azimzadeh, Parsiad Mosca, Michele Institute for Quantum Computing University of Waterloo Canada David R. Cheriton School of Computer Science University of Waterloo Canada Department of Combinatorics & Optimization University of Waterloo Canada Perimeter Institute for Theoretical Physics Waterloo Canada Canadian Institute for Advanced Research Toronto Canada

We study the problem of CNOT-optimal quantum circuit synthesis over gate sets consisting of CNOT and Z-basis rotations of arbitrary angles. We show that the circuit-polynomial correspondence relates such circuits to Fourier expansions of pseudo-Boolean functions, and that for certain classes of functions this expansion uniquely determines the minimum CNOT cost of an implementation. As a corollary we prove that CNOT minimization over CNOT and phase gates is at least as hard as synthesizing a CNOT-optimal circuit computing a set of parities of its inputs. We then show that this problem is NP-complete for two restricted cases where all CNOT gates are required to have the same target, and where the circuit inputs are encoded in a larger state space. The latter case has applications to CNOT optimization over more general Clifford+T circuits. We further present an efficient heuristic algorithm for synthesizing circuits over CNOT and Z-basis rotations with small CNOT cost. Our experiments show a 23% reduction of CNOT gates on average across a suite of Clifford+T benchmark circuits, with a maximum reduction of 43%. Copyright © 2017, The Authors. All rights reserved.

关键词： Timing circuits

来源：评论

学校读者我要写书评

暂无评论

Space-efficient Quantization Method for Reversible Markov Chains

arXiv

引用

arXiv 2022年

作者： Chiang, Chen-Fu Chowdhury, Anirban Wocjan, Pawel Department of Computer and Information Science State University of New York Polytechnic Institute United States Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada Ibm Quantum Ibm T.J. Watson Research Center Yorktown HeightsNY10598 United States

In a seminal paper, Szegedy showed how to construct a quantum walk W(P) for any reversible Markov chain P such that its eigenvector with eigenphase 0 is a quantum sample of the limiting distribution of the random walk and its eigenphase gap is quadratically larger than the spectral gap of P. The standard construction of Szegedy's quantum walk requires an ancilla register of Hilbert-space dimension equal to the size of the state space of the Markov chain. We show that it is possible to avoid this doubling of state space for certain Markov chains that employ a symmetric proposal probability and a subsequent accept/reject probability to sample from the Gibbs distribution. For such Markov chains, we give a quantization method which requires an ancilla register of dimension equal to only the number of different energy values, which is often significantly smaller than the size of the state space. To accomplish this, we develop a technique for block encoding Hadamard products of matrices which may be of wider interest. Copyright © 2022, The Authors. All rights reserved.

关键词： quantum theory

来源：评论

学校读者我要写书评

暂无评论

Improved classical and quantum algorithms for subset-sum

arXiv

引用

arXiv 2020年

作者： Bonnetain, Xavier Bricout, Rémi Schrottenloher, André Shen, Yixin Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo WaterlooON Canada Sorbonne Université Collège Doctoral ParisF-75005 France Inria France Université de Paris IRIF CNRS ParisF-75013 France

We present new classical and quantum algorithms for solving random subset-sum instances. First, we improve over the Becker-Coron-Joux algorithm (EUROCRYPT 2011) from Oe (20.291n) downto Oe (20.283n), using more general representations with values in {−1, 0, 1, 2}. Next, we improve the state of the art of quantum algorithms for this problem in several directions. By combining the Howgrave-Graham-Joux algorithm (EUROCRYPT 2010) and quantum search, we devise an algorithm with asymptotic cost Oe (20.236n), lower than the cost of the quantum walk based on the same classical algorithm proposed by Bernstein, Jeffery, Lange and Meurer (PQCRYPTO 2013). This algorithm has the advantage of using classical memory with quantum random access, while the previously known algorithms used the quantum walk framework, and required quantum memory with quantum random access. We also propose new quantum walks for subset-sum, performing better than the previous best time complexity of Oe (20.226n) given by Helm and May (TQC 2018). We combine our new techniques to reach a time Oe (20.216n). This time is dependent on a heuristic on quantum walk updates, formalized by Helm and May, that is also required by the previous algorithms. We show how to partially overcome this heuristic, and we obtain an algorithm with quantum time Oe (20.218n) requiring only the standard classical subset-sum heuristics. Copyright © 2020, The Authors. All rights reserved.

关键词： quantum theory

来源：评论

学校读者我要写书评

暂无评论

Tensor product representation of a topological ordered phase: Necessary symmetry conditions

引用

Physical Review B 2010年第16期82卷 165119-165119页

作者： Xie Chen Bei Zeng Zheng-Cheng Gu Isaac L. Chuang Xiao-Gang Wen Department of Physics Massachusetts Institute of Technology Cambridge Massachusetts 02139 USA Institute for Quantum Computing University of Waterloo Waterloo Ontario Canada Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario Canada Department of Mathematics and Statistics University of Guelph Guelph Ontario Canada Kavli Institute for Theoretical Physics University of California Santa Barbara California 93106 USA

The tensor product representation of quantum states leads to a promising variational approach to study quantum phase and quantum phase transitions, especially topological ordered phases which are impossible to handle with conventional methods due to their long-range entanglement. However, an important issue arises when we use tensor product states (TPSs) as variational states to find the ground state of a Hamiltonian: can arbitrary variations in the tensors that represent ground state of a Hamiltonian be induced by local perturbations to the Hamiltonian? Starting from a tensor product state which is the exact ground state of a Hamiltonian with Z2 topological order, we show that, surprisingly, not all variations in the tensors correspond to the variation in the ground state caused by local perturbations of the Hamiltonian. Even in the absence of any symmetry requirement of the perturbed Hamiltonian, one necessary condition for the variations in the tensors to be physical is that they respect certain Z2 symmetry. We support this claim by calculating explicitly the change in topological entanglement entropy with different variations in the tensors. This finding will provide important guidance to numerical variational study of topological phase and phase transitions. It is also a crucial step in using TPS to study universal properties of a quantum phase and its topological order.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Flag fault-tolerant error correction, measurement, and quantum computation for cyclic Calderbank-Shor-Steane codes

引用

Physical Review A 2020年第1期101卷 012342-012342页

作者： Theerapat Tansuwannont Christopher Chamberland Debbie Leung Institute for Quantum Computing and Department of Physics and Astronomy University of Waterloo Waterloo Ontario Canada N2L 3G1 IBM T. J. Watson Research Center Yorktown Heights New York 10598 USA Institute for Quantum Computing and Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario Canada N2L 3G1 Perimeter Institute for Theoretical Physics Waterloo Ontario Canada N2L 2Y5

Flag qubits have recently been proposed in syndrome extraction circuits to detect high-weight errors arising from fewer faults. The use of flag qubits allows the construction of fault-tolerant protocols with the fewest number of ancillas known to date. In this work, we prove some critical properties of Calderbank-Shor-Steane (CSS) codes constructed from classical cyclic codes that enable the construction of a flag fault-tolerant error correction scheme. We then develop fault-tolerant protocols as well as a family of circuits for flag fault-tolerant error correction and operator measurement, requiring only four ancilla qubits and applicable to cyclic CSS codes of distance 3. The measurement protocol can be further used for logical Clifford gate implementation via quantum gate teleportation. We also provide examples of cyclic CSS codes with large encoding rates.

关键词： quantum error correction

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：