Random Sampling of Quantum States: a Survey of Methods

Niek J. Bouman, Serge Fehr

Feng, Wei Ming, Yin, Yi Tong

Sampling is a fundamental class of computational problems. The problem of generating random samples from a solution space according to certain probability distribution has numerous important applications in approximate counting, probability inference, statistical learning, etc. In the big data era, the distributed sampling attracts considerably more attentions. In recent years, there is a line of research works that systematically study the theory of distributed sampling. This study surveys important results on distributed sampling, including distributed sampling algorithms with theoretically provable guarantees, the computational complexity of sampling in the distributed computing model, and the mutual relation between sampling and inference in the distributed computing model.

Zhen Qin, Michael B. Wakin, Zhihui Zhu

Quantum state tomography (QST) is a fundamental task in quantum information science that aims to reconstruct unknown quantum states from measurement data. However, the exponential growth of Hilbert-space dimension with system size makes full tomography of general quantum states statistically and computationally prohibitive. This challenge has motivated extensive research on structured quantum state tomography, where prior structure, such as low-rankness, tensor-network representations, shallow quantum circuits, and neural quantum states, can substantially reduce the effective degrees of freedom and enable scalable recovery. In this review, we provide a unified perspective on QST for structured quantum states through three closely related themes: compact state representations, measurement design, and computational algorithms. After reviewing common models for structured quantum states, we survey existing work on geometric preservation properties of measurement frameworks, ranging from informationally complete POVMs to randomized measurements, and their implications for sample complexity. On the algorithmic side, we review optimization methods for reconstructing structured quantum states from empirical measurements. By connecting QST with broader principles from compressive sensing, matrix sensing, and structured inverse problems, this survey highlights common theoretical foundations underlying sample complexity, measurement efficiency, and scalable recovery.

Patrick M. Hayden, Debbie Leung, Peter W. Shor +1 more

Barbara Fresch, Giorgio J. Moro

Tayyaba Noreen, Muhammad Zeeshan Haider, Kaiwen Zhang +2 more

Blockchain technology has grown rapidly and gained extensive adoption across various sectors due to its transparency and security benefits. Randomness plays crucial role in blockchain systems by ensuring fairness, security, and unpredictability in decentralized systems. This survey comprehensively analyzes randomness generation methods, particularly Pseudo-Random Number Generators (PRNGs) and Quantum Random Number Generators (QRNGs), in blockchain systems. PRNGs, while efficient, are vulnerable to predictability issues, whereas QRNGs offer higher security but require specialized hardware and have higher costs. The paper examines state-of-the-art randomness generation techniques, highlighting their strengths, limitations, and implications for blockchain security and efficiency. A novel taxonomy is proposed, categorizing randomness approaches into on-chain and off-chain mechanisms using PRNGs and QRNGs. By providing an in-depth exploration of existing methods and advancements, this survey enables readers to evaluate trade-offs and identify the most suitable approaches for specific blockchain applications. The survey also addresses gaps in current research and proposes future directions for secure and efficient randomness generation in decentralized systems. To the best of our knowledge, this paper is the first survey that analyses randomness techniques in blockchain using PRNG and QRNG.