Zhicheng Zhang

Here, P is a property testing problem, Q(P) is its query complexity, and S(P) is its sample complexity

So we can go back and forth between query and sample complexities. This leads to a list of new bounds, as well as new proofs of known results

5/5

Conjugate queries can help We give a natural problem over input quantum oracles $U$ which cannot be solved with exponentially many black-box queries to $U$ and $U^\dagger$, but which can be solved with constant many queries to ...

Tang, Wright, and Zhandry (arxiv.org/abs/2510.07622) recently proved: given samples of ρ, you can simulate a query to a unitary preparing a purification of ρ.

This beautiful result can strengthen quantum sample-to-query lifting into:

Q(P) = Ω(√S(P))

4/5

Quantum Lower Bounds by Sample-to-Query Lifting The polynomial method by Beals, Buhrman, Cleve, Mosca, and de Wolf (FOCS 1998, J. ACM 2001), the adversary method by Ambainis (STOC 2000, J. Comput. Syst. Sci. 2002), and the compressed oracle method ...

In our prior work (arxiv.org/abs/2308.01794), "quantum sample-to-query lifting" linked sample and query complexities.

Simple idea: if several samples can simulate a query, then you can
(1) convert a query algorithm to a sample algorithm
(2) convert a sample lower bound to a query lower bound

3/5

What is "property testing" of a quantum state?

You get samples of an unknown mixed quantum state ρ, promised to be in YES or NO. The task is to decide if ρ ∈ YES or ρ ∈ NO using as few samples as possible.

Another input model: given query to a black-box unitary encoding ρ, instead of samples

2/5

A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting Quantum sample-to-query lifting, a relation between quantum sample complexity and quantum query complexity presented in Wang and Zhang (SIAM J. Comput. 2025), was significantly strengthened by Tang, W...

New paper with Kean Chen and Qisheng Wang is out:

arxiv.org/abs/2512.01971

We compile a list of complexity bounds for property testing of classical distributions & quantum states via "quantum sample-to-query lifting"

The list contains 49 bounds, with 41 new and 18 (near-)optimal

1/5

Final remark:

Since the threat comes from violating a Bell-type inequality (specifically, Mermin inequality), it has a purely quantum nature:

(a) It makes no computational assumption
(b) It doesn't come from additional communication channel, as entanglement can't transmit information.

5/5

While the scenario is specific, it reveals a threat from quantum entanglement to access control, showing existing models are insufficient.

To protect against the threat, we design new quantum access control models, and analyze their security, flexibility and efficiency.

4/5

We show the answer is likely *no*.

Intuition:

Access control governs how users are allowed to access resources. If a system's security relies on a Bell-type inequality, and the access control mechanism allows users to test it, then introducing quantum resources can cause a security breach.

3/5

Motivation:

You trust a classical computer system, as its access control mechanism is *proven* to protect your private information. One day, the system upgrades by integrating quantum computing services. Should you still trust this system?

2/5

Access Control Threatened by Quantum Entanglement Access control is a cornerstone of computer security that prevents unauthorised access to resources. In this paper, we study access control in quantum computer systems. We present the first explicit s...

New paper with Mingsheng Ying on Quantum Access Control is out:

arxiv.org/abs/2507.02622

Access control is a cornerstone of computer security. We show a classically secure access control system can be insecure when adapted to the quantum setting. The source of the threat is *Entanglement*.

1/5

Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs Quantum recursive programming has been recently introduced for describing sophisticated and complicated quantum algorithms in a compact and elegant way. However, implementation of quantum recursion in...

(b) "Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs" (arxiv.org/abs/2408.10054)

(4/4)

Verification of Recursively Defined Quantum Circuits Recursive techniques have recently been introduced into quantum programming so that a variety of large quantum circuits and algorithms can be elegantly and economically programmed. In this paper, we p...

It's based on the following two joint works with Mingsheng Ying. I'll also present paper (b) at PLDI 2025 in June.

(a) "Verification of Recursively Defined Quantum Circuits" (arxiv.org/abs/2404.05934)

(3/4)

Content:
- Quantum & PL background
- Syntax & Semantics of RQC++, a quantum recursive programming language
- Various examples
- A theoretical framework for efficiently implementing quantum recursive programs

(2/4)

Quantum recursive programs - YouTube Talks given at DIMACS, Rutgers University during April and May 2025 by Zhicheng Zhang, a PhD student at University of Technology Sydney

Excited to share my 5-lecture mini-course 🎬 on "Quantum Recursive Programming"! An elegant way to program complicated quantum algorithms ⚛️

*No prior QC or PL knowledge is needed!

Given during my visit to DIMACS at Rutgers University.

(www.youtube.com/playlist?lis...)

(1/4)

Thanks a lot Clément for this post!

Can I be added please? Thanks!