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

2024 International Conference on quantum Computing and Engineering

作者： Ye, Orson Strelchuk, Sergii Univ Cambridge Dept Appl Math & Theoret Phys Wilberforce Rd Cambridge CB3 0WA England

ISBN: (纸本)9798331541378

Data encoding is a key step in almost all applications of quantum computation, but one that is not very well understood in general. Extensively researched in quantum machine learning, it is pivotal to exploiting the speedups offered by quantum algorithms. Failure to efficiently represent data risks weakening or nullifying prospective quantum advantages. While naive methods, such as basis encoding, will almost always work, they are extremely inefficient in terms of qubit use, rendering them infeasible for near-term applications. We focus on data encoding for genomics, a deeply data-driven field with computationally intensive algorithms throughout, from the initial DNA sequencing to pangenome assembly and more. We first examine the compressibility of genomic data from an information-theoretic perspective and how compression affects the quantum state preparation complexity. Here, there are two opposing forces at work: compression reduces data size but at the cost of the beneficial structure within the data. We review some standard approaches to data encoding in the context of genomics data from considering both the preparation complexity in terms of gate counts, qubit use, and depth, as well as the usefulness of the resulting states. We also present some new data encoding methods designed specifically for genomics that have a low-depth preparation circuits while still maintaining the essential features the algorithms require.

关键词： quantum Applications quantum circuit complexity Data Encoding Genomics State Preparation quantum Information

来源：评论

学校读者我要写书评

暂无评论

quantum circuit complexity as a Physical Observable

引用

Journal of Applied Mathematics and Physics 2025年第1期13卷 87-137页

作者： Logan Nye School of Computer Science Carnegie Mellon University Pittsburgh USA

This work proposes quantum circuit complexity—the minimal number of elementary operations needed to implement a quantum transformation—be established as a legitimate physical observable. We prove that circuit complexity satisfies all requirements for physical observables, including self-adjointness, gauge invariance, and a consistent measurement theory with well-defined uncertainty relations. We develop complete protocols for measuring complexity in quantum systems and demonstrate its connections to gauge theory and quantum gravity. Our results suggest that computational requirements may constitute physical laws as fundamental as energy conservation. This framework grants insights into the relationship between quantum information, gravity, and the emergence of spacetime geometry while offering practical methods for experimental verification. Our results indicate that the physical universe may be governed by both energetic and computational constraints, with profound implications for our understanding of fundamental physics.

关键词： quantum circuit complexity Physical Observables Operator Theory quantum Gravity quantum Measurement

来源：评论

学校读者我要写书评

暂无评论

A universal bound on entanglement velocity

引用

quantum Frontiers 2025年第1期4卷 1-16页

作者： Nye, Logan School of Computer Science Carnegie Mellon University 5000 Forbes Ave Pittsburgh 15213 PA United States

We establish a universal bound on entanglement dynamics, proving that for any quantum system with energy E, the rate of entanglement entropy change is limited by |dSdt|≤2Eπħ. This bound, which can be saturated by specific protocols, emerges from a framework treating entanglement rate as a physical observable and connects directly to quantum circuit complexity. When extended to quantum field theory, we demonstrate that the maximum entanglement propagation velocity equals the speed of light, revealing a fundamental connection between quantum information constraints and relativistic causality. We propose experimental tests on quantum computing platforms and explore implications for quantum computing efficiency and spacetime structure. Our results suggest that information-theoretic principles may be more fundamental than spacetime concepts, unifying quantum information, computational complexity, and relativistic physics. © The Author(s) 2025.

关键词： Entanglement dynamics Entanglement entropy quantum circuit complexity quantum field theory quantum information geometry Relativistic causality

来源：评论

学校读者我要写书评

暂无评论

On the Pauli Spectrum of QAC0 2024

On the Pauli Spectrum of QAC0

引用

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Nadimpalli, Shivam Parham, Natalie Vasconcelos, Francisca Yuen, Henry Columbia Univ New York NY 10027 USA Univ Calif Berkeley Berkeley CA 94720 USA

ISBN: (纸本)9798400703836

