Quantum Meets the Minimum Circuit Size Problem
- URL: http://arxiv.org/abs/2108.03171v3
- Date: Tue, 14 Sep 2021 16:10:05 GMT
- Title: Quantum Meets the Minimum Circuit Size Problem
- Authors: Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang
- Abstract summary: We study the Minimum Circuit Size Problem (MCSP) in the quantum setting.
MCSP is a problem to compute the circuit complexity of Boolean functions.
We show that these problems are not trivially in NP but in QCMA (or have QCMA protocols)
- Score: 3.199102917243584
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we initiate the study of the Minimum Circuit Size Problem
(MCSP) in the quantum setting. MCSP is a problem to compute the circuit
complexity of Boolean functions. It is a fascinating problem in complexity
theory -- its hardness is mysterious, and a better understanding of its
hardness can have surprising implications to many fields in computer science.
We first define and investigate the basic complexity-theoretic properties of
minimum quantum circuit size problems for three natural objects: Boolean
functions, unitaries, and quantum states. We show that these problems are not
trivially in NP but in QCMA (or have QCMA protocols). Next, we explore the
relations between the three quantum MCSPs and their variants. We discover that
some reductions that are not known for classical MCSP exist for quantum MCSPs
for unitaries and states, e.g., search-to-decision reduction and
self-reduction. Finally, we systematically generalize results known for
classical MCSP to the quantum setting (including quantum cryptography, quantum
learning theory, quantum circuit lower bounds, and quantum fine-grained
complexity) and also find new connections to tomography and quantum gravity.
Due to the fundamental differences between classical and quantum circuits, most
of our results require extra care and reveal properties and phenomena unique to
the quantum setting. Our findings could be of interest for future studies, and
we post several open problems for further exploration along this direction.
Related papers
- Complexity Theory for Quantum Promise Problems [5.049812996253858]
We study the relationship between quantum cryptography and complexity theory, especially within Impagliazzo's five worlds framework.
We focus on complexity classes p/mBQP, p/mQ(C)MA, $mathrmp/mQSZK_hv$, p/mQIP, and p/mPSPACE, where "p/mC" denotes classes with pure (p) or mixed (m) states.
We apply this framework to cryptography, showing that breaking one-way state generators, pseudorandom states, and EFI is bounded by mQCMA or
arXiv Detail & Related papers (2024-11-06T07:29:52Z) - Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties?
We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.
We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
arXiv Detail & Related papers (2024-08-22T08:21:28Z) - Discretized Quantum Exhaustive Search for Variational Quantum Algorithms [0.0]
Currently available quantum devices have only a limited amount of qubits and a high level of noise, limiting the size of problems that can be solved accurately with those devices.
We propose a novel method that can improve variational quantum algorithms -- discretized quantum exhaustive search''
arXiv Detail & Related papers (2024-07-24T22:06:05Z) - Quantum Information Processing with Molecular Nanomagnets: an introduction [49.89725935672549]
We provide an introduction to Quantum Information Processing, focusing on a promising setup for its implementation.
We introduce the basic tools to understand and design quantum algorithms, always referring to their actual realization on a molecular spin architecture.
We present some examples of quantum algorithms proposed and implemented on a molecular spin qudit hardware.
arXiv Detail & Related papers (2024-05-31T16:43:20Z) - 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) - Learning marginals suffices! [14.322753787990036]
We investigate the relationship between the sample complexity of learning a quantum state and the circuit complexity of the state.
We show that learning its marginals for the quantum state with low circuit complexity suffices for state tomography.
arXiv Detail & Related papers (2023-03-15T21:09:29Z) - 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) - Quantum Computing Quantum Monte Carlo [8.69884453265578]
We propose a hybrid quantum-classical algorithm that integrates quantum computing and quantum Monte Carlo.
Our work paves the way to solving practical problems with intermediatescale and early-fault tolerant quantum computers.
arXiv Detail & Related papers (2022-06-21T14:26:24Z) - 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) - Towards understanding the power of quantum kernels in the NISQ era [79.8341515283403]
We show that the advantage of quantum kernels is vanished for large size datasets, few number of measurements, and large system noise.
Our work provides theoretical guidance of exploring advanced quantum kernels to attain quantum advantages on NISQ devices.
arXiv Detail & Related papers (2021-03-31T02:41:36Z) - 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)
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.