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:2609.38986

Quantum Pseudorandom Error-Correcting Codes

Min-Hsiu Hsieh, Shogo Yamada

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

Pseudorandom error-correcting codes (PRCs), introduced by Christ and Gunn [CRYPTO 2024], are classical error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings. We initiate the study of quantum analogues of PRCs. We define quantum pseudorandom error-correcting codes (QPRCs). Assuming that Learning Parity with Noise (LPN) is hard for $2^{O(\sqrt{n})}$-time quantum algorithms, we construct QPRCs whose encodings are indistinguishable from Haar-random isometries. We call these pseudorandom isometric error-correcting codes (PRICs), and our construction is robust to all $o(n \frac{\log \log n}{\log n})$-local quantum noise, where $n$ is the number of physical qubits. Under the same assumption, we also construct QPRCs whose encodings are indistinguishable from the completely depolarizing channel and that are robust to all $αn$-local quantum noise for some constant $α>0$. The latter QPRCs give a direct quantum analogue of classical PRCs. To construct PRICs, we develop two technical ingredients of independent interest. First, we introduce a new classical cryptographic primitive which we call pseudorandom functional error-correcting codes (PRFCs) and construct them under the same LPN assumption. Second, we develop a new efficient decoding procedure within the codeword-stabilized (CWS) framework introduced in [Cross, Smith, Smolin, and Zeng, IEEE ISIT 2008], which is a generic framework for constructing quantum error-correcting codes by combining (possibly nonlinear) classical error-correcting codes and graphs. This resolves the open problem of finding a general method for efficiently decoding such CWS codes based on nonlinear classical codes, raised in [Li, Dumer, Grassl, and Pryadko, Physical Review A 2010].

AI Summary

Can efficient quantum error correction coexist with encodings that look computationally random, even under coherent oracle queries? This paper defines quantum pseudorandom error-correcting codes (QPRCs) and constructs two variants, assuming LPN is hard for $2^{O(\sqrt n)}$-time quantum algorithms, with $n$ denoting the LPN secret length. Pseudorandom isometric codes (PRICs) have encodings indistinguishable from a fixed Haar-random isometry. They achieve constant encoding rate and correct arbitrary $t$-local quantum noise for every $t=o(N\log\log N/\log N)$, where $N$ is the physical-qubit count. A second, public-key construction has encodings indistinguishable from the completely depolarizing channel and corrects $\alpha N$-local noise for some constant $\alpha>0$, also at constant rate. It combines an ordinary QECC with a quantum one-time pad whose keys are protected by classical pseudorandom codes. The PRIC construction introduces pseudorandom functional codes: deterministic classical encoders that are quantum-query-secure pseudorandom functions and permit decoding after a constant fraction of bit flips. These yield isometries correcting bit errors. A codeword-stabilized graph layer extends recovery to phase errors through an efficient randomized-graph decoding procedure. This also gives a black-box, keyed quantum-code construction from efficiently decodable nonlinear classical codes. Recovery guarantees concern the key-averaged channel in diamond distance and key-independent noise, not adaptive attacks informed by encoding queries. The CWS decoding result is correspondingly keyed rather than a decoder for arbitrary CWS codes. Linear-error robustness for PRICs remains open, as do stronger adaptive robustness notions and quantum watermarking, steganography, or chaotic-system applications.

Some signs of AI-generated textAI use disclosedStrong assumptions
Codex and Claude Code assisted with drafting and editing the manuscript.

Error found: The abstract overstates the CWS decoding result: the paper proves efficient decoding for a specially sampled keyed construction against key-independent noise, averaged over the key, rather than a general efficient decoder for arbitrary CWS codes.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
73 pages, 2 figures

Related papers

Codeword Stabilized Quantum Codes and Their Error Correction

Yunfan Li

