Abstract Quantum circuit optimizers use rewrite rules from circuit equivalences, yet prior work has identified thousands of such identities, creating substantial challenges for their storage, management, and effective application. For many widely used unitary gate sets, including Clifford+T, this apparent complexity is largely redundant, raising a fundamental question: How many quantum circuit identities are actually needed to generate all others? In this work, we provide strong evidence that a small pruned set of identities suffices to generate all circuit equivalences of bounded depth. Surprisingly, for circuits on up to nine qubits in which each side of an equality has depth at most ten, fewer than twenty identities are sufficient to derive all others, and for circuits on up to five qubits with depth at most ten, only 17 rules–each involving at most three qubits–are enough. These results enable significantly more compact and efficient rewriting systems for quantum compiler optimization and reveal underlying algebraic structure in common gate sets, showing that the vast majority of known circuit identities are consequences of a small foundational basis.

Access to the time-reverse $U^{-1}$ of an unknown quantum unitary process $U$ is widely assumed in quantum learning, metrology, and many-body physics. The fundamental task of unitary time-reversal dictates implementing $U^{-1}$ to within diamond-norm error $ε$ using black-box queries to the $d$-dimensional unitary $U$. Although the query complexity of this task has been extensively studied, existing lower bounds either hold only for the exact case (i.e., $ε=0$) or are suboptimal in $d$. This raises a central question: does approximation help reduce the query complexity of unitary time-reversal? We settle this question in the negative by establishing a robust and tight lower bound $Ω((1-ε)d^2)$ with explicit dependence on the error $ε$. This implies that unitary time-reversal retains optimal exponential hardness (in the number of qubits) even when constant error is allowed. Our bound applies to adaptive and coherent algorithms with unbounded ancillas and holds even when $ε$ is an average-case distance error.

Reasoning about quantum programs remains a fundamental challenge, regardless of the programming model or computational paradigm. Existing verification techniques are insufficient -- even for quantum circuits, a deliberately restricted model that lacks classical control, but still underpins many current quantum algorithms. Many existing formal methods require exponential time and space to represent and manipulate (representations of) assertions and judgments, making them impractical for quantum circuits with many qubits. This paper presents SAQR-QC, a logic for Scalable but Approximate Quantitative Reasoning about Quantum Circuits. SAQR-QC has three characteristics: (i) some deliberate loss of precision is built into it; (ii) it has a mechanism to help the accumulated loss of precision during a sequence of reasoning steps remain small; and (iii) every reasoning step is local -- involving just a small number of qubits -- making reasoning scalable. We demonstrate the effectiveness of SAQR-QC via two case studies: the verification of GHZ circuits involving non-Clifford gates, and the analysis of quantum phase estimation -- a core subroutine in Shor's factoring algorithm.

Verifying quantum systems has attracted a lot of interest in the last decades.In this paper, we study the quantitative model-checking of quantum continuous-time Markov chains (quantum CTMCs). The branching-time properties of quantum CTMCs are specified by continuous stochastic logic (CSL), which is well-known for verifying real-time systems, including classical CTMCs. The core of checking the CSL formulas lies in tackling multiphase until formulas. We develop an algebraic method using proper projection, matrix exponentiation, and definite integration to symbolically calculate the probability measures of path formulas. Thus the decidability of CSL is established. To be efficient, numerical methods are incorporated to guarantee that the time complexity is polynomial in the encoding size of the input model and linear in the size of the input formula. A running example of Apollonian networks is further provided to demonstrate our method.

This paper concerns the problem of checking if two shallow (i.e., constant-depth) quantum circuits perform equivalent computations. Equivalence checking is a fundamental correctness question—needed, e.g., for ensuring that transformations applied to a quantum circuit do not alter its behavior. For quantum circuits, the problem is challenging because a straightforward representation on a classical computer of each circuit’s quantum state can require time and space that are exponential in the number of qubits n . The paper presents Projection-Based Equivalence Checking (PBEC), which provides decision procedures for two variants of the equivalence-checking problem. Both can be carried out on a classical computer in time and space that, for any fixed depth, is linear in n . Our key insight is that local projections can serve as constraints that fully characterize the output state of a shallow quantum circuit. The output state is the unique quantum state that satisfies all the constraints. Beyond equivalence checking, we show how to use the constraint representation to check a class of assertions, both statically and at run time. Our assertion-checking methods are sound and complete for assertions expressed as conjunctions of local projections. Our experiments showed that computing the constraint representation of a random 100-qubit 1D circuit of depth 6 takes 129.64 seconds. Equivalence checking between two random 100-qubit 1D circuits of depth 3 requires 4.46 seconds for fixed input | 0 〉 ⊗ 100 , and no more than 31.96 seconds for arbitrary inputs. Computing the constraint description for a random 100-qubit circuit of depth 3 takes 6.99 seconds for a 2D structure, compared to 10.67 seconds for a circuit with arbitrary connectivity. At depth 2, equivalence checking takes 0.20 seconds for fixed input and 0.44 seconds for arbitrary input, with similar performance for both 2D and arbitrary-connectivity circuits.

