Quantum 6, 757 (2022). https://doi.org/10.22331/q-2022-07-07-757 We consider the power of local algorithms for approximately solving Max $k$XOR, a generalization of two constraint satisfaction problems previously studied with classical and quantum algorithms (MaxCut and Max E3LIN2). […]
Quantum 6, 756 (2022). https://doi.org/10.22331/q-2022-07-07-756 In this paper we study the Platonic Bell inequalities for all possible dimensions. There are five Platonic solids in three dimensions, but there are also solids with Platonic properties (also […]
Quantum 6, 755 (2022). https://doi.org/10.22331/q-2022-07-07-755 We consider a bipartite transformation that we call $self-embezzlement$ and use it to prove a constant gap between the capabilities of two models of quantum information: the conventional model, where […]
Quantum 6, 754 (2022). https://doi.org/10.22331/q-2022-06-30-754 We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters’09] for low-rank matrices [Wossnig, Zhao, and Prakash, Physical […]
Quantum 6, 753 (2022). https://doi.org/10.22331/q-2022-06-30-753 We present a formalism that captures the process of proving quantum superiority to skeptics as an interactive game between two agents, supervised by a referee. Bob, is sampling from a […]
Quantum 6, 752 (2022). https://doi.org/10.22331/q-2022-06-30-752 Quantum finite automata (QFA) are basic computational devices that make binary decisions using quantum operations. They are known to be exponentially memory efficient compared to their classical counterparts. Here, we […]
Quantum 6, 751 (2022). https://doi.org/10.22331/q-2022-06-29-751 We investigate whether certain non-classical communication channels can be simulated by a classical channel with a given number of states and a given `amount’ of noise. It is proved that […]
Quantum 6, 750 (2022). https://doi.org/10.22331/q-2022-06-29-750 We consider a collision between a moving particle and a fixed system, each having internal degrees of freedom. We identify the regime where the motion of the particle acts as […]
Quantum 6, 749 (2022). https://doi.org/10.22331/q-2022-06-29-749 We initiate the study of tradeoffs between exploration and exploitation in online learning of properties of quantum states. Given sequential oracle access to an unknown quantum state, in each round, […]
Quantum 6, 748 (2022). https://doi.org/10.22331/q-2022-06-29-748 We consider quantum systems with causal dynamics in discrete spacetimes, also known as quantum cellular automata (QCA). Due to time-discreteness this type of dynamics is not characterized by a Hamiltonian […]
Recent Comments