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

Deterministic Algorithms for the Hidden Subgroup Problem

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Ye, Zekun Li, Lvzhou Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China Key Laboratory of Machine Intelligence and Advanced Computing Ministry of Education China

We consider deterministic algorithms for the well-known hidden subgroup problem (HSP): for a finite group G and a finite set X, given a function f: G → X and the promise that for any g1, g2 ∈ G, f(g1) = f(g2) iff g1H = g2H for a subgroup H ≤ G, the goal of the decision version is to determine whether H is trivial or not, and the goal of the identification version is to identify H. An algorithm for the problem should query f(g) for g ∈ G at least as possible. Nayak [25] asked whether there exist deterministic algorithms with O(√|G|/|H|) query complexity for HSP. We answer this problem by proving the following results, which also extend the main results of Ref. [30], since here the algorithms do not rely on any prior knowledge of H. (i) When G is a general finite Abelian group, there exist an algorithm with O(√|G|/|H| |) queries to decide the triviality of H and an algorithm to identify H with O(√|G|/|H| log |H| + log |H|) queries. (ii) In general there is no deterministic algorithm for the identification version of HSP with query complexity of O(√|G|/|H|), since there exists an instance of HSP that needs ω(√|G|/|H|) queries to identify H.1 On the other hand, there exist instances of HSP with query complexity far smaller than O(√|G|/|H|), whose query complexity is O(log |G|/|H|) and even O(1). © 2021, CC BY.

关键词： Group theory

quantum Phase Estimation by Compressed Sensing

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Yi, Changhao Zhou, Cunlu Takahashi, Jun State Key Laboratory of Surface Physics Department of Physics Center for Field Theory and Particle Physics Fudan University Shanghai China Institute for Nanoelectronic Devices and Quantum Computing Fudan University Shanghai China Shanghai Research Center for Quantum Sciences Shanghai China Department of Computer Science & Institut Quantique Université de Sherbrooke QC Canada Center for Quantum Information and Control Department of Physics and Astronomy University of New Mexico NM United States Institute of Solid State Physics University of Tokyo Chiba Japan

As a signal recovery algorithm, compressed sensing is particularly effective when the data has low complexity and samples are scarce, which aligns natually with the task of quantum phase estimation (QPE) on early fault-tolerant quantum computers. In this work, we present a new Heisenberg-limited, robust QPE algorithm based on compressed sensing, which requires only sparse and discrete sampling of times. Specifically, given multiple copies of a suitable initial state and queries to a specific unitary matrix, our algorithm can recover the phase with a total runtime of O(ϵ−1poly log(ϵ−1)), where ϵ is the desired accuracy. Additionally, the maximum runtime satisfies Tmaxϵ π, making it comparable to state-of-the-art algorithms. Furthermore, our result resolves the basis mismatch problem in certain cases by introducing an additional parameter to the traditional compressed sensing framework. © 2023, CC BY.

关键词： Fault tolerant computer systems

Experimental Simulation of Loop quantum Gravity on a Photonic Chip

学校读者我要写书评

暂无评论

Experimental Simulation of Loop Quantum Gravity on a Photoni...

quantum 2.0, quantum 2024 in quantum 2.0 Conference and Exhibition

作者： Anguita, Malaquias Correa van der Meer, Reinier Huang, Zichang Qu, Dongxue Hooijschuur, Peter Liu, Hongguang Han, Muxin Renema, Jelmer J. Cohen, Lior MESA+ Institute for Nanotechnology University of Twente P.O.box 217 Enschede7500 AE Netherlands State Key Laboratory of Surface Physics Department of Physics Center for Field Theory and Particle Physics Institute for Nanoelectronic devices and Quantum computing Fudan University Shanghai200433 China Department of Physics Florida Atlantic University 777 Glades Road Boca RatonFL33431 United States Department Physik Institut für Quantengravitation Theoretische Physik III Friedrich-Alexander Universität Erlangen-Nürnberg Staudtstr. 7/B2 Erlangen91058 Germany Department of Electrical Computer and Energy Engineering University of Colorado Boulder BoulderCO80309 United States

We experimentally simulate a basic transition amplitude of Loop quantum Gravity on an integrated photonic chip, and show that this amplitude falls within 4% error from the theoretical prediction. © 2024 The Autho... 详细信息

ISBN: (纸本)9781557525185

关键词： Photonic integrated circuits

quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Mukhopadhyay, Priyanka Stetina, Torin F. Wiebe, Nathan Department of Physical & Environmental Sciences University of Toronto ON Canada Simons Institute for the Theory of Computing BerkeleyCA United States Berkeley Quantum Information and Computation Center University of California Berkeley United States Department of Computer Science University of Toronto ON Canada Pacific Northwest National Laboratory RichlandWA United States Canadian Institute for Advanced Research TorontoON Canada

We provide an explicit recursive divide and conquer approach for simulating quantum dynamics and derive a discrete first quantized non-relativistic QED Hamiltonian based on the many-particle Pauli Fierz Hamiltonian. We apply this recursive divide and conquer algorithm to this Hamiltonian and compare it to a concrete simulation algorithm that uses qubitization. Our divide and conquer algorithm, using lowest order Trotterization, scales for fixed grid spacing as Õ(ΛN2η2t2/ϵ) for grid size N, η particles, simulation time t, field cutoff Λ and error ϵ. Our qubitization algorithm scales as Õ(N(η + N)(η + Λ2)tlog(1/ϵ)). This shows that even a naïve partitioning and low-order splitting formula can yield, through our divide and conquer formalism, superior scaling to qubitization for large Λ. We compare the relative costs of these two algorithms on systems that are relevant for applications such as the spontaneous emission of photons, and the photoionization of electrons. We observe that for different parameter regimes, one method can be favored over the other. Finally, we give new algorithmic and circuit level techniques for gate optimization including a new way of implementing a group of multi-controlled-X gates that can be used for better analysis of circuit cost. © 2023, CC BY.

关键词： Hamiltonians

Distributed exact quantum algorithms for Bernstein-Vazirani and search problems

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Zhou, Xu Qiu, Daowen Luo, Le Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China The Guangdong Key Laboratory of Information Security Technology Sun Yat-sen University Guangzhou510006 China School of Physics and Astronomy Sun Yat-sen University Zhuhai519082 China QUDOOR Technologies Inc. Zhuhai519099 China

Distributed quantum computation has gained extensive attention since small-qubit quantum computers seem to be built more practically in the noisy intermediate-scale quantum (NISQ) era. In this paper, we give a distributed Bernstein-Vazirani algorithm (DBVA) with t computing nodes, and a distributed exact Grover’s algorithm (DEGA) that solve the search problem with only one target item in the unordered databases. Though the designing techniques are simple in the light of BV algorithm, Grover’s algorithm, the improved Grover’s algorithm by Long, and the distributed Grover’s algorithm by Qiu et al, in comparison to BV algorithm, the circuit depth of DBVA is not greater than 2max(n0,n1,··· ,nt−1) + 3 instead of 2n + 3, and the circuit depth of DEGA is 8(n mod 2) + 9, which is less than the circuit depth of Grover’s algorithm, (formula presented). In particular, we provide situations of our DBVA and DEGA on Mindquantum (a quantum software) to validate the correctness and practicability of our methods. By simulating the algorithms running in the depolarized channel, it further illustrates that distributed quantum algorithm has superiority of resisting noise. Copyright © 2023, The Authors. All rights reserved.

关键词： quantum theory

Matrix manipulations via unitary transformations and ancilla-state measurements

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Zenchuk, Alexander I. Qi, Wentao Kumar, Asutosh Wu, Junde Federal Research Center of Problems of Chemical Physics and Medicinal Chemistry RAS Moscow reg. Chernogolovka142432 Russia Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China Department of Physics Gaya College Magadh University Rampur Gaya823001 India School of Mathematical Sciences Zhejiang University Hangzhou310027 China

We propose protocols for calculating inner product, matrix addition and matrix multiplication based on multiqubit Toffoli-type and the simplest one-qubit operations and employ ancilla-measurements to remove all garbage of calculations. The depth (runtime) of addition protocol is O(1) and that of other protocols logarithmically increases with the dimensionality of the considered matrices. © 2023, CC BY-NC-ND.

关键词： Matrix algebra

Purely quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Zenchuk, Alexander I. Bochkin, Georgii A. Qi, Wentao Kumar, Asutosh Wu, Junde Federal Research Center of Problems of Chemical Physics and Medicinal Chemistry RAS Moscow reg. Chernogolovka142432 Russia Institute of Quantum Computing and Computer Theory School of Computer Science and Engineering Sun Yat-sen University Guangzhou510006 China Department of Physics Gaya College Gaya Rampur823001 India P.G. Department of Physics Magadh University Bodh Gaya824234 India School of Mathematical Sciences Zhejiang University Hangzhou310027 China