In this work, we show that the Petz recovered state ρ1/2BC(ρ−1/2BρABρ−1/2B⊗IC)ρ1/2BCis continuous regarding its marginals ρABand ρBC. In terms of infidelity 1 −F(ρ, σ) = 1 − tr | √ ρ √ σ| and trace norm ∥ ρ − σ ∥1= tr(|ρ − σ|), we obtain the following dimension-independent estimate 1 −F(ρAB, σAB) ≤ δ, 1 −F(ρBC, σBC) ≤ δ =⇒ 1 −F(ρABC, σABC) ≤ 18δ, ∥ ρAB− σAB∥1≤ ε, ∥ ρBC− σBC∥1≤ ε =⇒∥ ρABC− σABC∥≤ ε + 4ε1/2. As applications, we obtain the following applications in tomography of quantum Markov chains: • The sample complexity of quantum Markov chain tomography, i.e., how many copies of an unknown quantum Markov chain are necessary and sufficient to determine the state, is ˜Θ ((d2A+d2C)d2B/δ), and ˜Θ((d2A+d2C)d2B/ϵ2), where δ denotes infidelity error and ϵ denotes trace distance. • The sample complexity of quantum Markov chain certification, i.e., to certify whether a tripartite state equals a given quantum Markov chain σABCor at least δ-far from σABC, is Θ((dA+dC)dB/δ), and Θ((dA+dC)dB/ϵ2). • Õ(mindAd3Bd3C,d3Ad3BdC/ϵ2) copies of sample are sufficient to certify whether ρABCis a quantum Markov chain or ϵ-far from its Petz recovered state in trace distance. This implies that full state tomography is not always necessary for testing whether ρABCis a quantum Markov chain (equals to its Petz recovered state) or not.

Efficient and reliable entanglement distribution forms the core of quantum network architecture. The Quantum Max-Flow concept defines the upper boundary for efficiently transmitting entanglement within quantum tensor networks (Calegari, Freedman, and Walker, Journal of the American Mathematical Society, 2010). Despite the general invalidity of the Quantum analog of the Max-Flow Min-Cut theorem, this paper introduces a precise Quantum Max-Flow Min-Cut Theorem tailored to quantum tensor networks enhanced by ancilla entanglement. Specifically, our research establishes infinite ’n’ values for any quantum tensor network, where the Quantum Max-Flow matches the Quantum Min-Cut by attaching a maximally entangled state with dimension ’n’ to each edge. Our protocol exclusively relies on quantum teleportation and guarantees unambiguous success. This work highlights the potential of quantum repeaters, enabled by ancilla entanglement, to efficiently distribute entanglement throughout quantum networks.

Abstract Quantum computation is inevitably subject to imperfections in its implementation. These imperfections arise from various sources, including environmental noise at the hardware level and the introduction of approximate implementations by quantum algorithm designers, such as lower-depth computations. Given the significant advantage of relational logic in program reasoning and the importance of assessing the robustness of quantum programs between their ideal specifications and imperfect implementations, we design a proof system to verify the approximate relational properties of quantum programs. We demonstrate the effectiveness of our approach by providing the first formal verification of the renowned low-depth approximation of the quantum Fourier transform. Furthermore, we validate the approximate correctness of the repeat-until-success algorithm. From the technical point of view, we develop approximate quantum coupling as a fundamental tool to study approximate relational reasoning for quantum programs, a novel generalization of the widely used approximate probabilistic coupling in probabilistic programs, answering a previously posed open question for projective predicates.

