Complexity of quantum circuits via sensitivity, magic, and coherence
- URL: http://arxiv.org/abs/2204.12051v1
- Date: Tue, 26 Apr 2022 03:15:09 GMT
- Title: Complexity of quantum circuits via sensitivity, magic, and coherence
- Authors: Kaifeng Bu, Roy J. Garcia, Arthur Jaffe, Dax Enshan Koh, Lu Li
- Abstract summary: We study the complexity of quantum circuits using the notions of sensitivity, average sensitivity (also called influence), magic, and coherence.
Our results are pivotal for understanding the role of sensitivity, magic, and coherence in quantum computation.
- Score: 5.630280136865099
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum circuit complexity-a measure of the minimum number of gates needed to
implement a given unitary transformation-is a fundamental concept in quantum
computation, with widespread applications ranging from determining the running
time of quantum algorithms to understanding the physics of black holes. In this
work, we study the complexity of quantum circuits using the notions of
sensitivity, average sensitivity (also called influence), magic, and coherence.
We characterize the set of unitaries with vanishing sensitivity and show that
it coincides with the family of matchgates. Since matchgates are tractable
quantum circuits, we have proved that sensitivity is necessary for a quantum
speedup. As magic is another measure to quantify quantum advantage, it is
interesting to understand the relation between magic and sensitivity. We do
this by introducing a quantum version of the Fourier entropy-influence
relation. Our results are pivotal for understanding the role of sensitivity,
magic, and coherence in quantum computation.
Related papers
- Are Molecules Magical? Non-Stabilizerness in Molecular Bonding [50.24983453990065]
Isolated atoms as well as molecules at equilibrium are presumed to be simple from the point of view of quantum computational complexity.
We show that the process of chemical bond formation is accompanied by a marked increase in the quantum complexity of the electronic ground state.
arXiv Detail & Related papers (2025-04-09T08:14:27Z) - The curse of random quantum data [62.24825255497622]
We quantify the performances of quantum machine learning in the landscape of quantum data.
We find that the training efficiency and generalization capabilities in quantum machine learning will be exponentially suppressed with the increase in qubits.
Our findings apply to both the quantum kernel method and the large-width limit of quantum neural networks.
arXiv Detail & Related papers (2024-08-19T12:18:07Z) - Character Complexity: A Novel Measure for Quantum Circuit Analysis [0.0]
This paper introduces Character Complexity, a novel measure that bridges Group-theoretic concepts with practical quantum computing concerns.
I prove several key properties of character complexity and establish a surprising connection to the classical simulability of quantum circuits.
I present innovative visualization methods for character complexity, providing intuitive insights into the structure of quantum circuits.
arXiv Detail & Related papers (2024-08-19T01:58:54Z) - Unconditional quantum magic advantage in shallow circuit computation [2.517043342442487]
Quantum theory promises computational speed-ups over classical approaches.
The Gottesman-Knill Theorem implies that the full power of quantum computation resides in the specific resource of "magic" states.
In this work, we demonstrate the first unconditional magic advantage.
arXiv Detail & Related papers (2024-02-19T15:59:48Z) - Quantum Ruzsa Divergence to Quantify Magic [0.0]
We investigate the behavior of quantum entropy under quantum convolution and its application in magic.
We introduce a new quantum divergence based on quantum convolution, called the quantum Ruzsa divergence, to study the stabilizer structure of quantum states.
arXiv Detail & Related papers (2024-01-25T18:43:24Z) - Taming Quantum Time Complexity [45.867051459785976]
We show how to achieve both exactness and thriftiness in the setting of time complexity.
We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
The anticipated applications of quantum computers span across science and industry.
We present a survey of several potential application areas of quantum algorithms.
We outline the challenges and opportunities in each area in an "end-to-end" fashion.
arXiv Detail & Related papers (2023-10-04T17:53:55Z) - Monte Carlo Graph Search for Quantum Circuit Optimization [26.114550071165628]
This work proposes a quantum architecture search algorithm based on a Monte Carlo graph search and measures of importance sampling.
It is applicable to the optimization of gate order, both for discrete gates, as well as gates containing continuous variables.
arXiv Detail & Related papers (2023-07-14T14:01:25Z) - Wasserstein Complexity of Quantum Circuits [10.79258896719392]
Given a unitary transformation, what is the size of the smallest quantum circuit that implements it?
This quantity, known as the quantum circuit complexity, is a fundamental property of quantum evolutions.
We show that our new measure also provides a lower bound for the experimental cost of implementing quantum circuits.
arXiv Detail & Related papers (2022-08-12T14:44:13Z) - On exploring the potential of quantum auto-encoder for learning quantum systems [60.909817434753315]
We devise three effective QAE-based learning protocols to address three classically computational hard learning problems.
Our work sheds new light on developing advanced quantum learning algorithms to accomplish hard quantum physics and quantum information processing tasks.
arXiv Detail & Related papers (2021-06-29T14:01:40Z) - How smooth is quantum complexity? [0.0]
The "quantum complexity" of a unitary operator measures the difficulty of its construction from a set of elementary quantum gates.
In this paper, we present a unified perspective on various notions of quantum complexity, viewed as functions on the space of unitary operators.
arXiv Detail & Related papers (2021-06-15T17:58:08Z) - Numerical hardware-efficient variational quantum simulation of a soliton
solution [0.0]
We discuss the capabilities of quantum algorithms with special attention paid to a hardware-efficient variational eigensolver.
A delicate interplay between magnetic interactions allows one to stabilize a chiral state that destroys the homogeneity of magnetic ordering.
We argue that, while being capable of correctly reproducing a uniform magnetic configuration, the hardware-efficient ansatz meets difficulties in providing a detailed description to a noncollinear magnetic structure.
arXiv Detail & Related papers (2021-05-13T11:58:18Z) - Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems.
We propose an algorithm to implement imaginary time propagation on a quantum computer.
arXiv Detail & Related papers (2021-02-24T12:48:00Z) - Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
We experimentally investigate the dynamics of quantum scrambling on a 53-qubit quantum processor.
We show that while operator spreading is captured by an efficient classical model, operator entanglement requires exponentially scaled computational resources to simulate.
arXiv Detail & Related papers (2021-01-21T22:18:49Z) - Quantum walk processes in quantum devices [55.41644538483948]
We study how to represent quantum walk on a graph as a quantum circuit.
Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
arXiv Detail & Related papers (2020-12-28T18:04:16Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.