대규모 고전 데이터 처리에 있어 기하급수적인 양자 우위
Exponential quantum advantage in processing massive classical data
한국어 초록
고전 데이터 처리 및 머신러닝 분야에서 널리 적용 가능한 양자 우위(quantum advantage)를 입증하는 것은 오랜 기간 근본적인 미해결 문제였습니다. 본 연구에서는 폴리로그(polylogarithmic) 크기의 소형 양자 컴퓨터가 샘플을 실시간(on the fly)으로 처리함으로써 대규모 고전 데이터에 대한 대규모 분류(classification) 및 차원 축소를 수행할 수 있음을 증명합니다. 반면, 동일한 예측 성능을 달성하는 임의의 고전 컴퓨터는 기하급수적으로 더 큰 크기를 필요로 합니다. 나아가, 요구되는 크기보다는 작지만 기하급수적으로 큰 고전 컴퓨터라 하더라도 초다항식적(superpolynomially)으로 더 많은 샘플과 시간을 필요로 합니다. 저자들은 단일 세포 RNA 시퀀싱 및 영화 리뷰 감성 분석(sentiment analysis)을 포함한 실제 응용 분야에서 이러한 양자 우위의 증거를 제시하며, 60개 미만의 논리 큐비트로 크기를 4~6 자릿수(orders of magnitude) 감소시킬 수 있음을 입증합니다. 이러한 양자 우위는 무작위 고전 데이터 샘플만을 사용하여 양자 중첩 상태에서 고전 세계에 접근하는 알고리즘인 양자 오라클 스케칭(quantum oracle sketching)을 통해 가능해집니다. 고전적 그림자(classical shadows)와 결합된 본 알고리즘은 데이터 로딩 및 판독(readout) 병목 현상을 우회하여 대규모 고전 데이터로부터 간결한 고전 모델을 구축하며, 이는 해당 양자 컴퓨터보다 기하급수적으로 크지 않은 고전 컴퓨터로는 불가능함이 증명된 과제입니다. 이러한 양자 우위는 고전 컴퓨터에 무제한의 시간이 주어지거나 BPP = BQP인 경우에도 유지되며, 오직 양자역학의 정확성에만 의존합니다. 종합적으로, 본 연구 결과는 고전 데이터 기반 머신러닝이 양자 우위의 광범위하고 자연스러운 영역이자 복잡도 경계에서 양자역학을 검증하는 근본적인 테스트임을 확립합니다.
원문 초록
Broadly applicable quantum advantage, particularly in classical data processing and machine learning, has been a fundamental open problem. In this work, we prove that a small quantum computer of polylogarithmic size can perform large-scale classification and dimension reduction on massive classical data by processing samples on the fly, whereas any classical machine achieving the same prediction performance requires exponentially larger size. Furthermore, classical machines that are exponentially larger yet below the required size need superpolynomially more samples and time. We provide evidence for these quantum advantages in real-world applications, including single-cell RNA sequencing and movie review sentiment analysis, demonstrating four to six orders of magnitude reduction in size with fewer than 60 logical qubits. These quantum advantages are enabled by quantum oracle sketching, an algorithm for accessing the classical world in quantum superposition using only random classical data samples. Combined with classical shadows, our algorithm circumvents the data loading and readout bottleneck to construct succinct classical models from massive classical data, a task provably impossible for any classical machine that is not exponentially larger than the quantum machine. These quantum advantages persist even when classical machines are granted unlimited time or if BPP = BQP, and rely only on the correctness of quantum mechanics. Together, our results establish machine learning on classical data as a broad and natural domain of quantum advantage and a fundamental test of quantum mechanics at the complexity frontier.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
다중모달 정서 해석을 위한 토큰-영역 유도 교차 어텐션 융합
Token-Region Guided Cross-Attention Fusion for Multimodal Affect Interpretation
소셜 네트워크상의 다중모달 콘텐츠에 대한 자동 분석은 디지털 시대에 대중 정서와 정보 확산을 이해하기 위한 핵심 과제가 되었다. 그러나 인터넷 밈 분류는 시각적 단서와 내장된, 종종 스타일화된 텍스트 간의 복잡한 상호작용으로 인해, 특히 벵골어와 같은 저자원 언어에서는 여전히 계산적으로 어려운 과제로 남아 있다. 본 논문은 Multimodal Cross-Attention Fusion 프레임워크를 도입하여 벵골어 밈에서의 정치적 의도 탐지 문제를 다룬다. 먼저 비전-언어 모델(Vision-Language Model)을 활용하여 노이즈가 많은 밈 이미지로부터 고품질 OCR 텍스트를 추출한다. 이어서 시각 및 텍스트 특징을 인코딩하고, 의미 토큰을 시각 영역과 정렬하는 교차 모달 다중 헤드 어텐션 메커니즘을 통해 이를 융합한다. 또한 도메인 특화 정치 어휘집을 지식 사전(knowledge prior)으로 통합하는 방안을 탐구한다. PoliMemeDecode1 데이터셋에 대한 실험 평가 결과, 우리의 어텐션 기반 융합은 단일 모달 기준선 및 표준 연결(concatenation) 방법을 크게 능가하며, 약 0.94의 최첨단 Macro-F1을 달성하였다. 해석 가능성 분석은 또한 모델이 텍스트 의미를 시각적 증거에 효과적으로 그라운딩(grounding)하도록 학습함을 확인한다.
Twitter Sentiment Analysis
Fuzzy Pooling
Aspect-level Sentiment Classification with HEAT (HiErarchical ATtention) Network
Thumbs up? Sentiment Classification using Machine Learning Techniques
scTrilemma: 단일 세포 표현 학습에서 정체성, 불변성, 충실도의 균형 잡기
scTrilemma: Balancing Identity, Invariance, and Fidelity in Single-Cell Representation Learning
단일 세포 RNA 시퀀싱(single-cell RNA-seq) 표현 학습은 근본적으로 레이블이 없습니다(label-free). 즉, 세포 정체성(cell identity), 상태(state), 맥락(context)이 고정된 학습(training) 목표가 아니므로, 무엇이 신호(signal)이고 방해 요인(nuisance)인지는 분석 목적에 따라 달라집니다. 따라서 단일 표현은 생물학적 정체성과 상태를 보존하고, 방해 요인이 되는 맥락에 강건해야 하며, 유전자 발현 분석에 필요한 유전자 수준의 변이를 유지해야 합니다. 본 연구에서는 이 세 가지 요구 사항을 '표현 트릴레마(representation trilemma)'라고 부릅니다. 이 문제를 해결하기 위해, 모든 발현 기반 변이를 하나의 임베딩(embedding)으로 강제 통과시키는 대신 임베딩, 디코더, 사전 분포(prior)로 라우팅하는 잠재 병목 VAE인 scTrilemma를 소개합니다. scTrilemma는 단일 재구성 목표 아래에서 대상 어노테이션이나 보조 표현 손실 없이, 발현량에 따라 유전자 토큰을 게이팅하고, 세포 표현을 디코더로 라우팅하며, 레이블이 지정되지 않은 유사 벌크(pseudo-bulk) 맥락에 따라 사전 분포를 조건화합니다. 연속적인 CZ CELLxGENE Census 릴리스에 대한 릴리스 기반 제로샷(zero-shot) 평가에서, scTrilemma는 세 가지 요구 사항을 동시에 모두 선도하며 여러 질병 환경 전반에 걸쳐 생물학적 상태, 차등 발현(differential-expression) 및 경로(pathway) 구조를 보존합니다. 잠재 변수 개입(latent intervention) 실험은 다른 요구 사항에 거의 영향을 주지 않고 맥락을 제거할 수 있음을 추가로 보여주며, 정체성과 충실도 간의 관계만이 상충 관계(tension)로 남음을 입증합니다. 코드는 https://github.com/yunhak0/scTrilemma 에서 공개적으로 이용 가능합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
169 pages, including 10 pages of main text and 13 figures. Code available at https://github.com/haimengzhao/quantum-oracle-sketching