Studying the computational complexity and designing fast algorithms for determining winners under voting rules are classical and fundamental questions in computational social choice. In this paper, we accelerate voting by leveraging quantum computation: we propose a quantum-accelerated voting algorithm that can be applied to any anonymous voting rule. We show that our algorithm can be quadratically faster than any classical algorithm (based on sampling with replacement) under a wide range of common voting rules, including positional scoring rules, Copeland, and single transferable voting (STV). Precisely, our quantum-accelerated voting algorithm outputs the correct winner with high probability in $\Theta\left(\frac{n}{\text{MOV}}\right)$ time, where $n$ is the number of votes and $\text{MOV}$ is margin of victory, the smallest number of voters to change the winner. In contrast, any classical voting algorithm based on sampling with replacement requires $\Omega\left(\frac{n^2}{\text{MOV}^2}\right)$ time under a large class of voting rules. Our theoretical results are supported by experiments under plurality, Borda, Copeland, and STV.

This paper studies the quantum identity testing problem, a quantum analogue of distribution identity testing. The goal is to determine whether a quantum state is identical to another fixed quantum state, using as few state samples as possible. Rather than general entangled measurements, we consider the less powerful but experimentally friendly Pauli measurements. We follow the standard setting where Pauli measurements are regarded as two-outcome measurements, i.e., each$n$-qubit Pauli measurement has a one-bit outcome. We prove that for an$n$-qubit quantum system, the sample complexity of this problem is$\Theta \left({\mathrm {poly}(n)\cdot \frac {4^{n}}{\epsilon ^{2}}}\right)$if only Pauli measurements are allowed. In other words, we provide simple algorithms to determine whether two$n$-qubit quantum states,$\rho $and$\sigma $, are identical or$\epsilon $-far in trace distance using Pauli measurements, using$O\left({\min \{n^{4},n^{3}+\log ^{3}(1/\epsilon)\}\cdot \frac {4^{n}}{\epsilon ^{2}}}\right)$copies of$\rho $and$\sigma $. Interestingly,$\mathcal {O}\left({\frac {4^{n}}{\epsilon ^{2}}}\right)$copies are not sufficient under this setting.

This article proves a structured program theorem for flowchart quantum programs. The theorem states that any flowchart quantum program is equivalent to a single quantum program that repeatedly executes a quantum measurement and a subprogram, so long as the measurement outcome is true. Moreover, their expected runtime, variance, and general moments are the same. This theorem simplifies the quantum program’s verification significantly. – We derive an analytical characterization of the termination problem for quantum programs in polynomial time. Our procedure is more efficient and accurate with much simpler techniques than the analysis of this problem, as described in [ 29 ]. – We compute the expected runtime analytically and exactly for quantum programs in polynomial time. This result improves the methods based on the weakest precondition calculus for the question recently developed in [ 31 , 34 ]. – We show that a single loop rule is a relatively complete Hoare logic for quantum programs after applying our structured theorem. Although using fewer rules, our method verifies a broader class of quantum programs, compared with the results in [ 45 ] and [ 56 ].

Abstract A continuous-time Markov chain (CTMC) execution is a continuous class of probability distributions over states. This paper proposes a probabilistic linear-time temporal logic, namely continuous-time linear logic (CLL), to reason about the probability distribution execution of CTMCs. We define the syntax of CLL on the space of probability distributions. The syntax of CLL includes multiphase timed until formulas, and the semantics of CLL allows time reset to study relatively temporal properties. We derive a corresponding model-checking algorithm for CLL formulas. The correctness of the model-checking algorithm depends on Schanuel’s conjecture, a central open problem in transcendental number theory. Furthermore, we provide a running example of CTMCs to illustrate our method.

Bug-catching is important for developing quantum programs. Motivated by the incorrectness logic for classical programs, we propose an incorrectness logic towards a logical foundation for static bug-catching in quantum programming. The validity of formulas in this logic is dual to that of quantum Hoare logics. We justify the formulation of validity by an intuitive explanation from a reachability point of view and a comparison against several alternative formulations. Compared with existing works focusing on dynamic analysis, our logic provides sound and complete arguments. We further demonstrate the usefulness of the logic by reasoning several examples, including Grover's search, quantum teleportation, and a repeat-until-success program. We also automate the reasoning procedure by a prototyped static analyzer built on top of the logic rules.

In the above article[1], we add some missing citations in the Notations and Preliminaries section. The new Notations and Preliminaries section is as follows.

In this paper, we study the quantum identity testing problem, i.e., testing whether two given quantum states are identical, and quantum independence testing problem, i.e., testing whether a given multipartite quantum state is in tensor product form. For the quantum identity testing problem of 𝒟(ℂ^d) system, we provide a deterministic measurement scheme that uses 𝒪(d²/ε²) copies via independent measurements with d being the dimension of the state and ε being the additive error. For the independence testing problem 𝒟(ℂ^d₁⊗ℂ^{d₂}⊗⋯⊗ℂ^{d_m}) system, we show that the sample complexity is Θ̃((Π_{i = 1}^m d_i)/ε²) via collective measurements, and 𝒪((Π_{i = 1}^m d_i²)/ε²) via independent measurements. If randomized choice of independent measurements are allowed, the sample complexity is Θ(d^{3/2}/ε²) for the quantum identity testing problem, and Θ̃((Π_{i = 1}^m d_i^{3/2})/ε²) for the quantum independence testing problem.

