Quantum Sciences

  • Fractalizing quantum codes
    Quantum 5, 438 (2021). https://doi.org/10.22331/q-2021-04-22-438 We introduce "fractalization", a procedure by which spin models are extended to higher-dimensional "fractal" spin models. This allows us to interpret type-II fracton phases, fractal symmetry-protected topological phases, and more, in terms of well understood lower-dimensional spin models. Fractalization is also useful for deriving new spin models and quantum codes…
  • Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
    Quantum 5, 437 (2021). https://doi.org/10.22331/q-2021-04-20-437 The $p$-stage Quantum Approximate Optimization Algorithm (QAOA$_p$) is a promising approach for combinatorial optimization on noisy intermediate-scale quantum (NISQ) devices, but its theoretical behavior is not well understood beyond $p=1$. We analyze QAOA$_2$ for the $textit{maximum cut problem}$ (MAX-CUT), deriving a graph-size-independent expression for the expected cut fraction on any…
  • Lightweight Detection of a Small Number of Large Errors in a Quantum Circuit
    Quantum 5, 436 (2021). https://doi.org/10.22331/q-2021-04-20-436 Suppose we want to implement a unitary $U$, for instance a circuit for some quantum algorithm. Suppose our actual implementation is a unitary $tilde{U}$, which we can only apply as a black-box. In general it is an exponentially-hard task to decide whether $tilde{U}$ equals the intended $U$, or is significantly…
  • Resource theories of multi-time processes: A window into quantum non-Markovianity
    Quantum 5, 435 (2021). https://doi.org/10.22331/q-2021-04-20-435 We investigate the conditions under which an uncontrollable background processes may be harnessed by an agent to perform a task that would otherwise be impossible within their operational framework. This situation can be understood from the perspective of resource theory: rather than harnessing 'useful' quantum states to perform tasks, we…
  • Expressibility of the alternating layered ansatz for quantum computation
    Quantum 5, 434 (2021). https://doi.org/10.22331/q-2021-04-19-434 The hybrid quantum-classical algorithm is actively examined as a technique applicable even to intermediate-scale quantum computers. To execute this algorithm, the hardware efficient ansatz is often used, thanks to its implementability and expressibility; however, this ansatz has a critical issue in its trainability in the sense that it generically suffers…
  • How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
    Quantum 5, 433 (2021). https://doi.org/10.22331/q-2021-04-15-433 We significantly reduce the cost of factoring integers and computing discrete logarithms in finite fields on a quantum computer by combining techniques from Shor 1994, Griffiths-Niu 1996, Zalka 2006, Fowler 2012, Ekerå-Håstad 2017, Ekerå 2017, Ekerå 2018, Gidney-Fowler 2019, Gidney 2019. We estimate the approximate cost of our construction using…
  • Combining hard and soft decoders for hypergraph product codes
    Quantum 5, 432 (2021). https://doi.org/10.22331/q-2021-04-15-432 Hypergraph product codes are a class of constant-rate quantum low-density parity-check (LDPC) codes equipped with a linear-time decoder called small-set-flip (SSF). This decoder displays sub-optimal performance in practice and requires very large error correcting codes to be effective. In this work, we present new hybrid decoders that combine the belief…
  • Quantum-inspired algorithms for multivariate analysis: from interpolation to partial differential equations
    Quantum 5, 431 (2021). https://doi.org/10.22331/q-2021-04-15-431 In this work we study the encoding of smooth, differentiable multivariate functions in quantum registers, using quantum computers or tensor-network representations. We show that a large family of distributions can be encoded as low-entanglement states of the quantum register. These states can be efficiently created in a quantum computer, but…
  • Experimentally friendly approach towards nonlocal correlations in multisetting N-partite Bell scenarios
    Quantum 5, 430 (2021). https://doi.org/10.22331/q-2021-04-14-430 In this work, we study a recently proposed operational measure of nonlocality by Fonseca and Parisio [Phys. Rev. A 92, 030101(R) (2015)] which describes the probability of violation of local realism under randomly sampled observables, and the strength of such violation as described by resistance to white noise admixture. While…
  • Towards Quantum One-Time Memories from Stateless Hardware
    Quantum 5, 429 (2021). https://doi.org/10.22331/q-2021-04-08-429 A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which…
  • Grover Adaptive Search for Constrained Polynomial Binary Optimization
    Quantum 5, 428 (2021). https://doi.org/10.22331/q-2021-04-08-428 In this paper we discuss Grover Adaptive Search (GAS) for Constrained Polynomial Binary Optimization (CPBO) problems, and in particular, Quadratic Unconstrained Binary Optimization (QUBO) problems, as a special case. GAS can provide a quadratic speed-up for combinatorial optimization problems compared to brute force search. However, this requires the development of…
  • Quantum algorithms for Second-Order Cone Programming and Support Vector Machines
    Quantum 5, 427 (2021). https://doi.org/10.22331/q-2021-04-08-427 We present a quantum interior-point method (IPM) for second-order cone programming (SOCP) that runs in time $widetilde{O} left( nsqrt{r} frac{zeta kappa}{delta^2} log left(1/epsilonright) right)$ where $r$ is the rank and $n$ the dimension of the SOCP, $delta$ bounds the distance of intermediate solutions from the cone boundary, $zeta$ is a…
  • Quantum Algorithm for Simulating Hamiltonian Dynamics with an Off-diagonal Series Expansion
    Quantum 5, 426 (2021). https://doi.org/10.22331/q-2021-04-08-426 We propose an efficient quantum algorithm for simulating the dynamics of general Hamiltonian systems. Our technique is based on a power series expansion of the time-evolution operator in its off-diagonal terms. The expansion decouples the dynamics due to the diagonal component of the Hamiltonian from the dynamics generated by its…
  • Multiple-shot and unambiguous discrimination of von Neumann measurements
    Quantum 5, 425 (2021). https://doi.org/10.22331/q-2021-04-06-425 We present an in-depth study of the problem of multiple-shot discrimination of von Neumann measurements in finite-dimensional Hilbert spaces. Specifically, we consider two scenarios: minimum error and unambiguous discrimination. In the case of minimum error discrimination, we focus on discrimination of measurements with the assistance of entanglement. We provide an…
  • A universal scheme for robust self-testing in the prepare-and-measure scenario
    Quantum 5, 424 (2021). https://doi.org/10.22331/q-2021-04-06-424 We consider the problem of certification of arbitrary ensembles of pure states and projective measurements solely from the experimental statistics in the prepare-and-measure scenario assuming the upper bound on the dimension of the Hilbert space. To this aim, we propose a universal and intuitive scheme based on establishing perfect correlations…
  • Distinguishing noisy boson sampling from classical simulations
    Quantum 5, 423 (2021). https://doi.org/10.22331/q-2021-03-29-423 Giving a convincing experimental evidence of the quantum supremacy over classical simulations is a challenging goal. Noise is considered to be the main problem in such a demonstration, hence it is urgent to understand the effect of noise. Recently found classical algorithms can efficiently approximate, to any small error, the…
  • Dimensional Expressivity Analysis of Parametric Quantum Circuits
    Quantum 5, 422 (2021). https://doi.org/10.22331/q-2021-03-29-422 Parametric quantum circuits play a crucial role in the performance of many variational quantum algorithms. To successfully implement such algorithms, one must design efficient quantum circuits that sufficiently approximate the solution space while maintaining a low parameter count and circuit depth. In this paper, develop a method to analyze the…
  • There and back again: A circuit extraction tale
    Quantum 5, 421 (2021). https://doi.org/10.22331/q-2021-03-25-421 Translations between the quantum circuit model and the measurement-based one-way model are useful for verification and optimisation of quantum computations. They make crucial use of a property known as gflow. While gflow is defined for one-way computations allowing measurements in three different planes of the Bloch sphere, most research so…
  • Nonlinear extension of the quantum dynamical semigroup
    Quantum 5, 420 (2021). https://doi.org/10.22331/q-2021-03-23-420 In this paper we consider deterministic nonlinear time evolutions satisfying so called convex quasi-linearity condition. Such evolutions preserve the equivalence of ensembles and therefore are free from problems with signaling. We show that if family of linear non-trace-preserving maps satisfies the semigroup property then the generated family of convex quasi-linear…
  • Postquantum common-cause channels: the resource theory of local operations and shared entanglement
    Quantum 5, 419 (2021). https://doi.org/10.22331/q-2021-03-23-419 We define the type-independent resource theory of local operations and shared entanglement (LOSE). This allows us to formally quantify postquantumness in common-cause scenarios such as the Bell scenario. Any nonsignaling bipartite quantum channel which cannot be generated by LOSE operations requires a $textit{postquantum common cause}$ to generate, and constitutes a…
  • Device-independent certification of tensor products of quantum states using single-copy self-testing protocols
    Quantum 5, 418 (2021). https://doi.org/10.22331/q-2021-03-23-418 Self-testing protocols are methods to determine the presence of shared entangled states in a device independent scenario, where no assumptions on the measurements involved in the protocol are made. A particular type of self-testing protocol, called parallel self-testing, can certify the presence of copies of a state, however such protocols…
  • On the Quantum versus Classical Learnability of Discrete Distributions
    Quantum 5, 417 (2021). https://doi.org/10.22331/q-2021-03-23-417 Here we study the comparative power of classical and quantum learners for generative modelling within the Probably Approximately Correct (PAC) framework. More specifically we consider the following task: Given samples from some unknown discrete probability distribution, output with high probability an efficient algorithm for generating new samples from a good…
  • Entangled resource for interfacing single- and dual-rail optical qubits
    Quantum 5, 416 (2021). https://doi.org/10.22331/q-2021-03-23-416 Today's most widely used method of encoding quantum information in optical qubits is the dual-rail basis, often carried out through the polarisation of a single photon. On the other hand, many stationary carriers of quantum information – such as atoms – couple to light via the single-rail encoding in which…
  • Application-Motivated, Holistic Benchmarking of a Full Quantum Computing Stack
    Quantum 5, 415 (2021). https://doi.org/10.22331/q-2021-03-22-415 Quantum computing systems need to be benchmarked in terms of practical tasks they would be expected to do. Here, we propose 3 "application-motivated" circuit classes for benchmarking: deep (relevant for state preparation in the variational quantum eigensolver algorithm), shallow (inspired by IQP-type circuits that might be useful for near-term quantum…
  • Complete Information Balance in Quantum Measurement
    Quantum 5, 414 (2021). https://doi.org/10.22331/q-2021-03-17-414 Quantum measurement is a basic tool to manifest intrinsic quantum effects from fundamental tests to quantum information applications. While a measurement is typically performed to gain information on a quantum state, its role in quantum technology is indeed manifold. For instance, quantum measurement is a crucial process element in measurement-based…