The circuit class QAC(0) was introduced by Moore (1999) as a model for constant depth quantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower bounds against such circuits is a longstanding challenge in quantum circuit complexity;in particular, showing that polynomial-size QAC(0) cannot compute the parity function has remained an open question for over 20 years. In this work, we identify a notion of the Pauli spectrum of QAC(0) circuits, which can be viewed as the quantum analogue of the Fourier spectrum of classical AC(0) circuits. We conjecture that the Pauli spectrum of QAC(0) circuits satisfies low-degree concentration, in analogy to the famous Linial, Mansour, Nisan (LMN) theorem on the low-degree Fourier concentration of AC(0) circuits. If true, this conjecture immediately implies that polynomial-size QAC(0) circuits cannot compute parity. We prove this conjecture for the class of depth-d, polynomial-size QAC(0) circuits with at most n(O(1/d)) auxiliary qubits. We obtain new circuit lower bounds and learning results as applications: this class of circuits cannot correctly compute the n-bit parity function on more than (1/2 + 2-(Omega(n1/d)))-fraction of inputs, and the n-bit majority function on more than (1/2 + O(n(-1/4)))-fraction of inputs. Additionally we show that this class of QAC(0) circuits with limited auxiliary qubits can be learned with quasipolynomial sample complexity, giving the first learning result for QAC(0) circuits. More broadly, our results add evidence that Pauli-analytic techniques can be a powerful tool in studying quantum circuits.

关键词： QAC0 analysis of Boolean functions quantum circuit complexity

来源：评论

学校读者我要写书评

暂无评论

Power of uninitialized qubits in shallow quantum circuits

引用

THEORETICAL COMPUTER SCIENCE 2021年 851卷 129-153页

作者： Takahashi, Yasuhiro Tani, Seiichiro NTT Corp NTT Commun Sci Labs 3-1 Morinosato Wakamiya Atsugi Kanagawa 2430198 Japan

We study uninitialized qubits, whose initial state is arbitrary and unknown, in relation to the computational power of shallow quantum circuits. To do this, we consider uniform families of shallow quantum circuits with n input qubits, O (log n) initialized ancillary qubits, and n(O(1)) uninitialized ancillary qubits, where the input qubits only act as control qubits. We show that such a circuit with depth O((log n)(2)) can compute any symmetric Boolean function on n bits that is computable by a uniform family of polynomial-size classical circuits. Since it is unlikely that this can be done with only O(log n) initialized ancillary qubits, our result provides evidence that the presence of uninitialized ancillary qubits increases the computational power of shallow quantum circuits with only O (log n) initialized ancillary qubits. On the other hand, to understand the limitations of uninitialized qubits, we focus on sub-logarithmic-depth quantum circuits and show the impossibility of computing the parity function on n bits. (C) 2020 Elsevier B.V. All rights reserved.

关键词： quantum circuit complexity Shallow quantum circuit Uninitialized qubit

来源：评论

学校读者我要写书评

暂无评论

Exploring the optimality of approximate state preparation quantum circuits with a genetic algorithm

引用

PHYSICS LETTERS A 2023年 475卷

作者： Rindell, Tom Yenilen, Berat Halonen, Niklas Ponni, Arttu Tittonen, Ilkka Raasakka, Matti Aalto Univ Dept Elect & Nanoengn Micro & Quantum Syst Grp Espoo Finland Univ Helsinki Dept Phys Helsinki Finland Rhein Westfal TH Aachen Dept Phys Aachen Germany

We study the approximate state preparation problem on noisy intermediate-scale quantum (NISQ) computers by applying a genetic algorithm to generate quantum circuits for state preparation. The algorithm can account for the specific characteristics of the physical machine in the evaluation of circuits, such as the native gate set and qubit connectivity. We use our genetic algorithm to optimize the circuits provided by the low-rank state preparation algorithm introduced by Araujo et al., and find substantial improvements to the fidelity in preparing Haar random states with a limited number of CNOT gates. Moreover, we observe that already for a 5-qubit quantum processor with limited qubit connectivity and significant noise levels (IBM Falcon 5T), the maximal fidelity for Haar random states is achieved by a short approximate state preparation circuit instead of the exact preparation circuit. We also present a theoretical analysis of approximate state preparation circuit complexity to motivate our findings. Our genetic algorithm for quantum circuit discovery is freely available at https:// github .com /beratyenilen /qc -ga. (c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： quantum state preparation Genetic algorithm quantum circuit complexity Noisy intermediate-scale quantum NISQ

来源：评论

学校读者我要写书评

暂无评论

Aspects of the first law of complexity

引用

JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL 2020年第29期53卷 1-89页

作者： Bernamonti, Alice Galli, Federico Hernandez, Juan Myers, Robert C. Ruan, Shan-Ming Simon, Joan Univ Firenze Imento Fis & Astron Via G Sansone 1 I-50019 Sesto Fiorentino Italy INFN Sez Firenze Via G Sansone 1 I-50019 Sesto Fiorentino Italy Perimeter Inst Theoret Phys Waterloo ON N2L 2Y5 Canada Univ Waterloo Dept Phys & Astron Waterloo ON N2L 3G1 Canada Univ Edinburgh Sch Math Edinburgh EH9 3FD Midlothian Scotland Univ Edinburgh Maxwell Inst Math Sci Edinburgh EH9 3FD Midlothian Scotland