We study the discrimination of a pair of orthogonal quantum states in the many-copy setting. This is not a problem when arbitrary quantum measurements are allowed, as then the states can be distinguished perfectly even with one copy. However, it becomes highly nontrivial when we consider states of a multipartite system and locality constraints are imposed. We hence focus on the restricted families of measurements such as local operation and classical communication (LOCC), separable operations (SEP), and the positive-partial-transpose operations (PPT) in this paper. We first study asymptotic discrimination of an arbitrary multipartite entangled pure state against its orthogonal complement using LOCC/SEP/PPT measurements. We prove that the incurred optimal average error probability always decays exponentially in the number of copies, by proving upper and lower bounds on the exponent. In the special case of discriminating a maximally entangled state against its orthogonal complement, we determine the explicit expression for the optimal average error probability, thus establishing the associated Chernoff exponent. Our technique is based on the idea of using PPT operations to approximate LOCC. Then, we show an infinite asymptotic separation between SEP and PPT operations by providing a pair of states constructed from an unextendible product basis (UPB): they can be distinguished perfectly by PPT measurements, while the optimal error probability using SEP measurements admits an exponential lower bound. On the technical side, we prove this result by providing a quantitative version of the well-known statement that the tensor product of UPBs is UPB.

We propose a model of the substructural logic of Bunched Implications (BI) that is suitable for reasoning about quantum states. In our model, the separating conjunction of BI describes separable quantum states. We develop a program logic where pre- and post-conditions are BI formulas describing quantum states—the program logic can be seen as a counterpart of separation logic for imperative quantum programs. We exercise the logic for proving the security of quantum one-time pad and secret sharing, and we show how the program logic can be used to discover a flaw in Google Cirq’s tutorial on the Variational Quantum Algorithm (VQA).

In quantum computing, the basic unit of information is a qubit. Simulation of a general quantum program takes exponential time in the number of qubits, which makes simulation infeasible beyond 50 qubits on current supercomputers. So, for the understanding of larger programs, we turn to static techniques. In this paper, we present an abstract interpretation of quantum programs and we use it to automatically verify assertions in polynomial time. Our key insight is to let an abstract state be a tuple of projections. For such domains, we present abstraction and concretization functions that form a Galois connection and we use them to define abstract operations. Our experiments on a laptop have verified assertions about the Bernstein-Vazirani, GHZ, and Grover benchmarks with 300 qubits.

We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for communication. For an arbitrary protocol with n messages, designed for a noiseless qudit channel over a poly (n ) size alphabet, our main result is a simulation method that fails with probability less than 2-Θ(nϵ)and uses a qudit channel over the same alphabet n(1 + Θ(√{ϵ} )) times, of which an ϵ fraction can be corrupted adversarially. The simulation is thus capacity achieving to leading order, and we conjecture that it is optimal up to a constant factor in the √{ϵ} term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Our work improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al., SICOMP'19] for low ϵ.

We consider the problem of testing two hypotheses of quantum operations in a setting of many uses where an arbitrary prior probability distribution is given. The Chernoff exponent for quantum operations is investigated to track the minimal average error probability of discriminating two quantum operations asymptotically. We answer the question, “When is the Chernoff exponent for quantum operations finite?” We show that either two quantum operations can be perfectly distinguished with finite uses, or the minimal discrimination error decays exponentially with respect to the number of uses asymptotically. That is, the Chernoff exponent is finite if and only if the quantum operations can not be perfectly distinguished with finite uses. This rules out the possibility of super-exponential decay of error probability. Upper bounds of the Chernoff exponent for quantum operations are provided.