Quantum decoherence and errors represent some of the major challenges arising in quantum computations. Quantum error correcting codes protect quantum states against these errors and make quantum computing more reliable. One of the main problems of quantum error correction is the design of feasible decoding algorithms that can simplify error-correction for general quantum codes. The dissertation addresses decoding of general Codeword Stabilized (CWS) codes. This class of quantum codes also includes some other important classes such as additive Stabilizer codes and non-additive Union Stabilizer (USt) codes.We first design a generic error-correcting algorithm for CWS codes and analyze the number of decoding measurements and quantum gates. This algorithm performs exhaustive screening of different error patterns, similar to decoding of classical non-linear codes. For an n-qubit quantum code correcting up to t erroneous qubits, this brute-force approach consecutively tests all correctable error patterns and employs a separate n-qubit measurement in each test.The main result is a new error grouping technique that enables simultaneous testing of large groups of errors in a single measurement. To achieve this reduction, we first proceed with a new error-correction algorithm for the USt codes. Secondly, we design an algorithm that converts generic non-linear CWS codes into the simpler quasi-linear USt codes. Each decoding measurement can then either locate the actual error in a given group of errors or entirely eliminate this group. This technique yields a much simpler algorithm that exponentially reduces the number of measurements about 3^t times in any t-error-correcting CWS code.

•Jan 1, 2010•0 citations

Heuristics in quantum error correction

Alex Rigby

Noise is a major obstacle in the development of practical schemes for quantum computation and communication. Similar to the case of classical communication, this noise can be protected against by employing a code, which provides a means for encoding quantum states prior to transmission and allows for errors to be inferred, and hopefully corrected, by a decoder at the receiver. Unfortunately, designing good codes and decoders is typically a difficult problem. This thesis focuses on developing low-complexity heuristic approaches to three such problems: the design of modified belief propagation decoders for quantum low-density parity-check codes, the design of stabilizer codes for asymmetric channels, and the design of codeword stabilized codes. Quantum low-density parity-check codes are stabilizer codes with low-weight generators. Such codes permit low-complexity decoding via the use of belief propagation, which is an iterative message passing algorithm that takes place on a factor graph defined by the code. However, the performance of such a decoder is limited both by code structure and the degenerate nature of quantum errors. To overcome these limitations, at least in part, a number of modifications to belief propagation are developed. Central among these is the augmented decoder, which in the case of a decoding error, iteratively reattempts decoding using modified factor graph. This heuristic modification simply involves the duplication of a randomly selected subset of the graph’s check nodes, which are in one-to-one correspondence with the code’s stabilizer generators. Across a range of codes, it is shown that the decoders developed perform as well as or better than other modified decoders presented in literature. For a number of channels of physical interest, phase-flip errors occur far more frequently than bit-flip errors. When transmitting across these so-called asymmetric channels, the decoding error rate can be minimized by tailoring the code used to the channel. However, assessing the performance of codes on a given channel is made difficult by the #P-completeness of optimal decoding. To address this complexity, it is shown that the decoding error rate can be accurately approximated using only a small fraction of the possible errors caused by the channel. This approximation is then used to identify a number of cyclic stabilizer codes that perform well on two different asymmetric channels. To further build on this, a heuristic is demonstrated for assessing code performance based on the decoding error rate of an associated classical code. The complexity of calculating this classical error rate is relatively low, and it is shown that it can be used as the basis for a hill-climbing search algorithm. Such searches have yielded a large number of highly performant codes satisfying various structure constraints. The family of codeword stabilized codes encompasses both the stabilizer codes as well as many of the best known nonadditive codes. Constructing a standard form codeword stabilized code is a matter of selecting a simple undirected graph and a binary classical code. This makes designing optimal codes difficult as the number of possible graphs grows exponentially with code length, and the clique search required to construct the classical code is NP-hard. To address the exponential growth of the search space, a heuristic is developed for assessing graphs. This heuristic is then employed by a genetic algorithm that also makes use of a novel crossover operation based on spectral bisection, which is show to be superior to more standard crossover operations. With a graph selected, it is demonstrated that the complexity of the clique search required to construct the associated classical code can be mitigated through the use of a heuristic clique finding algorithm. A number of best known codes are presented that have been found using this approach.

•Jan 1, 2021•0 citations

Quantum stabilizer codes and beyond

Sarvepalli, Pradeep Kiran

