On the Pauli Spectrum of QAC⁰

​

Shivam Nadimpalli

Columbia

Columbia

UC Berkeley

Francisca Vasconcelos

Natalie Parham

Henry Yuen (Columbia)

joint work with

arXiv: 2311.09631

This talk

​

​

A new technique (inspired by Fourier analysis of Boolean functions)

​

to analyze QAC⁰ (a model of circuits with many-qubit gates).

Models of shallow quantum circuits

QNC

QNC⁰

Power of many-qubit gates?

• What is the power of shallow circuits augmented with gates that can act on many qubits simultaneously?

​

• Lightcone arguments are no longer a barrier: each output qubit can be affected by all input qubits simultaneously.

​

• Answer depends the kind of many-qubit gates allowed.

QAC

QAC_f: QAC with fanout

Classical AC

QAC⁰ vs QAC_f⁰

The power of QAC_f⁰

PARITY

FANOUT

The power of QAC_f⁰

FANOUT is equivalent to preparing CAT states:

​

​

CAT state preparation

The power of QAC_f⁰

QAC⁰ vs QAC_f⁰

Motivations

• Rising interest in many-qubit/nonlocal interactions:
• Analog quantum simulators: can implement global Hamiltonian evolution

​

• Adaptive measurements: can prepare CAT states, topologically ordered states, etc.

​

• FANOUT may be experimentally realizable in ion traps/neutral atom platforms.

​

• Beyond lightcones: can we develop new theoretical techniques for analyzing quantum circuits that have many-qubit interactions?

​

​

Our results

• We introduce the notion of the Pauli spectrum of a quantum circuit, which is a quantum analogue of the Fourier spectrum of a Boolean function.

​

• Result #1: Pauli spectrum of QAC⁰ circuits (with few ancilla) are highly concentrated on the low-degree components.

​

• Corollary: QAC⁰ circuits with few ancilla cannot approximate PARITY or MAJORITY.

​

• Result #2: Quantum circuits with concentrated Pauli spectrum can be learned sample-efficiently.

​

Pauli analysis of quantum circuits

Pauli spectrum of operators

Pauli spectrum of quantum channels

Low-degree concentration of QAC⁰

Lower bounds for PARITY

Lower bounds for PARITY

Lower bounds for PARITY

Analogy to Boolean Fourier analysis

Analogy to Boolean Fourier analysis

Analogy to Boolean Fourier analysis

Studying the Fourier spectrum of functions computed by various models of computation has been an extremely powerful tool in theoretical computer science:

- Circuit lower bounds

– Pseudorandomness

- Learning theory

- Property testing

- Classical-quantum separations

- more…

Overview of QAC⁰ low-degree concentration

Overview of QAC⁰ low-degree concentration

Learning low-degree channels

Learning quantum dynamics

U

The learning model

The learning model

Choi states can be prepared by running channel on half of maximally entangled state:

Learning quantum channels

Learning quantum channels

Learning algorithm

Learning algorithm

Learning algorithm

Learning QAC⁰ circuits

Alternate learning model

Analogy with classical learning theory

Summary

Summary

• QAC, QAC_f : models of shallow circuits with many-qubit gates

​

• Open question: QAC⁰ = QAC_f⁰?

​

• Broader question: How to analyze circuits with nonlocal interactions?

​

• This work: study Pauli spectrum of quantum circuits

​

Summary

• Main result: QAC⁰ circuits with few ancillas have concentrated Pauli spectrum

​

• Corollary: QAC⁰ circuits with few ancillas cannot approximate QAC_f⁰

​

• Main result: Channels with concentrated Pauli spectrum can be learned using quasipolynomially many Choi samples.

​

Future directions

• Prove our conjecture that QAC⁰ circuits with polynomially many ancillas have concentrated Pauli spectrum.
• This would show QAC⁰ ≠ QAC_f⁰

​

• Study power of other circuit models with nonlocal interactions, such as intermediate measurements, analog Hamiltonian evolution, etc.

​

• Better characterize power of QAC_f⁰: can all of BQP be solved in QAC_f⁰?

​

​

​

Thank You!