Let R be an invariant polynomial ring of a reductive group acting on a vector space, and let d be the minimum integer such that R is generated by those polynomials in R of degree no more than d. To upper bound such d is a long standing open problem since the very initial study of the invariant theory in the 19th century. Motivated by its significant role in characterizing multipartite entanglement, we study the invariant polynomial rings of local unitary groups - the direct product of unitary groups acting on the tensor product of Hilbert spaces, and local general linear groups - the direct product of general linear groups acting on the tensor product of Hilbert spaces. For these two group actions, we prove explicit upper bounds on the degrees needed to generate the corresponding invariant polynomial rings. On the other hand, systematic methods are provided to construct all homogeneous polynomials that are invariant under these two groups for any fixed degree. Thus, our results can be regarded as a complete characterization of the invariant polynomial rings. As an interesting application, we show that multipartite entanglement is additive in the sense that two multipartite states are local unitary equivalent if and only if r-copies of them are local unitary equivalent for some r.

Relational verification of quantum programs has many potential applications in quantum and post-quantum security and other domains. We propose a relational program logic for quantum programs. The interpretation of our logic is based on a quantum analogue of probabilistic couplings. We use our logic to verify non-trivial relational properties of quantum programs, including uniformity for samples generated by the quantum Bernoulli factory, reliability of quantum teleportation against noise (bit and phase flip), security of quantum one-time pad and equivalence of quantum walks.

In this paper, we propose Proq, a runtime assertion scheme for testing and debugging quantum programs on a quantum computer. The predicates in Proq are represented by projections (or equivalently, closed subspaces of the state space), following Birkhoff-von Neumann quantum logic. The satisfaction of a projection by a quantum state can be directly checked upon a small number of projective measurements rather than a large number of repeated executions. On the theory side, we rigorously prove that checking projection-based assertions can help locate bugs or statistically assure that the semantic function of the tested program is close to what we expect, for both exact and approximate quantum programs. On the practice side, we consider hardware constraints and introduce several techniques to transform the assertions, making them directly executable on the measurement-restricted quantum computers. We also propose to achieve simplified assertion implementation using local projection technique with soundness guaranteed. We compare Proq with existing quantum program assertions and demonstrate the effectiveness and efficiency of Proq by its applications to assert two sophisticated quantum algorithms, the Harrow-Hassidim-Lloyd algorithm and Shor’s algorithm.

Certifying multipartite entanglement is a fundamental task. Since n-qubit state is parameterized by 4n- 1 real numbers, it is interesting to design a measurement setup that detects multipartite entanglement with as little effort as possible, and at a minimum without fully revealing the whole information of the state, the so-called “tomography”. In this paper, we study the relationship between multipartite entanglement certification and tomography, with the constraint that only single-copy measurements are allowed. We show that by using nonadaptive single-copy measurements, universal entanglement detection, among all states, can not be accomplished without full state tomography. Moreover, we show that almost all multipartite correlations, including the genuine entanglement and the entanglement depth, require full state tomography to detect in this measurement setting. We also observe that universal entanglement detection, among pure states, can be accomplished using much fewer measurements than full state tomography even using only local measurements.

We derive a variant of quantum Hoare logic (QHL), called applied quantum Hoare logic (aQHL for short), by: 1. restricting QHL to a special class of preconditions and postconditions, namely projections, which can significantly simplify verification of quantum programs and are much more convenient when used in debugging and testing; and 2. adding several rules for reasoning about robustness of quantum programs, i.e. error bounds of outputs. The effectiveness of aQHL is shown by its applications to verify two sophisticated quantum algorithms: HHL (Harrow-Hassidim-Lloyd) for solving systems of linear equations and qPCA (quantum Principal Component Analysis).

We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for communication. For an arbitrary protocol with n messages, designed for noiseless qudit channels (where d is arbitrary), our main result is a simulation method that fails with probability less than 2−Θ (nє) and uses a qudit channel n (1 + Θ (√є)) times, of which an є fraction can be corrupted adversarially. The simulation is thus capacity achieving to leading order, and we conjecture that it is optimal up to a constant factor in the √є term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Perhaps surprisingly, this outperforms the best known overhead of 1 + O(√є loglog1/є) in the corresponding classical model, which is also conjectured to be optimal [Haeupler, FOCS’14]. Our work also improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al., FOCS’14] for low є.

We exhibit a Boolean function for which the quantum communication complexity is exponentially larger than the classical information complexity. An exponential separation in the other direction was already known from the work of Kerenidis et. al. [SICOMP 44, pp. 1550-1572], hence our work implies that these two complexity measures are incomparable.

It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. Previously, it was known only that estimating states to error ε in trace distance required O(dr2/ε2) copies for a d-dimensional density matrix of rank r. Here, we give a theoretical measurement scheme (POVM) that requires O(dr/δ)ln (d/δ) copies to estimate ρ to error δ in infidelity, and a matching lower bound up to logarithmic factors. This implies O((dr/ε2)ln (d/ε)) copies suffice to achieve error ε in trace distance. We also prove that for independent (product) measurements, Ω(dr2/δ2)/ ln(1/δ) copies are necessary in order to achieve error δ in infidelity. For fixed d, our measurement can be implemented on a quantum computer in time polynomial in n.