The importance of quantum error correction in paving the way to build a practical quantum computer is no longer in doubt. This dissertation makes a threefold contribution to the mathematical theory of quantum error-correcting codes. Firstly, it extends the framework of an important class of quantum codes -- nonbinary stabilizer codes. It clarifies the connections of stabilizer codes to classical codes over quadratic extension fields, provides many new constructions of quantum codes, and develops further the theory of optimal quantum codes and punctured quantum codes. Secondly, it contributes to the theory of operator quantum error correcting codes also called as subsystem codes. These codes are expected to have efficient error recovery schemes than stabilizer codes. This dissertation develops a framework for study and analysis of subsystem codes using character theoretic methods. In particular, this work establishes a close link between subsystem codes and classical codes showing that the subsystem codes can be constructed from arbitrary classical codes. Thirdly, it seeks to exploit the knowledge of noise to design efficient quantum codes and considers more realistic channels than the commonly studied depolarizing channel. It gives systematic constructions of asymmetric quantum stabilizer codes that exploit the asymmetry of errors in certain quantum channels.

arXiv:0810.2574•Oct 14, 2008•9 citations

Nonbinary codeword-stabilized quantum codes

Xie Chen, Bei Zeng, Isaac L. Chuang

The codeword-stabilized (CWS) quantum code formalism presents a unifying approach to both additive and nonadditive quantum error-correcting codes [see A. Cross et al., e-print arXiv:0708.1021], but only for binary states. Here we generalize the CWS framework to the nonbinary case (of both prime and nonprime dimensions) and map the search for nonbinary quantum codes to a corresponding search problem for classical nonbinary codes with specific error patterns. We show that while the additivity properties of nonbinary CWS codes are similar to the binary case, the structural properties of the nonbinary codes differ substantially from the binary case, even for prime dimensions. In particular, we identify specific structure patterns of stabilizer groups, based on which efficient constructions might be possible for codes that encode more dimensions than any stabilizer codes of the same length and distance; similar methods cannot be applied in the binary case. Understanding of these structural properties can help prune the search space and facilitate the identification of good nonbinary CWS codes.

arXiv:0808.3086•Physical Review A•Dec 8, 2008•31 citations

Quantum Error Correction Via Noise Guessing Decoding

Diogo Cruz, Francisco A. Monteiro, Bruno Coelho Coutinho

Quantum error correction codes (QECCs) play a central role in both quantum communications and quantum computation. Practical quantum error correction codes, such as stabilizer codes, are generally structured to suit a specific use, and present rigid code lengths and code rates. This paper shows that it is possible to both construct and decode QECCs that can attain the maximum performance of the finite blocklength regime, for any chosen code length when the code rate is sufficiently high. A recently proposed strategy for decoding classical codes called GRAND (guessing random additive noise decoding) opened doors to efficiently decode classical random linear codes (RLCs) performing near the maximum rate of the finite blocklength regime. By using noise statistics, GRAND is a noise-centric efficient universal decoder for classical codes, provided that a simple code membership test exists. These conditions are particularly suitable for quantum systems, and therefore the paper extends these concepts to quantum random linear codes (QRLCs), which were known to be possible to construct but whose decoding was not yet feasible. By combining QRLCs and a newly proposed quantum-GRAND, this work shows it is possible to decode QECCs that are easy to adapt to changing conditions. The paper starts by assessing the minimum number of gates in the coding circuit needed to reach the QRLCs’ asymptotic performance, and subsequently proposes a quantum-GRAND algorithm that makes use of quantum noise statistics, not only to build an adaptive code membership test, but also to efficiently implement syndrome decoding.

arXiv:2208.02744•IEEE Access•Jan 1, 2023•25 citations

Pseudorandom quantum authentication

Tobias Haug, Nikhil Bansal, Wai‐Keong Mok +2 more

We introduce the pseudorandom quantum authentication scheme (PQAS), an efficient method for encrypting quantum states that relies solely on the existence of pseudorandom unitaries (PRUs). The scheme guarantees that for any eavesdropper with quantum polynomial-time (QPT) computational power, the encrypted states are indistinguishable from the maximally mixed state. Furthermore, the receiver can verify that the state has not been tampered with and recover the original state with asymptotically unit fidelity. Our scheme is cost-effective, requiring only polylogarithmic circuit depth and a single shared key to encrypt a polynomial number of states. Notably, the PQAS can potentially exist even without quantum-secure one-way functions, requiring fundamentally weaker computational assumptions than semantic classical cryptography. Additionally, PQAS is secure against attacks that plague protocols based on QPT indistinguishability from Haar random states, such as chosen-plaintext attacks (CPAs) and attacks that reveal meta-information such as quantum resources. We relate the amount of meta-information that is leaked to quantum pseudoresources, giving the concept a practical meaning. As an application, we construct important cryptographic primitives, such as verifiable pseudorandom density matrices (VPRDMs), which are QPT-indistinguishable from random mixed states while being efficiently verifiable via a secret key, as well as verifiable noise-robust EFI pairs and one-way state generators (OWSGs). Our results establish a new paradigm of quantum information processing with weaker computational assumptions.