We propose quantum algorithms that are fundamentally quantum in nature for the computation of the determinant and inverse of an (N−1)×(N−1) matrix, with a computational depth of O(N2 log N). This approach is a straightforward modification of the existing algorithm for determining the determinant of an N × N matrix, which operates with a depth of O(N log2 N). The core concept involves encoding each row of the matrix into a pure state of a quantum system. In addition, we use the representation of the elements of the inverse matrix in terms of algebraic complements. This algorithm, in conjunction with the matrix multiplication algorithm discussed in the appendix, facilitates solving systems of linear algebraic equations with a depth of O(N log2 N). The measurement of the ancilla state yielding an output of 1 occurs with a probability of approximately 2−O(N log N), and eliminates the extraneous data generated during the computation. We provide suitable circuit designs for all three algorithms, each estimated to require O(N log N) in terms of space, specifically the number of qubits utilized in the circuit. © 2024, CC BY-NC-ND.

关键词： Inverse problems

Auxiliary-free replica shadow estimation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Liu, Qing Li, Zihao Yuan, Xiao Zhu, Huangjun Zhou, You Key Laboratory for Information Science of Electromagnetic Waves Ministry of Education Fudan University Shanghai200433 China State Key Laboratory of Surface Physics Department of Physics Fudan University Shanghai200433 China Institute for Nanoelectronic Devices and Quantum Computing Fudan University Shanghai200433 China Center for Field Theory and Particle Physics Fudan University Shanghai200433 China Center on Frontiers of Computing Studies Peking University Beijing100871 China School of Computer Science Peking University Beijing100871 China

Efficiently measuring nonlinear properties, like the entanglement spectrum, is a significant yet challenging task from quantum information processing to many-body physics. Current methodologies often suffer from an exponential scaling of the sampling cost or require auxiliary qubits and deep quantum circuits. To address these limitations, we propose an efficient auxiliary-free replica shadow (AFRS) framework, which leverages the power of the joint entangling operation on a few input replicas while integrating the mindset of shadow estimation. We rigorously prove that AFRS can offer exponential improvements in estimation accuracy compared with the conventional shadow method, and facilitate the simultaneous estimation of various nonlinear properties, unlike the destructive swap test. Additionally, we introduce an advanced local-AFRS variant tailored to estimating local observables with even constant-depth local quantum circuits, which significantly simplifies the experimental realization compared with the general swap test. Our work paves the way for the application of AFRS on near-term quantum hardware, opening new avenues for efficient and practical quantum measurements. © 2024, CC BY.

关键词： quantum entanglement

quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian

学校读者我要写书评

暂无评论

PRX quantum 2024年第1期5卷 010345-010345页

作者： Priyanka Mukhopadhyay Torin F. Stetina Nathan Wiebe Department of Physical & Environmental Sciences University of Toronto Ontario M1C 1A4 Canada Simons Institute for the Theory of Computing Berkeley California 94720 USA Berkeley Quantum Information and Computation Center University of California Berkeley California 94720-1460 USA Department of Computer Science University of Toronto Ontario M5S 2E4 Canada Pacific Northwest National Laboratory Richland Washington 99354 USA Canadian Institute for Advanced Research Toronto Ontario M5G 1M1 Canada

We provide an explicit recursive divide-and-conquer approach for simulating quantum dynamics and derive a discrete first-quantized nonrelativistic QED Hamiltonian based on the many-particle Pauli-Fierz Hamiltonian. We apply this recursive divide-and-conquer algorithm to this Hamiltonian and compare it to a concrete simulation algorithm that uses qubitization. Our divide-and-conquer algorithm, using lowest-order Trotterization, scales for fixed grid spacing as O~(ΛN2η2t2/ϵ) for grid size N, η particles, simulation time t, field cutoff Λ, and error ϵ. Our qubitization algorithm scales as O~(N(η+N)(η+Λ2)tlog (1/ϵ)). This shows that even a naive partitioning and low-order splitting formula can yield, through our divide-and-conquer formalism, superior scaling to qubitization for large Λ. We compare the relative costs of these two algorithms on systems that are relevant for applications such as the spontaneous emission of photons and the photoionization of electrons. We observe that for different parameter regimes, one method can be favored over the other. Finally, we give new algorithmic and circuit-level techniques for gate optimization, including a new way of implementing a group of multicontrolled-X gates that can be used for better analysis of circuit cost.

关键词： quantum simulation