Motivated by the recent resolution of asymptotic quantum birkhoff conjecture (AQBC), we attempt to estimate the distance between a given unital quantum channel and the convex hull of unitary channels. We provide two lower bounds on this distance by employing techniques from quantum information and operator algebras, respectively. We then show how to apply these results to construct some explicit counterexamples to AQBC. We also point out an interesting connection between the Grothendieck's inequality and AQBC.

We discuss quantum capacities for two types of entanglement networks: Q for the quantum repeater network with free classical communication, and R for the tensor network as the rank of the linear operation represented by the tensor network. We find that Q always equals R in the regularized case for the same network graph. However, the relationships between the corresponding one-shot capacities Q1and R1are more complicated, and the min-cut upper bound is in general not achievable. We show that the tensor network can be viewed as a stochastic protocol with the quantum repeater network, such that R1is a natural upper bound of Q1. We analyze the possible gap between R1and Q1for certain networks, and compare them with the one-shot classical capacity of the corresponding classical network.

It is a fundamental problem to decide how many copies of an unknown mixed quantum state are necessary and sufficient to determine the state. This is the quantum analogue of the problem of estimating a probability distribution given some number of samples.

We prove limitations on LOCC and separable measurements in bipartite state discrimination problems using techniques from convex optimization. Specific results that we prove include: an exact formula for the optimal probability of correctly discriminating any set of either three or four Bell states via LOCC or separable measurements when the parties are given an ancillary partially entangled pair of qubits; an easily checkable characterization of when an unextendable product set is perfectly discriminated by separable measurements, along with the first known example of an unextendable product set that cannot be perfectly discriminated by separable measurements; and an optimal bound on the success probability for any LOCC or separable measurement for the recently proposed state discrimination problem of Yu, Duan, and Ying.

We study the distinguishability of bipartite quantum states by positive operator-valued measures with positive partial transpose (PPT POVMs). The contributions of this paper include: 1) we give a negative answer to an open problem of showing a limitation of a previous known method for detecting nondistinguishability; 2) we show that a maximally entangled state and its orthogonal complement, no matter how many copies are supplied, cannot be distinguished by the PPT POVMs, even unambiguously. This result is much stronger than the previous known ones; and 3) we study the entanglement cost of distinguishing quantum states. It is proved that √{2/3}|00〉+√{1/3}|11〉 is sufficient and necessary for distinguishing three Bell states by the PPT POVMs. An upper bound of entanglement cost of distinguishing a d ⊗ d pure state and its orthogonal complement is obtained for separable operations. Based on this bound, we are able to construct two orthogonal quantum states, which cannot be distinguished unambiguously by separable POVMs, but finite copies would make them perfectly distinguishable by local operations and classical communication. We further observe that a two-qubit maximally entangled state is always enough for distinguishing a d ⊗ d pure state and its orthogonal complement by the PPT POVMs, no matter the value of d. In sharp contrast, an entangled state with Schmidt number at least d is always needed for distinguishing such two states by separable POVMs. As an application, we show that the entanglement cost of distinguishing a d ⊗ d maximally entangled state and its orthogonal complement must be a maximally entangled state for d=2, which implies that teleportation is optimal, and in general, it could be chosen as O(logd/d).

We define a formal framework for reasoning about linear-time properties of quantum systems in which quantum automata are employed in the modeling of systems and certain (closed) subspaces of state Hilbert spaces are used as the atomic propositions about the behavior of systems. We provide an algorithm for verifying invariants of quantum automata. Then, an automata-based model-checking technique is generalized for the verification of safety properties recognizable by reversible automata and ω--properties recognizable by reversible Büchi automata.

Quantum cryptography has been extensively studied in the last twenty years, but information-flow security of quantum computing and communication systems has been almost untouched in the previous research. Due to the essential difference between classical and quantum systems, formal methods developed for classical systems, including probabilistic systems, cannot be directly applied to quantum systems. This paper defines an automata model in which we can rigorously reason about information-flow security of quantum systems. The model is a quantum generalisation of Goguen and Meseguer's noninterference. The unwinding proof technique for quantum noninterference is developed, and a certain compositionality of security for quantum systems is established. The proposed formalism is then used to prove security of access control in quantum systems.