Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1701.01062 · Leibniz international proceedings in informatics

Overlapping Qubits

Rui Chao, Reichardt, Ben W., Sutherland, Chris, Thomas Vidick

Published Jan 1, 2017• 26 citations
arXivHTMLPDF

Abstract

An ideal system of $n$ qubits has $2^n$ dimensions. This exponential grants power, but also hinders characterizing the system's state and dynamics. We study a new problem: the qubits in a physical system might not be independent. They can "overlap," in the sense that an operation on one qubit slightly affects the others. We show that allowing for slight overlaps, $n$ qubits can fit in just polynomially many dimensions. (Defined in a natural way, all pairwise overlaps can be $\leq ε$ in $n^{O(1/ε^2)}$ dimensions.) Thus, even before considering issues like noise, a real system of $n$ qubits might inherently lack any potential for exponential power. On the other hand, we also provide an efficient test to certify exponential dimensionality. Unfortunately, the test is sensitive to noise. It is important to devise more robust tests on the arrangements of qubits in quantum devices.

DOI
10.4230/lipics.itcs.2017.48

Related papers

Beyond the Swap Test: Optimal Estimation of Quantum State Overlap

Marco Fanizza, Matteo Rosati, Michalis Skotiniotis +2 more

We study the estimation of the overlap between two unknown pure quantum states of a finite-dimensional system, given M and N copies of each type. This is a fundamental primitive in quantum information processing that is commonly accomplished from the outcomes of N swap tests, a joint measurement on one copy of each type whose outcome probability is a linear function of the squared overlap. We show that a more precise estimate can be obtained by allowing for general collective measurements on all copies. We derive the statistics of the optimal measurement and compute the optimal mean square error in the asymptotic pointwise and finite Bayesian estimation settings. Besides, we consider two strategies relying on the estimation of one or both states and show that, although they are suboptimal, they outperform the swap test. In particular, the swap test is extremely inefficient for small values of the overlap, which become exponentially more likely as the dimension increases. Finally, we show that the optimal measurement is less invasive than the swap test and study the robustness to depolarizing noise for qubit states.

arXiv:1906.10639•Physical Review Letters•Feb 14, 2020•63 citations

Quantum and classical bounds for two-state overlaps

Ernesto F. Galvão, Daniel J. Brod

Suppose we have $N$ quantum systems in unknown states $\left|{\ensuremath{\psi}}_{i}\right\ensuremath{\rangle}$, but we know the value of some pairwise overlaps ${\left|\ensuremath{\langle}{\ensuremath{\psi}}_{k}|{\ensuremath{\psi}}_{l}\ensuremath{\rangle}\right|}^{2}$. What can we say about the values of the unknown overlaps? We provide a complete answer to this problem for three pure states and two given overlaps and a way to obtain bounds for the general case. We discuss how the answer contrasts from that of a classical model featuring only coherence-free, diagonal states, and we describe three applications: basis-independent coherence witnesses, dimension witnesses, and characterization of multiphoton indistinguishability.

arXiv:1902.11039•Physical Review A•Jun 19, 2020•31 citations

Optimal Overlapping Tomography

Kiara Hansenne, Rui Qu, Lisa T. Weinbrenner +7 more

Characterizing large-scale quantum systems is central to fundamental physics and essential for applications of quantum technologies. While a full characterization requires exponentially increasing resources, focusing on application-relevant information can often lead to significantly simplified analysis. Overlapping tomography is such a scheme, allowing one to obtain all the information contained in specific subsystems of multiparticle quantum systems in an efficient manner, but the ultimate limits of this approach remain elusive. We present protocols for overlapping tomography that are optimal with respect to the number of measurement settings. First, by providing algorithmic approaches based on graph theory we find the minimal number of Pauli settings, relating overlapping tomography to the problem of covering arrays in combinatorics. This significantly reduces the number of measurement settings, showing for instance that two-body overlapping tomography of nearest neighbors in qubit systems with planar topologies can always be performed with nine Pauli settings. Second, we prove that using general projective measurements, all k-body marginals can be reconstructed with only 3^{k} settings, independently of the system size. Finally, we demonstrate the practical applicability of our methods in a six-photon experiment. Our results will find applications in learning noise and interaction patterns in quantum computers as well as characterizing fermionic systems in quantum chemistry.

