Tradeoff Constructions for Quantum Locally Testable Codes

• URL: http://arxiv.org/abs/2309.05541v3
• Date: Tue, 23 Jan 2024 07:03:46 GMT
• Title: Tradeoff Constructions for Quantum Locally Testable Codes
• Authors: Adam Wills, Ting-Chun Lin, Min-Hsiu Hsieh
• Abstract summary: We present three constructions that can make new quantum locally testable codes (qLTCs) from old. These constructions can be used on as-yet undiscovered qLTCs to obtain new parameters. We find a number of present applications to prove the existence of codes in previously unknown parameter regimes.
• Score: 11.640839589988788
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we continue the search for quantum locally testable codes (qLTCs) of new parameters by presenting three constructions that can make new qLTCs from old. The first analyses the soundness of a quantum code under Hastings' weight reduction construction for qLDPC codes arXiv:2102.10030 to give a weight reduction procedure for qLTCs. Secondly, we describe a novel `soundness amplification' procedure for qLTCs which can increase the soundness of any qLTC to a constant while preserving its distance and dimension, with an impact only felt on its locality. Finally, we apply the AEL distance amplification construction to the case of qLTCs for the first time which can turn a high-distance qLTC into one with linear distance, at the expense of other parameters. These constructions can be used on as-yet undiscovered qLTCs to obtain new parameters, but we also find a number of present applications to prove the existence of codes in previously unknown parameter regimes. In particular, applications of these operations to the hypersphere product code arXiv:1608.05089 and the hemicubic code arXiv:1911.03069 yield many previously unknown parameters. Additionally, soundness amplification can be used to produce the first asymptotically good testable quantum code (rather than locally testable) - that being one with linear distance and dimension, as well as constant soundness. Lastly, applications of all three results are described to an upcoming work.

Related papers

• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Quantum Locally Recoverable Codes [27.438045041448248]
  In the long term, like their classical counterparts, quantum locally recoverable codes may be used for large-scale quantum data storage. We show that even the weakest form of a stronger locality property called local correctability, which permits more robust local recovery, is impossible quantumly.
  arXiv  Detail & Related papers  (2023-11-15T02:27:01Z)
• How to harness high-dimensional temporal entanglement, using limited interferometry setups [62.997667081978825]
  We develop the first complete analysis of high-dimensional entanglement in the polarization-time-domain. We show how to efficiently certify relevant density matrix elements and security parameters for Quantum Key Distribution. We propose a novel setup that can further enhance the noise resistance of free-space quantum communication.
  arXiv  Detail & Related papers  (2023-08-08T17:44:43Z)
• Robust sparse IQP sampling in constant depth [3.670008893193884]
  NISQ (noisy intermediate scale quantum) approaches without any proof of robust quantum advantage and fully fault-tolerant quantum computation. We propose a scheme to achieve a provable superpolynomial quantum advantage that is robust to noise with minimal error correction requirements.
  arXiv  Detail & Related papers  (2023-07-20T09:41:08Z)
• General Distance Balancing for Quantum Locally Testable Codes [12.547444644243544]
  We prove a lower bound on the soundness of quantum locally testable codes under the distance balancing construction of Evra et al. arXiv:2004.07935 [quant-ph] Our technical contribution is that the new soundness of the quantum code is at least the old soundness divided by the classical code length (up to a constant factor) By using a good classical LDPC code, we are able to grow the dimension of the hypersphere product codes arXiv:1608.05089 [quant-ph] and the hemicubic codes arXiv:1911.03069 [
  arXiv  Detail & Related papers  (2023-05-01T07:03:10Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Quantum Locally Testable Code with Constant Soundness [1.5559957709246597]
  We present two constructions of quantum locally testable codes (QLTC) with constant soundness. In the first approach, we introduce an operation called check product, and show how this operation gives rise to QLTCs of constant soundness. In the second approach, we consider hypergraph product of a quantum code and a classical repetition code, and observe a special case in which the soundness of component codes is preserved.
  arXiv  Detail & Related papers  (2022-09-23T04:38:01Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Single-shot quantum error correction with the three-dimensional subsystem toric code [77.34726150561087]
  We introduce a new topological quantum code, the three-dimensional subsystem toric code (3D STC) The 3D STC can be realized by measuring geometrically-local parity checks of weight at most three on the cubic lattice with open boundary conditions.
  arXiv  Detail & Related papers  (2021-06-04T17:35:00Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Fault-tolerant quantum speedup from constant depth quantum circuits [0.0]
  We show that there is no classical algorithm which can sample according to its output distribution in $poly(n)$ time. We present two constructions, each taking $poly(n)$ physical qubits, some of which are prepared in noisy magic states.
  arXiv  Detail & Related papers  (2020-05-23T13:53:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.