We investigate the first law of complexity proposed in Bernamontiet al(2019Phys. Rev. Lett.123081601), i.e., the variation of complexity when the target state is perturbed, in more detail. Based on Nielsen's geometric approach to quantum circuit complexity, we find the variation only depends on the end of the optimal circuit. We apply the first law to gain new insights into the quantum circuits and complexity models underlying holographic complexity. In particular, we examine the variation of the holographic complexity for both the complexity = action and complexity = volume conjectures in perturbing the AdS vacuum with coherent state excitations of a free scalar field. We also examine the variations of circuit complexity produced by the same excitations for the free scalar field theory in a fixed AdS background. In this case, our work extends the existing treatment of Gaussian coherent states to properly include the time dependence of the complexity variation. We comment on the similarities and differences of the holographic and QFT results.

关键词： AdS-CFT correspondence quantum circuit complexity holographic complexity

来源：评论

学校读者我要写书评

暂无评论

Learning bounds for quantum circuits in the agnostic setting

引用

quantum INFORMATION PROCESSING 2021年第9期20卷 286-286页

作者： Popescu, Claudiu Marius Tech Univ Cluj Napoca Signal Proc Grp Baritiu St 26-28 Cluj Napoca Romania

In this paper, we investigate the learnability of some hypothesis sets for regression and binary classification defined by quantum circuits. The analysis is based on concepts and results from quantum computing (Solovay-Kitaev theorem) and statistical learning theory (covering numbers and Rademacher complexity). The obtained learning bounds depend polynomially on the parameters defining the circuits set, namely the number of qubits and the number of 1 and 2 qubits gates used for their implementation. Our setting is quite general: no realisability assumptions are made, and any 1 and 2 qubits gates are allowed. Finally, we compare the current bounds with others found in the literature and discuss their implications for classification and regression on quantum data.

关键词： quantum circuit complexity Learning bounds Covering numbers

来源：评论

学校读者我要写书评

暂无评论

Power of Uninitialized Qubits in Shallow quantum circuits 35

Power of Uninitialized Qubits in Shallow Quantum Circuits

引用

35th Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Takahashi, Yasuhiro Tani, Seiichiro NTT Corp NTT Commun Sci Labs Tokyo Japan

ISBN: (纸本)9783959770620

We study the computational power of shallow quantum circuits with O(log n) initialized and n(O)(1) uninitialized ancillary qubits, where n is the input length and the initial state of the uninitialized ancillary qubits is arbitrary. First, we show that such a circuit can compute any symmetric function on n bits that is classically computable in polynomial time. Then, we regard such a circuit as an oracle and show that a polynomial-time classical algorithm with the oracle can estimate the elements of any unitary matrix corresponding to a constant-depth quantum circuit on n qubits. Since it seems unlikely that these tasks can be done with only O(log n) initialized ancillary qubits, our results give evidences that adding uninitialized ancillary qubits increases the computational power of shallow quantum circuits with only O(log n) initialized ancillary qubits. Lastly, to understand the limitations of uninitialized ancillary qubits, we focus on near-logarithmic-depth quantum circuits with them and show the impossibility of computing the parity function on n bits. 2012 ACM Subject Classification Theory of computation -> quantum computation theory

关键词： quantum circuit complexity Shallow quantum circuit Uninitialized Qubit

来源：评论

学校读者我要写书评

暂无评论

Collapse of the Hierarchy of Constant-Depth Exact quantum circuits

引用

COMPUTATIONAL complexity 2016年第4期25卷 849-881页

作者： Takahashi, Yasuhiro Tani, Seiichiro NTT Corp NTT Commun Sci Labs Atsugi Kanagawa 2430198 Japan

We study the quantum complexity class of quantum operations implementable exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates. Our main result is that the quantum OR operation is in , which is an affirmative answer to the question posed by Hoyer and palek. In sharp contrast to the strict hierarchy of the classical complexity classes: , our result with Hoyer and palek's one implies the collapse of the hierarchy of the corresponding quantum ones: . Then, we show that there exists a constant-depth subquadratic-size quantum circuit for the quantum threshold operation. This allows us to obtain a better bound on the size difference between the and circuits for implementing the same operation. Lastly, we show that, if the quantum Fourier transform modulo a prime is in , there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a oracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a circuit with gates for the quantum Fourier transform.

关键词： quantum circuit complexity OR function threshold function discrete logarithm algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：