arXiv:2408.05730•Physical Review Letters•Jul 14, 2025•12 citations

Local quantum overlapping tomography

Bruna G. M. Araújo, Márcio M. Taddei, Daniel Cavalcanti +1 more

Reconstructing the full quantum state of a many-body system requires the estimation of a number of parameters that grows exponentially with system size. Nevertheless, there are situations in which one is only interested in a subset of these parameters, and a full reconstruction is not needed. A paradigmatic example is a scenario in which one aims at determining all the reduced states only up to a given size. Overlapping tomography provides constructions to address this problem with a number of product measurements much smaller than what is obtained when performing independent tomography of each reduced state. There are, however, many relevant physical systems with a natural notion of locality where one is mostly interested in the reduced states of neighboring particles. In this work, we study this form of local overlapping tomography. First of all, we show that, contrary to its full version, the number of product-measurement settings needed for local overlapping tomography does not grow with system size. Then, we present strategies for qubit and fermionic systems in selected lattice geometries. The developed methods find a natural application in the estimation of many-body systems prepared in current quantum simulators or quantum computing devices, where interactions are often local.

arXiv:2112.03924•Physical Review A•Dec 28, 2022•8 citations

Practical bound for dimensionality in high-dimensional entanglement

Jacquiline Romero, Miles J. Padgett

The quantum world differs from our classical experience in many ways. Perhaps most curious is the phenomenon of quantum entanglement, where measuring the state of one particle can instantaneously define the state of another, even though the second particle is arbitrarily distant. For much of the 20th century, it was debated whether entanglement really exists. The issue was quantified by Bell’s formulation of the Bell inequality (1), and the subsequent flurry of experiments by Clauser, Aspect, and others, demonstrating that quantum entanglement was real (2⇓–4). All of these early tests were applied to systems where the measured state of one particle can only take one of two values, but such systems are not representative of the wider world. In PNAS, Krenn et al. derive a new entanglement test for systems where the measured state can take on one of many values (Fig. 1) (5). The authors apply their test to the spatial structure (i.e., state) of two separated photons. Krenn et al. confirmed that the photons are entangled over at least 100 of these spatial states. This large number of states allows entanglement in higher dimensions, which can increase both the security of communication and the efficiency of computing protocols (6).

Proceedings of the National Academy of Sciences•Apr 15, 2014•0 citations

Novel strategies for quantum state property estimation

Ivan Palmisano

A significant amount of research is currently devoted to quantum technologies, i.e., technologies that harness the complex features of quantum systems for practical purposes. Remarkably, these have the potential to shape the way we will live in the future by, for example, providing new ways of breaking the current cryptographic security measures or by exponentially enhancing the computational capability of computers. This, in turn, could serve as a means for studying phenomena so complex that they render classical computers completely unusable. With these promises at hand, methods that efficiently certify the correct functioning of quantum devices and computations become of paramount importance. Specifically, it is often required to assess a characterization of the quantum states that come out from a specific computation or experiment. The traditional method of quantum state tomography relies on a rather straightforward but brute-force approach to reconstruct the full density matrix that encodes a quantum state. This method is highly demanding because of the curse of dimensionality, according to which the number of required measurements scales with the system’s dimension, and thus exponentially with the number of qubits. As the quantum protocols demand a progressively higher number of qubits, overall, a complete characterization of quantum states through tomography loses its effectiveness, thus calling for a partial but simpler reconstruction of states. Furthermore, an additional obstacle must be taken into account. In particular, the same complex features of the quantum realm that would help to navigate through the sea of potential applications hinder a growth of the current technological state of the art, which indeed is limited within the so-called NISQ (Noisy Intermediate-Scale Quantum) devices. These, as the name suggests, are characterized by inevitable noises and imperfections, and as such are not advanced enough for achieving a real quantum advantage in the near term. In this Thesis we are going to discuss new techniques for the estimation of properties of unknown quantum states in the context of quantum information science. The protocols that we will present are flexible enough to not only include state tomography within them, but to also adapt to noises and imperfections present in the computational devices. Ivan Palmisano was funded by the CITI-GENS project. This project received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Actions COFUND Action (Grant Agreement No 945231). All views expressed in this article are strictly those of the author and may under no circumstances be regarded as an official position of the European Research Executive Agency or the European Commission.

