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• 12 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•61 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•24 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•6 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•4 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

Two qubits and beyond

Jonathan A. Jones, Dieter Jaksch

As we have seen, even a single qubit is a surprisingly interesting object. However, the real power of quantum information processing begins with systems of two or more qubits. Before studying these in detail we need to expand our notation a little. Consider a system of two qubits, labeled a and b , each of which has two basis states, |0⧽ and |1⧽. The whole system then has four basis states, which can be written as |0 a 0 b ⧽, |0 a 1 b ⧽, |1 a 0 b ⧽ and |1 a 1 b ⧽, and can be found in any general superposition of these states, so that it occupies a four-dimensional Hilbert space. In the same way, a system of three qubits inhabits an eight-dimensional Hilbert space, and so on. This exponential increase in the size of the Hilbert space with a linear increase in the number of qubits underlies the power of quantum computers. Direct products The size of the Hilbert spaces involved can also be a huge problem, however, making it difficult to describe states of systems with many qubits. A partial solution is to note that some states can be described in a simpler way, using the concept of direct products . These states, in which the individual qubits can in principle be discussed separately, make up a tiny minority of the states accessible to a multi-qubit system, but include many important states, most notably the basis states. States of this kind are said to be separable , and states which are not separable are said to be entangled . Entangled states are much more interesting than separable ones, but it is wise to begin with the simpler case.

Cambridge University Press eBooks•Jul 19, 2012•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).
As we have seen, even a single qubit is a surprisingly interesting object. However, the real power of quantum information processing begins with systems of two or more qubits. Before studying these in detail we need to expand our notation a little. Consider a system of two qubits, labeled a and b , each of which has two basis states, |0⧽ and |1⧽. The whole system then has four basis states, which can be written as |0 a 0 b ⧽, |0 a 1 b ⧽, |1 a 0 b ⧽ and |1 a 1 b ⧽, and can be found in any general superposition of these states, so that it occupies a four-dimensional Hilbert space. In the same way, a system of three qubits inhabits an eight-dimensional Hilbert space, and so on. This exponential increase in the size of the Hilbert space with a linear increase in the number of qubits underlies the power of quantum computers. Direct products The size of the Hilbert spaces involved can also be a huge problem, however, making it difficult to describe states of systems with many qubits. A partial solution is to note that some states can be described in a simpler way, using the concept of direct products . These states, in which the individual qubits can in principle be discussed separately, make up a tiny minority of the states accessible to a multi-qubit system, but include many important states, most notably the basis states. States of this kind are said to be separable , and states which are not separable are said to be entangled . Entangled states are much more interesting than separable ones, but it is wise to begin with the simpler case.