arXiv:2501.00951•Jan 1, 2025•5 citations
Pseudorandom error-correcting codes (PRCs), introduced by Christ and Gunn [CRYPTO 2024], are classical error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings. We initiate the study of quantum analogues of PRCs. We define quantum pseudorandom error-correcting codes (QPRCs). Assuming that Learning Parity with Noise (LPN) is hard for 2O(n)2^{O(\sqrt{n})}2O(n​)-time quantum algorithms, we construct QPRCs whose encodings are indistinguishable from Haar-random isometries. We call these pseudorandom isometric error-correcting codes (PRICs), and our construction is robust to all o(nlog⁡log⁡nlog⁡n)o(n \frac{\log \log n}{\log n})o(nlognloglogn​)-local quantum noise, where nnn is the number of physical qubits. Under the same assumption, we also construct QPRCs whose encodings are indistinguishable from the completely depolarizing channel and that are robust to all αnαnαn-local quantum noise for some constant α>0α>0α>0. The latter QPRCs give a direct quantum analogue of classical PRCs.
To construct PRICs, we develop two technical ingredients of independent interest. First, we introduce a new classical cryptographic primitive which we call pseudorandom functional error-correcting codes (PRFCs) and construct them under the same LPN assumption. Second, we develop a new efficient decoding procedure within the codeword-stabilized (CWS) framework introduced in [Cross, Smith, Smolin, and Zeng, IEEE ISIT 2008], which is a generic framework for constructing quantum error-correcting codes by combining (possibly nonlinear) classical error-correcting codes and graphs. This resolves the open problem of finding a general method for efficiently decoding such CWS codes based on nonlinear classical codes, raised in [Li, Dumer, Grassl, and Pryadko, Physical Review A 2010].
Can efficient quantum error correction coexist with encodings that look computationally random, even under coherent oracle queries? This paper defines quantum pseudorandom error-correcting codes (QPRCs) and constructs two variants, assuming LPN is hard for 2O(n)2^{O(\sqrt n)}2O(n​)-time quantum algorithms, with nnn denoting the LPN secret length.
Pseudorandom isometric codes (PRICs) have encodings indistinguishable from a fixed Haar-random isometry. They achieve constant encoding rate and correct arbitrary ttt-local quantum noise for every t=o(Nlog⁡log⁡N/log⁡N)t=o(N\log\log N/\log N)t=o(NloglogN/logN), where NNN is the physical-qubit count. A second, public-key construction has encodings indistinguishable from the completely depolarizing channel and corrects αN\alpha NαN-local noise for some constant α>0\alpha>0α>0, also at constant rate. It combines an ordinary QECC with a quantum one-time pad whose keys are protected by classical pseudorandom codes.
The PRIC construction introduces pseudorandom functional codes: deterministic classical encoders that are quantum-query-secure pseudorandom functions and permit decoding after a constant fraction of bit flips. These yield isometries correcting bit errors. A codeword-stabilized graph layer extends recovery to phase errors through an efficient randomized-graph decoding procedure. This also gives a black-box, keyed quantum-code construction from efficiently decodable nonlinear classical codes.
Recovery guarantees concern the key-averaged channel in diamond distance and key-independent noise, not adaptive attacks informed by encoding queries. The CWS decoding result is correspondingly keyed rather than a decoder for arbitrary CWS codes. Linear-error robustness for PRICs remains open, as do stronger adaptive robustness notions and quantum watermarking, steganography, or chaotic-system applications.
Quantum decoherence and errors represent some of the major challenges arising in quantum computations. Quantum error correcting codes protect quantum states against these errors and make quantum computing more reliable. One of the main problems of quantum error correction is the design of feasible decoding algorithms that can simplify error-correction for general quantum codes. The dissertation addresses decoding of general Codeword Stabilized (CWS) codes. This class of quantum codes also includes some other important classes such as additive Stabilizer codes and non-additive Union Stabilizer (USt) codes.We first design a generic error-correcting algorithm for CWS codes and analyze the number of decoding measurements and quantum gates. This algorithm performs exhaustive screening of different error patterns, similar to decoding of classical non-linear codes. For an n-qubit quantum code correcting up to t erroneous qubits, this brute-force approach consecutively tests all correctable error patterns and employs a separate n-qubit measurement in each test.The main result is a new error grouping technique that enables simultaneous testing of large groups of errors in a single measurement. To achieve this reduction, we first proceed with a new error-correction algorithm for the USt codes. Secondly, we design an algorithm that converts generic non-linear CWS codes into the simpler quasi-linear USt codes. Each decoding measurement can then either locate the actual error in a given group of errors or entirely eliminate this group. This technique yields a much simpler algorithm that exponentially reduces the number of measurements about 3^t times in any t-error-correcting CWS code.
Noise is a major obstacle in the development of practical schemes for quantum computation and communication. Similar to the case of classical communication, this noise can be protected against by employing a code, which provides a means for encoding quantum states prior to transmission and allows for errors to be inferred, and hopefully corrected, by a decoder at the receiver. Unfortunately, designing good codes and decoders is typically a difficult problem. This thesis focuses on developing low-complexity heuristic approaches to three such problems: the design of modified belief propagation decoders for quantum low-density parity-check codes, the design of stabilizer codes for asymmetric channels, and the design of codeword stabilized codes. Quantum low-density parity-check codes are stabilizer codes with low-weight generators. Such codes permit low-complexity decoding via the use of belief propagation, which is an iterative message passing algorithm that takes place on a factor graph defined by the code. However, the performance of such a decoder is limited both by code structure and the degenerate nature of quantum errors. To overcome these limitations, at least in part, a number of modifications to belief propagation are developed. Central among these is the augmented decoder, which in the case of a decoding error, iteratively reattempts decoding using modified factor graph. This heuristic modification simply involves the duplication of a randomly selected subset of the graph’s check nodes, which are in one-to-one correspondence with the code’s stabilizer generators. Across a range of codes, it is shown that the decoders developed perform as well as or better than other modified decoders presented in literature. For a number of channels of physical interest, phase-flip errors occur far more frequently than bit-flip errors. When transmitting across these so-called asymmetric channels, the decoding error rate can be minimized by tailoring the code used to the channel. However, assessing the performance of codes on a given channel is made difficult by the #P-completeness of optimal decoding. To address this complexity, it is shown that the decoding error rate can be accurately approximated using only a small fraction of the possible errors caused by the channel. This approximation is then used to identify a number of cyclic stabilizer codes that perform well on two different asymmetric channels. To further build on this, a heuristic is demonstrated for assessing code performance based on the decoding error rate of an associated classical code. The complexity of calculating this classical error rate is relatively low, and it is shown that it can be used as the basis for a hill-climbing search algorithm. Such searches have yielded a large number of highly performant codes satisfying various structure constraints. The family of codeword stabilized codes encompasses both the stabilizer codes as well as many of the best known nonadditive codes. Constructing a standard form codeword stabilized code is a matter of selecting a simple undirected graph and a binary classical code. This makes designing optimal codes difficult as the number of possible graphs grows exponentially with code length, and the clique search required to construct the classical code is NP-hard. To address the exponential growth of the search space, a heuristic is developed for assessing graphs. This heuristic is then employed by a genetic algorithm that also makes use of a novel crossover operation based on spectral bisection, which is show to be superior to more standard crossover operations. With a graph selected, it is demonstrated that the complexity of the clique search required to construct the associated classical code can be mitigated through the use of a heuristic clique finding algorithm. A number of best known codes are presented that have been found using this approach.
The importance of quantum error correction in paving the way to build a practical quantum computer is no longer in doubt. This dissertation makes a threefold contribution to the mathematical theory of quantum error-correcting codes. Firstly, it extends the framework of an important class of quantum codes -- nonbinary stabilizer codes. It clarifies the connections of stabilizer codes to classical codes over quadratic extension fields, provides many new constructions of quantum codes, and develops further the theory of optimal quantum codes and punctured quantum codes. Secondly, it contributes to the theory of operator quantum error correcting codes also called as subsystem codes. These codes are expected to have efficient error recovery schemes than stabilizer codes. This dissertation develops a framework for study and analysis of subsystem codes using character theoretic methods. In particular, this work establishes a close link between subsystem codes and classical codes showing that the subsystem codes can be constructed from arbitrary classical codes. Thirdly, it seeks to exploit the knowledge of noise to design efficient quantum codes and considers more realistic channels than the commonly studied depolarizing channel. It gives systematic constructions of asymmetric quantum stabilizer codes that exploit the asymmetry of errors in certain quantum channels.
The codeword-stabilized (CWS) quantum code formalism presents a unifying approach to both additive and nonadditive quantum error-correcting codes [see A. Cross et al., e-print arXiv:0708.1021], but only for binary states. Here we generalize the CWS framework to the nonbinary case (of both prime and nonprime dimensions) and map the search for nonbinary quantum codes to a corresponding search problem for classical nonbinary codes with specific error patterns. We show that while the additivity properties of nonbinary CWS codes are similar to the binary case, the structural properties of the nonbinary codes differ substantially from the binary case, even for prime dimensions. In particular, we identify specific structure patterns of stabilizer groups, based on which efficient constructions might be possible for codes that encode more dimensions than any stabilizer codes of the same length and distance; similar methods cannot be applied in the binary case. Understanding of these structural properties can help prune the search space and facilitate the identification of good nonbinary CWS codes.
Quantum error correction codes (QECCs) play a central role in both quantum communications and quantum computation. Practical quantum error correction codes, such as stabilizer codes, are generally structured to suit a specific use, and present rigid code lengths and code rates. This paper shows that it is possible to both construct and decode QECCs that can attain the maximum performance of the finite blocklength regime, for any chosen code length when the code rate is sufficiently high. A recently proposed strategy for decoding classical codes called GRAND (guessing random additive noise decoding) opened doors to efficiently decode classical random linear codes (RLCs) performing near the maximum rate of the finite blocklength regime. By using noise statistics, GRAND is a noise-centric efficient universal decoder for classical codes, provided that a simple code membership test exists. These conditions are particularly suitable for quantum systems, and therefore the paper extends these concepts to quantum random linear codes (QRLCs), which were known to be possible to construct but whose decoding was not yet feasible. By combining QRLCs and a newly proposed quantum-GRAND, this work shows it is possible to decode QECCs that are easy to adapt to changing conditions. The paper starts by assessing the minimum number of gates in the coding circuit needed to reach the QRLCs’ asymptotic performance, and subsequently proposes a quantum-GRAND algorithm that makes use of quantum noise statistics, not only to build an adaptive code membership test, but also to efficiently implement syndrome decoding.
We introduce the pseudorandom quantum authentication scheme (PQAS), an efficient method for encrypting quantum states that relies solely on the existence of pseudorandom unitaries (PRUs). The scheme guarantees that for any eavesdropper with quantum polynomial-time (QPT) computational power, the encrypted states are indistinguishable from the maximally mixed state. Furthermore, the receiver can verify that the state has not been tampered with and recover the original state with asymptotically unit fidelity. Our scheme is cost-effective, requiring only polylogarithmic circuit depth and a single shared key to encrypt a polynomial number of states. Notably, the PQAS can potentially exist even without quantum-secure one-way functions, requiring fundamentally weaker computational assumptions than semantic classical cryptography. Additionally, PQAS is secure against attacks that plague protocols based on QPT indistinguishability from Haar random states, such as chosen-plaintext attacks (CPAs) and attacks that reveal meta-information such as quantum resources. We relate the amount of meta-information that is leaked to quantum pseudoresources, giving the concept a practical meaning. As an application, we construct important cryptographic primitives, such as verifiable pseudorandom density matrices (VPRDMs), which are QPT-indistinguishable from random mixed states while being efficiently verifiable via a secret key, as well as verifiable noise-robust EFI pairs and one-way state generators (OWSGs). Our results establish a new paradigm of quantum information processing with weaker computational assumptions.