•Oct 1, 2026•0 citations
An ideal system of nnn qubits has 2n2^n2n dimensions. This exponential grants power, but also hinders characterizing the system's state and dynamics. We study a new problem: the qubits in a physical system might not be independent. They can "overlap," in the sense that an operation on one qubit slightly affects the others. We show that allowing for slight overlaps, nnn qubits can fit in just polynomially many dimensions. (Defined in a natural way, all pairwise overlaps can be ≤ε\leq ε≤ε in nO(1/ε2)n^{O(1/ε^2)}nO(1/ε2) dimensions.) Thus, even before considering issues like noise, a real system of nnn qubits might inherently lack any potential for exponential power. On the other hand, we also provide an efficient test to certify exponential dimensionality. Unfortunately, the test is sensitive to noise. It is important to devise more robust tests on the arrangements of qubits in quantum devices.
We study the estimation of the overlap between two unknown pure quantum states of a finite-dimensional system, given M and N copies of each type. This is a fundamental primitive in quantum information processing that is commonly accomplished from the outcomes of N swap tests, a joint measurement on one copy of each type whose outcome probability is a linear function of the squared overlap. We show that a more precise estimate can be obtained by allowing for general collective measurements on all copies. We derive the statistics of the optimal measurement and compute the optimal mean square error in the asymptotic pointwise and finite Bayesian estimation settings. Besides, we consider two strategies relying on the estimation of one or both states and show that, although they are suboptimal, they outperform the swap test. In particular, the swap test is extremely inefficient for small values of the overlap, which become exponentially more likely as the dimension increases. Finally, we show that the optimal measurement is less invasive than the swap test and study the robustness to depolarizing noise for qubit states.
Suppose we have NNN quantum systems in unknown states $\left|{\ensuremath{\psi}}_{i}\right\ensuremath{\rangle}$, but we know the value of some pairwise overlaps ${\left|\ensuremath{\langle}{\ensuremath{\psi}}_{k}|{\ensuremath{\psi}}_{l}\ensuremath{\rangle}\right|}^{2}$. What can we say about the values of the unknown overlaps? We provide a complete answer to this problem for three pure states and two given overlaps and a way to obtain bounds for the general case. We discuss how the answer contrasts from that of a classical model featuring only coherence-free, diagonal states, and we describe three applications: basis-independent coherence witnesses, dimension witnesses, and characterization of multiphoton indistinguishability.
Characterizing large-scale quantum systems is central to fundamental physics and essential for applications of quantum technologies. While a full characterization requires exponentially increasing resources, focusing on application-relevant information can often lead to significantly simplified analysis. Overlapping tomography is such a scheme, allowing one to obtain all the information contained in specific subsystems of multiparticle quantum systems in an efficient manner, but the ultimate limits of this approach remain elusive. We present protocols for overlapping tomography that are optimal with respect to the number of measurement settings. First, by providing algorithmic approaches based on graph theory we find the minimal number of Pauli settings, relating overlapping tomography to the problem of covering arrays in combinatorics. This significantly reduces the number of measurement settings, showing for instance that two-body overlapping tomography of nearest neighbors in qubit systems with planar topologies can always be performed with nine Pauli settings. Second, we prove that using general projective measurements, all k-body marginals can be reconstructed with only 3^{k} settings, independently of the system size. Finally, we demonstrate the practical applicability of our methods in a six-photon experiment. Our results will find applications in learning noise and interaction patterns in quantum computers as well as characterizing fermionic systems in quantum chemistry.
Reconstructing the full quantum state of a many-body system requires the estimation of a number of parameters that grows exponentially with system size. Nevertheless, there are situations in which one is only interested in a subset of these parameters, and a full reconstruction is not needed. A paradigmatic example is a scenario in which one aims at determining all the reduced states only up to a given size. Overlapping tomography provides constructions to address this problem with a number of product measurements much smaller than what is obtained when performing independent tomography of each reduced state. There are, however, many relevant physical systems with a natural notion of locality where one is mostly interested in the reduced states of neighboring particles. In this work, we study this form of local overlapping tomography. First of all, we show that, contrary to its full version, the number of product-measurement settings needed for local overlapping tomography does not grow with system size. Then, we present strategies for qubit and fermionic systems in selected lattice geometries. The developed methods find a natural application in the estimation of many-body systems prepared in current quantum simulators or quantum computing devices, where interactions are often local.
The quantum world differs from our classical experience in many ways. Perhaps most curious is the phenomenon of quantum entanglement, where measuring the state of one particle can instantaneously define the state of another, even though the second particle is arbitrarily distant. For much of the 20th century, it was debated whether entanglement really exists. The issue was quantified by Bell’s formulation of the Bell inequality (1), and the subsequent flurry of experiments by Clauser, Aspect, and others, demonstrating that quantum entanglement was real (2⇓–4). All of these early tests were applied to systems where the measured state of one particle can only take one of two values, but such systems are not representative of the wider world. In PNAS, Krenn et al. derive a new entanglement test for systems where the measured state can take on one of many values (Fig. 1) (5). The authors apply their test to the spatial structure (i.e., state) of two separated photons. Krenn et al. confirmed that the photons are entangled over at least 100 of these spatial states. This large number of states allows entanglement in higher dimensions, which can increase both the security of communication and the efficiency of computing protocols (6).
A significant amount of research is currently devoted to quantum technologies, i.e., technologies that harness the complex features of quantum systems for practical purposes. Remarkably, these have the potential to shape the way we will live in the future by, for example, providing new ways of breaking the current cryptographic security measures or by exponentially enhancing the computational capability of computers. This, in turn, could serve as a means for studying phenomena so complex that they render classical computers completely unusable. With these promises at hand, methods that efficiently certify the correct functioning of quantum devices and computations become of paramount importance. Specifically, it is often required to assess a characterization of the quantum states that come out from a specific computation or experiment. The traditional method of quantum state tomography relies on a rather straightforward but brute-force approach to reconstruct the full density matrix that encodes a quantum state. This method is highly demanding because of the curse of dimensionality, according to which the number of required measurements scales with the system’s dimension, and thus exponentially with the number of qubits. As the quantum protocols demand a progressively higher number of qubits, overall, a complete characterization of quantum states through tomography loses its effectiveness, thus calling for a partial but simpler reconstruction of states. Furthermore, an additional obstacle must be taken into account. In particular, the same complex features of the quantum realm that would help to navigate through the sea of potential applications hinder a growth of the current technological state of the art, which indeed is limited within the so-called NISQ (Noisy Intermediate-Scale Quantum) devices. These, as the name suggests, are characterized by inevitable noises and imperfections, and as such are not advanced enough for achieving a real quantum advantage in the near term. In this Thesis we are going to discuss new techniques for the estimation of properties of unknown quantum states in the context of quantum information science. The protocols that we will present are flexible enough to not only include state tomography within them, but to also adapt to noises and imperfections present in the computational devices. Ivan Palmisano was funded by the CITI-GENS project. This project received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Actions COFUND Action (Grant Agreement No 945231). All views expressed in this article are strictly those of the author and may under no circumstances be regarded as an official position of the European Research Executive Agency or the European Commission.