Abstract. We compute the three point correlation function for the eigenvalues of the Laplacian on quantum star graphs in the limit where the number of edges tends to infinity. This extends a work by Berkolaiko and Keating, where they get the 2-point correlation function and show that it follows neither Poisson, nor random matrix statistics. It makes use of the trace formula and combinatorial analysis. PACS numbers: 05.45.Mt,03.65.Sq Submitted to: J. Phys. A: Math. Gen. 1.

Jan 1, 20070 citations

Lecture notes in computer science

A Combinatorial Approach to Quantum Random Functions

Nico Döttling, Giulio Malavolta, Sihang Pu

Published Jan 1, 2020• 2 citations

Publisher

DOI: 10.1007/978-3-030-64834-3_21

Related papers

Combinatorial Optimization with Few Qubits

Rudy Raymond, Alexander Buts, Marco Pistoia

Despite the premise of quantum computing for Combinatorial Optimization (CO), near-term quantum computers still lack the physical resources, especially the number of qubits, to address problem instances of the same scale as their classical counterparts. Various methods to scale the problem instances addressable with few qubits have been popular and promising. In this paper, we introduce a method for CO utilizing few qubits. The method consists of applications of Quantum Random Access Code (QRAC) for encoding variables into qubits, Classical Shadow (CS) for decoding the variables, and Coordinate Descent (CD) for optimizing quantum circuits that generate desirable quantum states for the CO instances. We show that QRAC is useful to reveal the caveats of encoding more variables into few qubits and how to alleviate them. We also show that CS is effective to reduce quantum resources for decoding variables from the qubits. We then argue that CD methods are useful not only for optimizing parameters of quantum circuits encoding the solution of the CO instance, but also for explaining why utilizing activation function like tanh in the postprocessing of observing quantum states and in the objective function help achieve higher solution quality. We demonstrate the effectiveness of our proposed method by experiments on parameterized quantum circuits for solving instances of NP-hard graph partitioning task called minimum bisection.Despite the premise of quantum computing for Combinatorial Optimization (CO), near-term quantum computers still lack the physical resources, especially the number of qubits, to address problem instances of the same scale as their classical counterparts. Various methods to scale the problem instances addressable with few qubits have been popular and promising. In this paper, we introduce a method for CO utilizing few qubits. The method consists of applications of Quantum Random Access Code (QRAC) for encoding variables into qubits, Classical Shadow (CS) for decoding the variables, and Coordinate Descent (CD) for optimizing quantum circuits that generate desirable quantum states for the CO instances. We show that QRAC is useful to reveal the caveats of encoding more variables into few qubits and how to alleviate them. We also show that CS is effective to reduce quantum resources for decoding variables from the qubits. We then argue that CD methods are useful not only for optimizing parameters of quantum circuits encoding the solution of the CO instance, but also for explaining why utilizing activation function like tanh in the postprocessing of observing quantum states and in the objective function help achieve higher solution quality. We demonstrate the effectiveness of our proposed method by experiments on parameterized quantum circuits for solving instances of NP-hard graph partitioning task called minimum bisection.

IEEE International Conference on Quantum Computing and Engineering (QCE)Aug 30, 20250 citations

Monte Carlo to Las Vegas for Recursively Composed Functions

Bandar Al-Dhalaan, Shalev Ben-David

For a (possibly partial) Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ as well as a query complexity measure $M$ which maps Boolean functions to real numbers, define the composition limit of $M$ on $f$ by $M^*(f)=\lim_{k\to\infty} M(f^k)^{1/k}$ . We study the composition limits of general measures in query complexity. We show this limit converges under reasonable assumptions about the measure. We then give a surprising result regarding the composition limit of randomized query complexity: we show $R_0^*(f)=\max\{R^*(f),C^*(f)\}$ . Among other things, this implies that any bounded-error randomized algorithm for recursive 3-majority can be turned into a zero-error randomized algorithm for the same task. Our result extends also to quantum algorithms: on recursively composed functions, a bounded-error quantum algorithm can be converted into a quantum algorithm that finds a certificate with high probability. Along the way, we prove various combinatorial properties of measures and composition limits.For a (possibly partial) Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ as well as a query complexity measure $M$ which maps Boolean functions to real numbers, define the composition limit of $M$ on $f$ by $M^*(f)=\lim_{k\to\infty} M(f^k)^{1/k}$. We study the composition limits of general measures in query complexity. We show this limit converges under reasonable assumptions about the measure. We then give a surprising result regarding the composition limit of randomized query complexity: we show $R_0^*(f)=\max\{R^*(f),C^*(f)\}$. Among other things, this implies that any bounded-error randomized algorithm for recursive 3-majority can be turned into a zero-error randomized algorithm for the same task. Our result extends also to quantum algorithms: on recursively composed functions, a bounded-error quantum algorithm can be converted into a quantum algorithm that finds a certificate with high probability. Along the way, we prove various combinatorial properties of measures and composition limits.

cs.CCCross-listedarXiv:2601.08073Jan 14, 20260 citations

AN APPROACH TO QUANTUM PROBABILITY

Stanley Gudder

Foundations of probability and physicsDec 1, 200127 citations

Study of quantum random number generators

Patrik Mäki

May 15, 20210 citations

ON QUANTUM RANDOMNESS

WORLD SCIENTIFIC eBooksApr 1, 19980 citations

Three-point correlations for quantum star graphs

Marie-Line Chabanol

Jan 1, 20070 citations

For a (possibly partial) Boolean function

f\colon\{0,1\}^n\to\{0,1\}

as well as a query complexity measure

M

which maps Boolean functions to real numbers, define the composition limit of

M

f

M^*(f)=\lim_{k\to\infty} M(f^k)^{1/k}

. We study the composition limits of general measures in query complexity. We show this limit converges under reasonable assumptions about the measure. We then give a surprising result regarding the composition limit of randomized query complexity: we show

R_0^*(f)=\max\{R^*(f),C^*(f)\}

. Among other things, this implies that any bounded-error randomized algorithm for recursive 3-majority can be turned into a zero-error randomized algorithm for the same task. Our result extends also to quantum algorithms: on recursively composed functions, a bounded-error quantum algorithm can be converted into a quantum algorithm that finds a certificate with high probability. Along the way, we prove various combinatorial properties of measures and composition limits.